Yashiklar prinsipi

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

Режа:

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

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

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