Энергетика ва саноатни ахборотлаштириш факультети «информатика ва ат» кафeдраси

ЎЗБEКИСТОН РEСПУБЛИКАСИ ОЛИЙ ВА ЎРТА МАХСУС ТАЪЛИМ ВАЗИРЛИГИ

НАМАНГАН МУҲАНДИСЛИК-ҚУРИЛИШ ИНСТИТУТИ

ЭНЕРГЕТИКА ВА САНОАТНИ АХБОРОТЛАШТИРИШ ФАКУЛЬТЕТИ

«ИНФОРМАТИКА ВА АТ» КАФEДРАСИ


«Тизимлар назарияси асослари» фанидан амалий машғулотларини ўтказиш бўйича

AMALIY MASHG’ULOT ISH

Бажарди: _____-ИАТ-19 гуруҳ талабаси
__________________________
Қабул қилди: __________________________


Наманган -2022

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

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

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

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

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

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

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

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

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

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

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

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

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

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