Algoritmlar va berilganlar strukturasi

 Regulyar graflar. 1-rasmdagi G
1
,G
3
,G
8
,G
11
graflari ularning har birida barcha 
uchlar bir xil darajaga ega ekanligi bilan ajralib turadi. Bunday graflar regulyar yoki 
bir jinsli deb nomlanadi. 20-rasmda uchinchi, toʻrtinchi va beshinchi darajadagi 
muntazam sakkizta uchli graflar koʻrsatilgan. 
 
5-rasm. Regulyar graflar 

Uchinchi darajali graflar kubik deb nomlanganiga e‘tibor bering. – rasmdagi 
G
11
va –rasmdagi G
1
. Shubhasiz, d darajali regulyar grafdagi qirralarning soni m=1/2nd
ga teng. Bundan kelib chiqadiki, toq sonli uchlar uchun regulyar graf faqat juft 
darajaga, toq daraja uchun esa faqat uchlar soni boʻlishi mumkin. Shuning uchun har 
qanday kubik graf uchlarning juft soniga ega.
Grafni tasvirlash usullari
Grafni tasvirlash uchun bir nechta usullardan foydalaniladi. Graflardan oʻtish 
uchun siz oʻzingizning muammoingizni eng samarali hal qiladiganlardan 
foydalanishingiz kerak. Koʻpincha, tanlov qoʻshnilik matritsasi va qoʻshnilik 
roʻyxati oʻrtasida boʻladi (quyidagi jadval ikkala yondashuvning samaradorligini 
taqqoslaydi). Shu bilan birga, oʻrnatilgan C-massivga tayanib, oʻzingizning 
ma‘lumotlar tuzilmalaringizni modellashtirishingiz va STD-da mavjud boʻlgan turli 
xil konteynerlardan foydalanishingiz mumkin. 
1-misol; 
using
System; 
using
System.Collections.Generic; 
using
System.Linq; 
using
System.Text; 
using
System.Threading.Tasks; 
namespace
ConsoleApp15 
{ 
class
Program
{ 
static
void
Main(
string
[] args) 
{ 
Random rand = 
new
Random(); 
Queue<
int
> q = 
new
Queue<
int
>();
string
exit = 
""
; 
int
u; 
u = rand.Next(3, 5); 
bool
[] used = 
new
bool
[u + 1];
int
[][] g = 
new
int
[u + 1][];
for
(
int
i = 0; i < u + 1; i++) 
{ 
g[i] = 
new
int
[u + 1]; 
Console.Write(
"\n({0}) вершина -->["
, i + 1); 
for
(
int
j = 0; j < u + 1; j++) 
{ 
g[i][j] = rand.Next(0, 2); 

g[i][i] = 0; 
foreach
(var item 
in
g[i]) 
{ 
Console.Write(
" {0}"
, item); 
} 
Console.Write(
"]\n"
); 
} 
} 
Console.ReadKey(); 
} 
} 
} 
(1) вершина -->[ 0 0 0 0 0] 
 0 1 0 0 0] 
 0 1 0 0 0] 
 0 1 0 1 0] 
 0 1 0 1 0] 
 
(2) вершина -->[ 0 0 0 0 0] 
 0 0 0 0 0] 
 0 0 1 0 0] 
 0 0 1 0 0] 
 0 0 1 0 1] 
 
(3) вершина -->[ 1 0 0 0 0] 
 1 0 0 0 0] 
 1 0 0 0 0] 
 1 0 0 0 0] 
 1 0 0 0 0] 
 
(4) вершина -->[ 1 0 0 0 0] 
 1 0 0 0 0] 

 1 0 0 0 0] 
 1 0 0 0 0] 
 1 0 0 0 0] 
 
(5) вершина -->[ 0 0 0 0 0] 
 0 1 0 0 0] 
 0 1 1 0 0] 
 0 1 1 1 0] 
 0 1 1 1 0] 
2-misol; 
# include  
# include  
using namespace std; 
void Dijkstra(vector>>&, int&); 
int main(){ 
 
vector>> G { 
 
 
{{1,1},{3,6}}, 
 
 
{{0,1},{2,4},{3,3},{4,9},{5,8},{6,7}}, 
 
 
{{0,6},{1,4}}, 
 
 
{{1,3},{4,2}}, 
 
 
{{3,2},{1,9}}, 
 
 
{{1,8},{6,5}}, 
 
 
{{1,7},{5,5}} 
 
}; 
 
int vortex; 
 
cout <<"nomer versiyasi:"; 
 
cin>>vortex; 

 
return 0; 
} 
void Dijkstra(vector>>&myG, int &s){ 
 
const int inf=2000000000; 
 
size_t n=myG.size(); 
 
vector D(n,inf); 
 
vector P(n); 
 
vectorU(n,false); 
 
D[s]=0; 
 
for (size_t i=0; i
 
 
size_t v=1000000000; 
 
 
for (size_t j=0; j
 
 
if(!U[j]&&(v==1000000000 || D[j]
 
 
v=j; 
 
 
if(D[v]==inf) 
 
 
break; 
 
 
U[v]=true; 
 
 
auto beg=myG[v].begin(); 
 
 
auto lst=myG[v].end(); 
 
 
while (beg !=lst){ 
 
 
 
auto to=beg->first; 
 
 
 
auto len=beg->second; 
 
 
 
if (D[v]+len
 
 
 
 
D[v]=D[v]+len; 
 
 
 
 
P[to]=v; 
 
 
 
} 
 
 
 
beg++;