Topshiriq Graf cho’qqilarini bo’yash algoritmlari


Download 352.67 Kb.
bet1/4
Sana14.06.2020
Hajmi352.67 Kb.
#118716
  1   2   3   4
Bog'liq
CAL 018 Zokirov Farrux-61


CAL 018 ZOKIROV FARRUX

Yakuniy nazorat ish

Variant № 61


  1. Graf cho’qqilarini bo’yash algoritmlari

  2. Matritsaning bazis minori. Matritsalar rangi.Misol.

  3. Stek tuzilmasini tushuntiring va misol keltiring.



  1. Topshiriq

Graf cho’qqilarini bo’yash algoritmlari. Avvalo Graf ozi nima Grafning cho’qisi nima shuni bilib olishimiz kere bo’ladi.Graf nima ?



Graf – bu tugunlar va qirralar (tugunlar juftligini birlashtiruvchi) to’plamidan iborat bo’lgan abstrakt matematik ob’ektdir.

(V, E) sonlar juftligiga graf deyiladi, bu yerda V – iхtiyoriy bo`sh bo`lmagan to`plam, E esa V(2) ning qism to`plami (E V(2)), bunda V(2) V to`plam elementlarining tartiblanmagan juftliklari to`plami. V to`plam elementlari grafning uchlari deyiladi, E to`plam elementlari esa grafning qirralarideyiladi. Agar V chekli bo`lsa, graf chekli deyiladi, aks holda cheksiz graf deyiladi.



Grafning cho’qisi deb esa quyidagi holatga aytiladi. To`plamlarning bir-biri bilan bog`lanishini tasvirlashimizda graflardan foydalanamiz. Ko`p hollarda bo`sh bo`lmagan X to`plamning elementlari orasidagi o`zaro munosabati, ya’ni Y to`plam elementlarini X to`plamning o`ziga akslantirishni geometrik shaklda ifodalash qulay bo`lib qoladi. Bunday geometrik shakllar graflar deyiladi. Agarda bunga ilmiy ta’rif bersak quyidagi jumlaga ega bo`lamiz: Ikkitа tugunlаr (cho`qqi) vа yo`llаr (qovurg`alаr) to`plаmlаrining bir-biri bilаn bоg`lаnishigа grаflаr dеyilаdi. Uni G(X;U) ko`rinishidа ifоdаlаsh mumkin. Bu еrdа X- tugunlаr to`plаmi, U-yo`llаr to`plаmi.

Mаsаlаn: U1, U2- tugunlаr (cho`qqilаr); L-yo`l

Grafning cho’qqilari ko’p hollarda tugunlar deb yuritiladi. Tugun bu bir nеchtа yo`llаrning bоshlаnishi vа оxiri (tugаshi) bo`lishi mumkin. Tugunlаr sifаtidа elеktr stаnsiyalаrni misоl qilish mumkin.

Quyida Grafning cho’qillari (tugunlari)ni bo’yab o’tish orqali ushbu Grafning uchlari orasidagi eng qisqa masofani qidirish dastuini tuzib chiqamiz :



#include

#include

using namespace std;
int main()

{

int n;

cout<<"Graf uchlari va qirralari sonini kiriting: ";cin>>n;
int a[n][n]={0};

int d[n]={10000};

int v[n]={1};

for(int i=0;i

d[i] = 10000;

v[i] = 1;

for(int j=i+1;j

{

int tmp;

cout<>tmp;

a[i][j]=a[j][i]=tmp;

}

}

for(int i=0;i

{

for(int j=0;j

printf("%5d",a[i][j]);

cout<

}

int minex ;

int min ;

d[0] = 0;

do {

minex = 10000;

min = 10000;

int tmp;

for (int i = 0; i

{

if ((v[i] == 1) && (d[i]

{

min = d[i];

minex = i;

}

}
if (minex != 10000)

{

for (int i = 0; i

{

if (a[minex][i] > 0)

{

tmp = min + a[minex][i];

if (tmp < d[i])

{

d[i] = tmp;

}

}

}

v[minex] = 0;

}

} while (minex < 10000);

cout<<"\nUchigacha bo'lgan qisqa masofalar: \n";

for (int i = 0; i

printf("%5d ", d[i]);

int end = 4;

v[0] = end + 1;

int k = 1;

int weight = d[end];

while (end != 0)

{

for (int i = 0; i

if (a[i][end] != 0)

{

int temp = weight - a[i][end];

if (temp == d[i])

{

weight = temp;

end = i;

v[k] = i + 1;

k++;

}

}

}

cout<<"\nUchigacha neg qisqa yo'l:\n";

for (int i = k - 1; i >= 0; i--)

printf("%3d ", v[i]);

return 0;

}


  1. Download 352.67 Kb.

    Do'stlaringiz bilan baham:
  1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling