Дискрет анал

2-маъруза машғулоти

1. 
   Ориентирланган (йўналтирилган) графларда занжир ва цикл.
   

Агар графнинг А ва В учлари қирраларнинг бирор кетма-кетлиги орқали туташтирилган бўлса, улар боғланган учлар дейилади. Агар бу кетма –кетлик бир хил кирралардангина иборат бўлмаса, бу граф занжир дейилади.
Агар занжирнинг барча учлари хам хар хил бўлса, бундай граф элементар граф дейилади. Агар занжир ёпик , яъни унинг бошлангич нуктаси ва охирги нуктаси ва охирги нуктаси биргина учда жойлашган булса, уни цикл деб аталади. Барча учлари хар хил бўлган цикл элементар цикл дейилади.

2. 
   Графларнинг характеристикалари.
   

Таркибида графнинг хар бир кирраси факат бир мартадагина катнашадиган циклга эга булган граф Эйлер графи дейилади.
Теорема. Барча учларнинг даражалари жуфт бўлган боғланган граф Эйлер чизиғи бўлади. Энди қирраларнинг карралиги тушунчасини караймиз. Агар графнинг иккита учи бир неча қирралар билан туташтирилган булса, у холда граф каррали қиррага эга дейилади. Каррали қирраларни устига карралик кўрсаткичи ёзилган битта қирра билан алмаштириш мумкин. Карралик тушунчасидан хар хил ўтказиш қобилиятига эга булган транспорт йуллари ёки электр тармоклари системасини графларда ифодалашда фойдаланиш қулайдир.

3. 
   Граф матрицаси.
   

Ҳар бир қиррасининг йўналиши кўрсатилган граф йўналиши кўрсатилган граф дейилади. Йўналиши кўрсатилган графлар транспорт ситемаларини, шу жумладан, бир томонлама харакатли кўча тармокларини анализ қилишда фойдаланилади. Йўналиши кўрсатилган графларнинг мухим татбиқларидан бири тармоқли планлаштириш ва бошқариш методларидан иборат.
3-маъруза машғулоти

1. 
   Графда энг қисқа йўлни топиш усуллари.
   

Кўп амалий масалаларни ечишда йўналишга эга бўлмаган боғланган графда икки ихтиерий учи орасидаги энг қисқа йўлни топиш масаласини татбиқ этишга тўғри келади. Умумий холда графларда энг қисқа йўлни топиш масаласи қуйидагича қўйилади.
Берилган йўналишга эга бўлмаган G(X,U) графнинг хар бир қиррасиз бирор узунлик деб аталувчи L(u)0 сони булиб, натижада хосил бўлган ихтиерий занжир узунлиги

ифода билан характерланади.

Берилган G графда ихтиёрий а ва в учлари орасида шундай йўлни топиш керакки натижада у энг қисқа узунликка эга бўлсин.
Қирралари бир бирлик узунликка эга бўлган графларда энг қисқа узунликка эга бўлган йўлни топиш.

2.