Graflar ustida amallar. Marshrutlar va zanjirlar

misol. 7- shaklda uchlari to‘plamlari kesishmaydigan graflarning birikmasi amali tasvirlangan. ■



_{K2 va K3}


Agar uchlari to‘plamlari kesishmasi bo‘sh bo‘lmagan graflarni
biriktirish zarur bo‘lsa, u holda hal qilinayotgan masala xossalarini e’tiborga olib ish ko‘rish kerakligini ta’kidlaymiz.


_{1 4} ^{1 4
2 5 2 5}

• 
  shakl
  

Graflarni ko‘paytirish.


G_{1  (V1,U1 )} va G₂ (V_{2 ,U2 )} graflar berilgan bo‘lsin. Uchlari to‘plami V V_{1 V2} bo‘lgan G  (V ,U ) grafning qirralari (yoylari) kortejini quyidagicha aniqlaymiz: agar v₁ '  v₁ '' va (v_{2 ',v2 '') U2} yoki v₂ '  v₂ '' va (v_{1 ',v1 '') U1} bo‘lsa, u holda (v ',v '') U bo‘ladi, bu yerda v_{1 ',v1 ''V1,} v_{2 ',v2 ''V2 ,} v '  (v₁ ',v₂ ') V va v ''  (v_{1 '',v2 '') V . Shunday} usul bilan hosol qurilgan
G  (V ,U ) graf G₁ va G₂ graflarning ko‘paytmasi deb ataladi va G  G_{1  G2} kabi belgilanadi.
_Graflarning ko‘paytmasi ta’rifiga asosan berilgan G_{1  (V1,U1 ) va} G_{2  (V2 ,U2 )}
graflarning ko‘paytmasi hisoblangan G grafdagi:
_– uchlar (v_{1, v2 )} yoki (v_{2 , v1 )} ko‘rinishdagi juftliklardan iboratdir, bu yerda v_{1 V1,} v_{2 V2 ;}
– v '  (v₁ ',v₂ ') V va v ''  (v₁ '',v₂ '') V uchlar faqat va faqat shu holda qo‘shni bo‘ladilarki, qachonki bu uchlarni (juftliklarni) tashkil qiluvchi elementlarning biri unga mos element bilan ustma-ust tushgan holda boshqa elementlar o‘z grafida qo‘shni bo‘lishsa, bu yerda
_{v1 ',v1 ''V1, v2 ',v2 ''V2 ;
–} | V_{1 | m1, | V2}| m_{2 , | U1 | n1} va | U₂| n₂ munosabatlardan | V| m_1m2 va | U| m_1n2+m_2n1
bo‘lishi kelib chiqadi.
_7- misol. 8- shaklda uchlari to‘plamlari kesishmaydigan K_{2 va K3}


8- shakl
graflarning ko‘paytmasi amali tasvirlangan. ■


Dekart ko‘paytmalar bilan bog‘liq tuzilmalar ustida bajariladigan amallar boshqalaridan o‘ziga xosligi bilan ajralib turadi. Bu o‘ziga xoslik graflarni ko‘paytirish amalida namoyon bo‘ladi. Aniqrog‘i, graflar ko‘patmasida qatnashgan birorta grafning qirralari korteji bo‘sh bo‘lsada, ko‘paytirish amalini qo‘llash natijasida hosil bo‘lgan grafning qirralari korteji bo‘sh bo‘lmasligi ham mumkin. Haqiqatdan ham, yuqorida keltirilgan graflarning ko‘paytmasi ta’rifidan kelib chiqadiki, agar G  (V ,U ) graf G_{1  (V1,U1 )} va G₂ (V_{2 ,U2 )} graflarning ko‘paytmasi, ya’ni, G  G_{1  G2} bo‘lsa, u holda V V_{1 V2} bo‘ladi va U kortej elementlari bilan (V_{1 U2 ) (U1 V2 )} birlashma elementlari orasida o‘zaro bir qiymatli moslik mavjud. Shuning uchun, agar, masalan, U_{1  ,} U₂  bo‘lsa, u holda (V_{1 U2 ) (U1 V2 )  V1 U2}   bo‘ladi, chunki grafning tarifiga ko‘ra V_{1  . Demak, U  , ya’ni G1} bo‘sh graf bo‘lsada, G  G_{1  G2} bo‘sh bo‘lmagan grafdir.
Graflarni ko‘paytirish amalini takror qo‘llash usuli bilan graflar nazariyasining muhim sinfini tashkil etuvchi n o‘lchovli kublarni aniqlash mumkin. n o‘lchovli kub (Q_{n ) uchlari soni ikkiga teng} bo‘lgan to‘la graf K₂ yordamida quyidagi rekurrent formula bilan aniqlanadi: Q_{1 }K_{2 , Qn} K_{2  Qn1.}
Yuqorida graflar ustidagi ba’zi amallar haqida qisqacha ma’lumot berildi. Shuni ta’kidlash lozimki, graflar ustida bundan boshqa bir qator amallar ham bor.


Marshrutlar va zanjirlar haqida umumiy ma’lumotlar


Uchlari to‘plami V  {v₁,v₂,...,v_m} va qirralar korteji U  {u₁,u₂,...,u_n} bo‘lgan oriyentirlanmagan G  (V ,U ) graf berilgan bo‘lsin. Bu G grafdagi uchlar va qirralarning har ikki qo‘shni qirralari umumiy chetki uchga ega
_(...,v_{i ,u j ,vi ,uj ,vi ,...)}
1 1 2 2 3
ko‘rinishdagi chekli yoki cheksiz ketma-ketligi marshrut deb ataladi.
_Marshrutni uning uchlari ketma-ketligi (...,v_{i ,vi ,...) yoki qirralari}
1 2
_{ketma-ketligi} (...,u _{j ,u j ,...) ko‘rinishda ham belgilash mumkin.}
1 2
Agar marshrutda qandaydir uchdan oldin uchlar bo‘lmasa, bu uchni marshrutning boshlang‘ich uchi deb, shu uchdan keyin marshrutga tegishli uchlar bo‘lmaganda esa, uni marshrutning oxirgi uchi deb ataydilar.
Agar marshrutning boshlang‘ich uchi v_p va oxirgi uchi v_q bo‘lsa, u holda uni v_p uchdan v_q