Yashiklar prinsipi

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