Yashiklar prinsipi

Графлар устида амаллар

Режа:

1. 
   Графлар устида содда амаллар.
   
2. 
   Графларни бирлаштириш.
   
3. 
   Графларни бириктириш.
   
4. 
   Графларни кўпайтириш
   

Калит сўзлар: Графга учни, қиррани, ёйни қўшиш, қиррани иккига бўлиш, изоморф ва гомеоморф графлар, бўлиниш графи, графларнинг бирлашмаси, дизъюнкт бирлашма, графларнинг бирикмаси, графларнинг кўпайтмаси, ўлчовли куб.

1. Графлар устида содда амаллар. Графлар устида турли амаллар бажариш мумкин, масалан, графларни бирлаштириш, бириктириш, кўпайтириш, графни қисмларга ажратиш ва ҳоказо.
Енг содда амаллардан бири сифатида графдан учни олиб ташлаш амалини келтирса бўлади. Бу амални қўллаш берилган графнинг учлари тўпламидан бирорта элемент йўқотишни (олиб ташлашни) англатади. Натижада учлари сони биттага камайган янги граф ҳосил бўлади. Албатта, бу амални учлари сони иккитадан кам бўлмаган графлар учун қўллаш мумкин бўлиб, уни бажариш жараёнида олиб ташланаётган уч билан биргаликда шу учга инсидент бўлган барча қирралар (ёйлар) ҳам олиб ташланади.
Енг содда амаллар қаторига графдан қиррани (ёйни) олиб ташлаш амалини ҳам киритиш мумкин. Бу амалга кўра берилган графнинг қирралари (ёйлари) тўпламидан бирорта элемент йўқотилади (олиб ташланади). Берилган графдан қиррани (ёйни) олиб ташлаётганда шу қиррага (ёйга) инсидент учларни графда қолдириш ҳам йўқотиш ҳам мумкин. Бу ерда вазиятга қараб иш юритилади.
ва графлар берилган бўлсин. Агар ва графнинг барча қирралари (ёйлари) графнинг ҳам қирралари (ёйлари), яъни бўлса, у ҳолда граф графнинг қисм графи деб аталади.
1- мисол. 1- шаклда Петерсен графининг қисм графларидан бири тасвирланган. ■
Агар граф каррали қирраларга эга бўлмаса, у ҳолда учлари графнинг барча учларидан иборат бўлган шундай ягона граф мавжудки, графдаги барча жуфт учлар фақат ва фақат графда қўшни бўлмагандагина қўшнидир. Бундай граф берилган графнинг тўлдирувчи графи деб аталади.
Берилган граф учун тўлдирувчи графни қуриш жараёнини ҳам графлар устида бажариладиган амаллар қаторига киритиш мумкин. граф учун тўлдирувчи графни қуриш амалини қўллаш натижасида граф ҳосил бўлади. Исботлаш мумкинки, муносабат ўринлидир.
2- мисол. 2- шаклда тасвирланган граф 1- шаклда ифодаланган граф учун тўлдирувчи графдир.
Графлар устида шундай амалларни бажариш мумкинки, улар элементлари сони берилган графдагидан кўпроқ бўлган бошқа графларнинг ҳосил бўлишига олиб келади. Бундай амаллар қаторига учни қўшиш амали ёки қиррани (ёйни) қўшиш амалини киритиш мумкин.
Графга янги учни қўшиш турлича усул билан амалга оширилиши мумкин. Масалан, янги учни берилган графга қўшиш шу графнинг ва учларига инсидент бўлган қандайдир қиррасига қўшиш орқали қуйидагича икки босқичда бажарилиши мумкин:
1) қирра берилган графдан олиб ташланади;
2) ҳосил бўлган графга иккита янги қирралар: ва учларга инсидент қирра ҳамда ва учларга инсидент қирра қўшилади.
Бу жараён графда қиррага даражаси 2 бўлган янги учни қўшиш (киритиш) ёки қиррани иккига бўлиш амали деб аталади.
Агар граф графдан қиррани иккига бўлиш амалини чекли марта кетма-кет қўллаш воситасида ҳосил қилинган бўлса, у ҳолда граф графнинг бўлиниш графи деб аталади.
Бўлиниш графлари изоморф бўлган графлар гомеоморф графлар деб аталади.

3- шаклда тасвирланган графлар изоморф эмас, лекин улар гомеоморф, чунки бу графларнинг ҳар бири 4- шаклда тасвирланган бўлиниш графига эга.
2. Графларни бирлаштириш.
ва графлар берилган бўлсин. Учлари тўплами ва қирралари (ёйлари) кортежи каби аниқланган⁴ граф ва графларнинг бирлашмаси (уюшмаси) деб аталади ва кўринишда белгиланади.