Yashiklar prinsipi

3- мисол. 5- шаклда учлари тўпламлари кесишмайдиган ва графларнинг бирлашмаси амали тасвирланган. ■
4- мисол. Учлари тўпламлари кесишадиган графларнинг бирлашмаси амали 6- шаклда тасвирланган. ■

Агар бирлаштирилаётган графларнинг учлари тўпламлари кесишмаса, у ҳолда бу графларнинг бирлашмаси дизъюнкт бирлашма деб аталади. Масалан, 5- шаклда тасвирланган бирлашма дизъюнкт, 6- шаклдаги бирлашма эса – дизъюнкт эмас.
3. Графларни бириктириш.
ва графлар берилган бўлсин. ва графлар бирлаштирилиши ҳамда графнинг ҳар бир учи графнинг ҳар бир учи билан қирра воситасида туташтирилиши натижасида ҳосил бўлган граф ва графларнинг бирикмаси (туташмаси) деб аталади ва кўринишда белгиланади.
5- мисол. Учта уй ва учта қудуқ ҳақидаги бошқотирма масалага мос граф учлари тўпламлари кесишмайдиган иккита ( ) нолграфларнинг бирикмасидир. ■
6- мисол. 7- шаклда учлари тўпламлари кесишмайдиган ва графларнинг бирикмаси амали тасвирланган. ■
Агар учлари тўпламлари кесишмаси бўш бўлмаган графларни бириктириш зарур бўлса, у ҳолда ҳал қилинаётган масала хоссаларини эътиборга олиб иш кўриш кераклигини таъкидлаймиз.
4. Графларни кўпайтириш. ва графлар берилган бўлсин. Учлари тўплами бўлган графнинг қирралари (ёйлари) кортежини қуйидагича аниқлаймиз: агар ва ёки ва бўлса, у ҳолда бўлади, бу ерда , , ва . Шундай усул билан ҳосол қурилган граф ва графларнинг кўпайтмаси деб аталади ва каби белгиланади.

Графларнинг кўпайтмаси таърифига асосан берилган ва графларнинг кўпайтмаси ҳисобланган графдаги:
– учлар ёки кўринишдаги жуфтликлардан иборатдир, бу ерда , ;
– ва учлар фақат ва фақат шу ҳолда қўшни бўладиларки, қачонки бу учларни (жуфтликларни) ташкил қилувчи элементларнинг бири унга мос элемент билан устма-уст тушган ҳолда бошқа элементлар ўз графида қўшни бўлишса, бу ерда , ; – , , ва муносабатлардан ва бўлиши келиб чиқади.
[John Harris, Jeffry L.Hirst, Michael Mossinghoff. Combinatorics and Graph Theory Springer 2008. 21- 26 бет]


7- мисол. 8- шаклда учлари тўпламлари кесишмайдиган ва графларнинг кўпайтмаси амали тасвирланган. ■
Графларни кўпайтириш амалини такрор қўллаш усули билан графлар назариясининг муҳим синфини ташкил этувчи ўлчовли кубларни аниқлаш мумкин. ўлчовли куб ( ) учлари сони иккига тенг бўлган тўла граф ёрдамида қуйидаги рекуррент формула билан аниқланади:
, .
Юқорида графлар устидаги баъзи амаллар ҳақида қисқача маълумот берилди. Шуни таъкидлаш лозимки, графлар устида бундан бошқа бир қатор амаллар ҳам бор.