Ўзбекистон республикаси олий ва ўрта махсус таълим вазирлиги наманган муҳандислик – Қурилиш институти

ЎЗБЕКИСТОН РЕСПУБЛИКАСИ


ОЛИЙ ВА ЎРТА МАХСУС ТАЪЛИМ ВАЗИРЛИГИ
НАМАНГАН МУҲАНДИСЛИК – ҚУРИЛИШ ИНСТИТУТИ

“САНОАТНИ АХБОРОТЛАШТИРИШ ФАКУЛЬТЕТИ”

“ИНФОРМАТИКА ВА АХБОРОТ ТЕХНОЛОГИЯЛАРИ” КАФЕДРАСИ

“ТИЗМЛАР НАЗАРИЯСИ АСОСЛАРИ” ФАНИДАН

Амалий машгулот № 3

Бажарди: 55С-Б-ИАТ-19 гуруҳ
талабаси
Ф. Рахмоналиев


Қабул қилди: Д.Шокиров


Наманган - 2022 йил


3 - АМАЛИЙ МАШҒУЛОТ.
ГРАФЛАР НАЗАРИЯСИНИ ЎРГАНИШ ВА УЛАР УСТИДА
АМАЛЛАР БАЖАРИШ
Ишдан мақсад: Талабаларга тизимларни математик ифодалаш учун графлар назариясидан кенг фойдаланишни ўргатиш. Графлар назарияси -чизиқлар ва тугунлардан тузилган баъзи бир геометрик конфигурациялар тўғрисидаги масалаларни ечишда ишлатилишини ўргатиш орқали талабаларда графларга доир билим, малака ва кўникма хосил қилишдан иборат.

Масаланинг қўйилиши: Талаба вариант бўйича графларга доир масалаларни яъни энг қисқа йўлни топиш алгоритмини тузиши, қўшнилик матрицасини хосил қилиш орқали MS Excel дастури ёрдамида вариантда берилган пунктлар орасидаги энг қисқа масофани аниқлаши ва керакли натижа олиши лозим.

НАЗАРИЙ ҚИСМ
Тизимлар назариясида тизимларни математик ифодалаш учун графлар назарияси кенг қўлланилади.
Графлар назарияси фани -чизиқлар ва тугунлардан тузилган баъзи бир геометрик конфигурациялар тўғрисидаги масалаларни ечишда ишлатилади. Бундай масалаларни ечишда, геометрик конфигурацияларда тугунлар бир -бири билан тўғри чизиқ ёки ёй билан бирлаштирилганми, буларнинг узунлиги қанча каби факторлар эътиборга олинмайди. энг муҳими шундаки, ҳар бир чизиқ қандайдир берилган иккита нуқтани бирлаштираяпти. Графлар назариясида қўлланиладиган таърифларни кўриб чиқамиз [9].
Таъриф. Тўплам ва В тўпламдан олинган жуфтликлар наборига граф дейилади.
В тўпламдаги лар қандайдир объектлар бўлиб, Г графнинг тугунлари дейилади. Е тўпламдаги ҳар бир жуфтлик графнинг ёйлари дейилади.
Агар қирра берилган бўлса, у ҳолда ва учлар бирлаштирилган дейилади.
1-мисол:
Агар ва бўлсин, у ҳолда ва тўплам графни ҳосил қилади.

Графнинг учларини тугунлар, 2 та учини бирлаштирувчи чизиқни ёйлар деб атаймиз.

1-расм. Граф.

Графнинг иккита тугуни умумий ёй билан ўзаро боғланган бўлса, улар қўшни тугунлар дейилади.
Агар нинг 2 та ёйи умумий тугунга эга бўлса, улар қўшма ёйлар дейилади.

2-расм. қўшма ёйли граф.

Бу ерда ёй ёйга қўшма, чунки умумий тугунга эга.
Бирорта тугунни ўзини - ўзига боғлайдиган ёйга ҳалқа дейилади.
3-расм. Ҳалқа.
Агар тугун ҳеч қандай ёйга инседент бўлмаса, у ҳолда бу тугун изоляцияланган тугун дейилади. Фақат изоляцияланган тугунлардан иборат графлар 0 графлар ёки бўш тўпламлар дейилади ва Г₀ билан белгиланади.

4-расм. Нолъ (бўш) граф.

Агар графнинг барча тугунлари ўзаро боғланган бўлса, бундай граф тўлиқ граф дейилади.

5-расм. Тўлиқ граф.

Агар графнинг барча қирраларида йўналиш кўрсатилган бўлса бундай граф йўналтириган граф дейилади.

6-расм. Йўналтирилган граф.

Агар графнинг қирраларида йўналтириш кўрсатилмаган бўлса, у ҳолда граф йўналтирилмаган граф дейилади.

7-расм. Йўналтирилмаган граф.

Амалий бажариш учун топшириқлар

1. 
   Қуйидаги берилган йўналтирилган графдаги 1-пунктдан 8-пунктга боришнинг энг қисқа масофасини топинг.
   

2. 
   Қуйидаги берилган йўналтирилган графдаги 1-пунктдан 9-пунктга боришнинг энг қисқа масофасини топинг
   

3. 
   Қуйидаги берилган йўналтирилган графдаги 1-пунктдан 10-пунктга боришнинг энг қисқа масофасини топинг
   

4. 
   Қуйидаги берилган йўналтирилган графдаги 1-пунктдан 9-пунктга боришнинг энг қисқа масофасини топинг
   

5. 
   Қуйидаги берилган йўналтирилган графдаги А-пунктдан F-пунктга боришнинг энг қисқа масофасини топинг
   

5-вариант