Graflar ustida amallar. Marshrutlar va zanjirlar

Grafning bog‘lamliligi tushunchasi. Agar oriyentirlanmagan grafda chetlari a va b uchlardan iborat marshrut topilsa, bu a va b uchlar bog‘langan deb, marshrutning o‘zi esa a va b uchlarni bog‘lovchi marshrut debataladi.
_Tabiiyki, agar qandaydir uchlarni bog‘lovchi marshrut biror a_i
uchdan bir necha marta o‘tsa, u holda marshrutning siklik qismini olib


_tashlab (bunda siklik qismning o‘rniga marshrutda faqat a_i


uch


qoldiriladi) yana o‘sha uchlarni bog‘lovchi oddiy zanjir ko‘rinishdagi marshrutni hosil qilish mumkin. Shuning uchun, marshrut bilan bog‘langan uchlar doimo oddiy zanjir bilan ham bo‘glangan bo‘ladi degan xulosaga kelamiz.
Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf bog‘lamli graf deb ataladi.


Agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo‘lsa, u holda bu ikkita uch ekvivalent (bog‘langan) deyiladi. Bunday uchlar to‘plami grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. Uchlar to‘plami bo‘yicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni bog‘lamlilik komponentalari (qisqacha, komponentalari) deb ataluvchi bog‘lamli qismlarning birlashmasi deb qarash mumkin. Bu yerda berilgan graf bog‘lamlilik komponentalariga bo‘laklandi (ajratildi) deb aytish mumkin. Isbotlash mumkinki, har qanday graf o‘zining bog‘lamlilik komponentalarining diz’yunktiv birlashmasi sifatida ifodalanishi mumkin, bunda grafning bog‘lamlilik komponentalariga bo‘laklanishi bir qiymatli aniqlanadi.


Keyingi ma’lumotlarni bayon etish uchun yoq tushunchasi zarur bo‘ladi. Tekislikda geometrik ifodalanuvchi grafni qaraymiz. Bu grafga tegishli bo‘lmagan (ya’ni grafning hech qaysi uchi bilan ustma- ust tushmaydigan va uning hech qaysi qirrasida yotmaydigan) biror A nuqtani hech qaysi nuqtasi grafga tegishli bo‘lmagan uzluksiz chiziq bilan tutashtirish mumkin bo‘lgan barcha nuqtalar to‘plami grafning A nuqtani o‘zida saqlovchi yoqi deb ataladi.
Yoq tushunchasiga berilgan ta’rifga ko‘ra yoq grafning geometrik ifodalanishi yordamida tekislikning “qirqib” olinadigan qismidan iboratdir. Tekislikda geometrik ifodalanuvchi ixtiyoriy grafning hech bo‘lmaganda bitta yoqi bo‘lishi va uning bitta yoqi chegaraga ega emasligi (cheksizligi) o‘z-o‘zidan ravshandir.

• 
  teorema (Eyler 1752). Tekis va bog‘lamli
  

G  (V ,U )


graf uchun


m  r


 2  n


tenglik o‘rinlidir, bu yerda m  V


, n  U


, r – yoqlar soni.


Isboti. Teoremani isbotlash uchun matematik induksiya usulini grafdagi qirralar soni n bo‘yicha qo‘llaymiz. Induksiya usulining


bazasi sifatida


n  0


bo‘lgan holni qaraymiz. Bu holda teoremaning


tasdig‘iga ko‘ra


m  r  2


bo‘lishi kerak. Haqiqatdan ham, G tekis va


bog‘lamli graf bo‘lgani uchun, u yagona uchdan tashkil topadi va bu


uch yagona (cheksiz) yoqda yotadi, ya’ni holda teoremaning tasdig‘i to‘g‘ridir.


m  1 va


r  1. Demak, bu


Induksion o‘tish: teoremaning tasdig‘i n  k uchun to‘g‘ri bo‘lsin


deb faraz qilib, uning


n  k 1


uchun ham to‘g‘ri ekanligini


ko‘rsatamiz. Farazimizga ko‘ra .. tenglik o‘rinlidir. k ta qirraga ega G tekis va bog‘lamli grafga (k 1)- qirrani (uni e bilan belgilaymiz) shunday qo‘shish kerakki, bunda e qirra G graf joylashgan tekislikda yotsin va hosil bo‘lgan graf ham bog‘lamli bo‘lsin. Bu amalni bajarganda quyidagi uchta holdan biri ro‘y beradi:

• 
  qo‘shilayotgan qirra sirtmoqdir – bu holda e qirra, albatta, G grafdagi uchlardan biriga insident bo‘lib, yoqlardan birida yotadi va bu yoqni ikkiga (sirtmoq yotgan yoqning sirtmoq chizig‘i bilan chegaralangan ichki va tashqi qismlari) ajratadi, ya’ni uchlar soni
  

o‘zgarmaydi, yoqlar soni esa birga oshadi: m  r 1  2  k 1;

• 
  qo‘shilayotgan qirra G grafda bor bo‘lgan ikkita uchlarni tutashtiradi – bu holda ham grafning biror (e qirra yotgan) yoqi ikkiga
  

ajraladi, uchlari soni esa o‘zgarmaydi: m  r 1  2  k 1;

• 
  qo‘shilayotgan qirra sirtmoq emas va u G grafdagi uchlardan faqat bittasiga insidentdir – bu holda grafning biror yoqida e qirraga insident bo‘lgan bitta boshqa uch yasaladi (grafning uchlari soni bittaga oshadi) va e qirra joylashgan yoq yaxlitlikni saqlagan holda e
  

qirrani o‘z ichiga oladi (yoqlar soni o‘zgarmaydi):
■


m 1 r


 2  k 1.


2- teoremaning tasdig‘idagi deb ataladi.


m  r


 2  n


tenglik Eyler formulasi


Eyler formulasi stereometriyada ham qo‘llaniladi: uchlari ..ta, yoqlari r ta va qirralari n ta ixtiyoriy ko‘pyoqli uchun Eyler formulasi o‘rinlidir. Bu tasdiqning negizida isboti o‘quvchiga havola qilinayotgan quyidagi tasdiq yotadi: stereometriyada berilgan ta’rifga ko‘ra aniqlangan ixtiyoriy ko‘pyoqliga mos tekis izomorf graf mavjuddir.
Eyler teoremasidan bir qator natijalar kelib chiqadi. Masalan, bu teoremadan foydalanib uni osonlik bilan bog‘lamli bo‘lmagan graflar uchun quyidagicha umumlashtirish mumkin.

• 
  natija. Tekis
  

G  (V ,U )


graf uchun


m  r


 1 n  k


tenglik


o‘rinlidir, bunda m  V
komponentalar soni.


, n  U


, r – yoqlar soni, k – bog‘lamlilik

•