Fan nomi algoritmlarni loyihalash hafta

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI


Dasturiy injiniring kafedrasi

LABORATORIYA MASHG’ULOTI

FAN NOMI		Algoritmlarni loyihalash
HAFTA		12
MAVZU:		Kesishmaydigan to’plam ostilari va birlashmalarini qidirish algoritmi.
ISHDAN MAQSAD:		Graflar ustida amallar bajarish Graflarni birlashtirish; Graflarni biriktirish;

Graflarni birlashtirish. va graflar berilgan bo’lsin. Uchlari to’plami va qirralari korteji kabi aniqlangan graf va graflarning birlashmasi deb ataladi va ko’rinishda belgilanadi. 2.5–rasmda uchlari to’plami kesishmaydigan va graflarning birlashmasi amali tasvirlangan.

1–rasm.
Ta’rif: Agar birlashtirilayotgan graflarning uchlari to’plami kesishmasa, u holda bu graflarning birlashmasi dizyunkt birlashma birlashma deyiladi.

Uchlari to’plamlari kesishadigan graflarning birlashmasi amali 2.6–rasmda tasvirlangan.
4

2–rasm.

T1={
1–rasmda tasvirlangan birlashma dizyunkt, 2–rasmda tasvirlangan birlashma esa – dizyunkt emas.
Dastur kodi:
#include
using namespace std;
int main()
{int k,l,a,b,u,v,n,m,i,j,ne=1;
int mas[10]={0}, min, mincost=0,cost[10][10],mass[5][5],mas1[5]={0};
int path[100]={0}; //ushbu massivda yulni tashkil qiladigan tugunlar yoziladi
int path_index=0;
cout<<"1-Graf tugunlar sonini kiriting "; cin>>n;
cout<<"2-Graf tugunlar sonini kiriting "; cin>>m;
cout<<"1-Graf qushnilik matritsasini kiriting\n";
for(i=0;ifor(j=0;j{cin>>cost[i][j];}
cout<<"2-Graf qushnilik matritsasini kiriting\n";
for(i=0;ifor(j=0;j{cin>>mass[i][j];}
for(i=0;ifor(j=0;jif(cost[i][j]==1&&mass[i][j]==1){a=i;
for(u=j;uif(mass[i][u]!=0)
cost[i][u]=mass[i][u];} goto L1;
}
}
L1: for(i=a+1;ifor(j=0;jif(mass[i][j]!=0)
cost[i][j]=mass[i][j];}
cout<for(i=0;ifor(j=0;jcout<cout<return 0;
}




Graflarni biriktirish. va graflar berilgan bo’lsin. va graflar birlashtirilshi hamda grafning har bir uchi grafning har bir uchi bilan qirra vositasida tutashtirilishi natijasida hosil bo’lgan graf va graflarning birikmasi deb ataladi va ko’rinishda belgilanadi.
3–rasmda uchlari to’plamlari kesishmaydigan va graflarning birikmasi amali tasvirlangan. Agar uchlari to’plamlari kesishmasi bo’sh bo’lmagan graflarni biriktirish zarur bo’lsa, u holda hal qilinayotgan masala hossalarini e’tiborga olish kerak bo’ladi.

3–rasm.

Laboratoriya mashg’uloti 12.1