Режа: Асосий тушунчалар ва граф турлари Графларни ифодалаш усуллари Графларни кўрувдан ўтказиш

Режа:

1.Асосий тушунчалар ва граф турлари
2.Графларни ифодалаш усуллари
3.Графларни кўрувдан ўтказиш
4.Энг қисқа йўлни аниқлаш масаласи

Асосий тушунчалар ва граф турлари.
Граф - бу мураккаб чизиқсиз кўпбоғламли динамик тузилма бўлиб, мураккаб объектларнинг хусусиятлари ва муносабатларини акс эттиради.
Математик назарияда ва информатикада граф — бу тугунлар(учлар)дан иборат бўлган бўш бўлмаган тўплам ва тугунларни бирлаштирувчи ёйлар мажмуидир.

Граф турлари

Объектлар тугун ёки граф узеллари кўринишида ва муносабатлар ёй ёки йўналтирилган қирралар каби ифодаланади. «Граф» тушунчасини 1-марта 1936 йил венгрия математиги Денни Кёниг киритган. Лекин графлар назарияси бўйича 1-иш Леонард Эйлерга тегишли бўлган ва у 1736 йилда бажарилган эди.тугундан бошқа биронта тугунга мурожаат мавжуд

Ихтиёрий тугундан бошқа биронта тугунга мурожаат мавжуд бўлса, у холда бундай граф йўналтирилмаган граф дейилади (1-расм).
Агар граф тугунлари ўзаро боғланган бўлса-ю, лекин бу ёйлар орқали муносабат фақат бир томонлама бўлса, у холда бундай графлар йўналтирилган графлар дейилади.

Алохида ёйлар

Айнан битта қирра

Оғирликка эга бўлган граф (weighted graph) – бу қирралари (ёйлари) оғирликлари билан берилган граф хисобланаaди. (i,j) қирранинг оғирлиги w_ij каби белгиланади.

Графлар назариясининг айрим бир белгиланишлари:
•G=(V, E), бу ерда G – граф, V – тугунлар, E – қирралар;
• |V| – тугунлар сони;
•|E| – граф ўлчами (қирралар сони).
Агар графда боши ва охири битта тугунда туташадиган қирра мавжуд бўлса, унга илмоқли қирра дейилади.