4
Graf haqida tushunchasi
Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler tomonidan
o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari
haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga
asos bo‘ldi.
Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar
joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4,
5, 6 va 7 raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shahrini o‘sha
davrda to‘rtta , , va qismlarga bo‘lgan. Shaharning ixtiyoriy qismida joylashgan
uydan chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib
kelish mumkinmi? Kyonigsberg ko‘priklari haqidagi bu masalani hal qilish
jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu
marshrut Eyler sikli nomi bilan yuritiladi, mavjudligi shartlari ham topildi. Bu
natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. L.
Eylerning bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yicha
yagona ilmiy ish bo‘lib keldi.
5
Grafning uchlari va qirralari (yoylari) uning
elementlari deb at
aladi. graf
elementlarining soni ()ga tengdir, bu yerda grafning uchlari soni va bilan uning
qirralari (yoylari) soni belgilangan.
Grafning qirrasi (yoyi), odatda, uni tashkil etuvchi uchlar yordamida , yoki , yoki
ko‘rinishda belgilanadi. Boshqa belgilashlar ham ishlatiladi: masalan, yoy uchun yoki
, qirra uchun , yoy yoki qirra uchun (ya’ni uchlari ko‘rsatilmasdan bitta harf
vositasida) ko‘rinishda.
Graf yoyi uchun uning chetki uchlarini ko‘rsatish tartibi muhim ekanligini
ta’kidlaymiz, ya’ni va yozuvlar bir-biridan farq qiluvchi yoylarni ifodalaydi. Agar
yoy ko‘rinishda ifodalangan bo‘lsa, u holda uning boshlang‘ich uchi, esa oxirgi uchi
deb ataladi. Bundan tashqari, yoy ko‘rinishda yozilsa, u haqida uchdan chiquvchi
(boshlanuvchi) va uchga kiruvchi (uchda tugovchi) yoy deb aytish ham odat tusiga
kirgan.
Qirra uchun uning yozuvidagi harflar joylashish tartibi muhim rol o‘ynamaydi va va
elementlar qirraning uchlari yoki chetlari deb ataladi.
Agar grafda yo qirra, yo yoy, yoki yoy topillsa, u holda va uchlar tutashtirilgan
deyiladi. Agar grafning ikkita uchini tutashtiruvchi qirra yoki yoy bor bo‘lsa, u holda
ular qo‘shni uchlar deb, aks holda esa, qo‘shni bo‘lmagan uchlar deb aytiladi.
Grafning ikkita uchi qo‘shni bo‘lsa, ular shu uchlarni tutashtiruvchi qirraga (yoyga)
insident, o‘z navbatida, qirra yoki yoy bu uchlarga insident deyiladi.
Grafda ikkita qirra (yoy) umumiy chetga ega bo‘lsa, ular qo‘shni qirralar (yoylar)
deyiladi.
6
Shuni ta’kidlash kerakki, qo‘shnilik tushunchasi grafning bir jinsli, insidentlik
tushunchasi esa uning turli jinsli elementlari orasidagi munosabatni ifodalaydi.
Ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni va qirralar (yoylar)
soni ga qarab belgilanadi va bu holda grafni
-graf deb ataydilar.
Agar grafda kortej faqat qirralardan iborat bo‘lsa, u holda yo‘naltirilmagan
(oriyentirlanmagan) va faqat yo‘naltirilgan (oriyentirlangan) qirralardan (ya’ni,
yoylardan) tashkil topgan bo‘lsa, u holda u yo‘naltirilgan (oriyentirlangan) graf deb
ataladi. Oriyentirlangan graf, qisqacha, orgraf deb ham ataladi.
Qator hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham
bo‘lgan graflar bilan ish ko‘rishga to‘g‘ri keladi. Bunday graflar aralash graflar deb
ataladi.
Agar grafning (orgrafning) korteji tarkibida to‘plamdan olingan takrorlanuvchi
elementlar bo‘lsa, u holda ular karrali yoki parallel qirralar (yoylar) deb ataladi.
Karrali qirralari yoki yoylari bo‘lgan graf multigraf deyiladi.
Ikkala chetki (boshlang‘ich va oxirgi) uchlari ustma-ust tushgan qirra (yoy), ya’ni
grafning elementi sirtmoq deb ataladi. Sirtmoq, odatda, yo‘naltirilmagan deb
hisoblanadi. Qirralari (yoylari) orasida sirtmoqlari bo‘lgan graf psevdograf deyiladi.
Umumiy holda uchlar to‘plami va (yoki) qirralar (yoylar, qirra va yoylar) korteji
cheksiz ko‘p elementli bo‘lishi mumkin. Bundan keyin to‘plam va kortej faqat chekli
bo‘lgan graflarni qaraymiz. Bunday graflar chekli graflar deb ataladi.
Hech qanaqa qirra (yoy) bilan bog‘lanmagan uch yakkalangan (ajralgan, xolis,
yalong‘och) uch deb ataladi.
7
Faqat yakkalangan uchlardan tashkil topgan graf (ya’ni, grafda qirralar va yoylar
bo‘lmasa) nolgraf yoki bo‘sh graf deb ataladi. Uchlari soni ga teng bo‘lgan bo‘sh
grafni yoki kabi belgilash qabul qilingan.
Istalgan ikkita uchlari qo‘shni bo‘lgan sirtmoqsiz va karrali qirralarsiz
oriyentirlanmagan graf to‘la graf deb ataladi. Uchlari soni ga teng bo‘lgan to‘la graf
bilan belgilanadi. Ravshanki, grafning qirralar soni bo‘ladi.
Agar orgrafning istalgan ikkita uchini har bir yo‘nalishda tutashtiruvchi faqat bittadan
yoy mavjud bo‘lsa, u holda unga to‘la orgraf deb ataladi. Ravshanki, to‘la grafdagi
qirralarning har birini ikkita (yo‘nalishlari bir-biriga qarama-qarshi bo‘lgan) yoylarga
almashtirilsa, natijada to‘la orgraf hosil bo‘ladi. Shuning uchun, to‘la orgrafdagi
yoylar soni oriyentirlanmagan to‘la grafdagi qirralar sonidan ikki baravar ko‘pdir,
ya’ni uchlari ta bo‘lgan to‘la orgrafdagi yoylar soni bo‘ladi.
Agar grafning uchlariga qandaydir belgilar, masalan,
sonlari mos qo‘yilgan
bo‘lsa, u belgilangan graf deb ataladi.
Agar va graflarning uchlari to‘plamlari, ya’ni va to‘plamlar orasida uchlarning
qo‘shnilik munosabatini saqlaydigan o‘zaro bir qiymatli moslik o‘rnatish mumkin
bo‘lsa, u holda va graflar izomorf graflar deb ataladi. Bu ta’rifni quyidagicha ham
ifodalash mumkin: agar
va ularga mos bo‘lgan (,
) uchun (, ) bo‘lsa, u holda
va graflar izomorfdir. Agar izomorf graflardan biri oriyentirlangan bo‘lsa, u holda
ikkinchisi ham, albatta, oriyentirlangan bo‘lishi va ulardagi mos yoylarning
yo‘nalishlari ham bir-birlariga mos bo‘lishlari shart.
Graf uchiga insident qirralar soni shu uchning lokal darajasi, yoki, qisqacha, darajasi,
yoki valentligi deb ataladi. Grafdagi uchning darajasini
bilan belgilaymiz.
8
Sirtmoqqa insident bo‘lgan uchning darajasini aniqlashda shuni e’tiborga olish
kerakki, qaralayotgan masalaga bog‘liq holda sirtmoqni bitta qirra deb ham, ikkita
qirra deb ham hisoblash mumkin. Ravshanki, ajralgan uchning darajasi nolga teng.
Darajasi birga teng uch chetki (yoki osilgan) uch deb ataladi. Chetki (osilgan) uchga
insident qirra ham chetki (yoki osilgan) qirra deb ataladi.
Agar grafning barcha uchlari bir xil darajaga ega bo‘lsa, u holda bunday graf darajali
regulyar graf deb ataladi. Uch darajali regulyar graf kubik (yoki uch valentli) graf deb
ataladi. graf nol darajali regulyar graf ekanligini, esa () darajali regulyar graf
ekanligini ta’kidlaymiz.
Ko‘rinib turibdiki, oriyentirlanmagan grafda barcha uchlar darajalarining yig‘indisi
qirralar sonining ikki baravariga teng juft son bo‘ladi, chunki qirralarni sanaganda har
bir qirra hisobda ikki marta qatnashadi. Shunday qilib, XVIII asrdayoq L. Eyler
tomonidan isbotlangan quyidagi tasdiq o‘rinlidir.
1- lemma (“ko‘rishishlar” haqida).
Ixtiyoriy
oriyentirlanmagan grafda barcha uchlar
darajalari yig‘indisi qirralar sonining ikki baravariga teng.
Agar grafning uchlar to‘plamini o‘zaro kesishmaydigan shunday ikkita qism
to‘plamlarga (bo‘laklarga) ajratish mumkin bo‘lsaki, grafning ixtiyoriy qirrasi bu
to‘plamlarning biridan olingan qandaydir uchni ikkinchi to‘plamdan olingan biror
uch bilan tutashtiradigan bo‘lsa, u holda bunday graf ikki bo‘lakli graf (bixromatik
yoki Kyonig grafi) deb ataladi. Ta’rifdan ko‘rinib turibdiki, ikki bo‘lakli grafning har
bir bo‘lagidagi ixtiyoriy ikkita uchlar qo‘shni bo‘la olmaydi. Biror bo‘lagida faqat
bitta uch bo‘lgan to‘la ikki bo‘lakli graf yulduz deb ataladi.
Agar ikki bo‘lakli grafning turli bo‘laklariga tegishli istalgan ikkita uchi qo‘shni
bo‘lsa, u holda bu graf to‘la ikki bo‘lakli graf deb ataladi. To‘la ikki bo‘lakli grafni
bilan belgilaymiz, bu yerda va bilan grafning bo‘laklaridagi uchlar sonlari
9
belgilangan.
graf uchun va bo‘lishi ravshan, bu yerda – grafning uchlari soni,
– uning qirralari soni.
Grafning ikki bo‘lakli graf bo‘lishi haqidagi ba’zi qo‘shimcha ma’lumotlar
(Kyonig teoremasi) ushbu bobning 4- paragrafida keltirilgan.
Ikkidan katta ixtiyoriy natural son uchun bo‘lakli graf tushunchasini ham kiritish
mumkin.
|
