Graflar nazariyasining dastlabki ma’lumotlari
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.
Grafning abstrakt ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar. Avvalo, grafning abstrakt matematik tushuncha sifatidagi ta’rifini va boshqa ba’zi sodda tushunchalarni keltiramiz. V qandaydir bo‘shmas to‘plam bo‘lsin. Uning
v1 V
va v2 V
elementlaridan tuzilgan
v1, v2
ko‘rinishdagi barcha juftliklar
(kortejlar) to‘plamini (V to‘plamning o‘z-o‘ziga Dekart ko‘paytmasini) V V
belgilaymiz.
bilan
Graf deb shunday
V ,U
juftlikka aytiladiki, bu yerda
V
va U –
v1, v2
( v1 V ,
v2 V ) ko‘rinishdagi juftliklar korteji bo‘lib,
V V
to‘plamning
elementlaridan tuzilgandir.
Bundan buyon grafni belgilashda
V ,U
yozuv o‘rniga
(V ,U )
yozuvdan
foydalanamiz. Grafning tashkil etuvchilarini ko‘rsatish muhim bo‘lmasa, u holda uni lotin alifbosining bitta harfi, masalan, G bilan belgilaymiz.
G (V ,U )
graf berilgan bo‘lsin. V to‘plamning elementlariga G grafning
uchlari, V to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi.
Graflar nazariyasida “uch” iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi ham qo‘llaniladi. Umuman olganda, hanuzgacha graflar nazariyasining ba’zi iboralari bo‘yicha umumiy kelishuv qaror topmagan. Shuning uchun, bundan keyingi ta’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham keltirishga harakat qilamiz.
G (V ,U )
grafning ta’rifiga ko‘ra, U bo‘sh kortej bo‘lishi ham mumkin.
Agar U bo‘sh bo‘lmasa, u holda bu kortej
(a, b)
( a V ,
b V ) ko‘rinishdagi
juftliklardan tashkil topadi, bunda
a b
bo‘lishi hamda ixtiyoriy
(a, b)
juftlik U
kortejda istalgancha marta qatnashishi mumkin.
(a,b) U
juftlikni tashkil etuvchi a va b uchlarning joylashish tartibidan
bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash
mumkin. Agar
(a,b)
juftlik uchun uni tashkil etuvchilarning joylashish tartibi
ahamiyatsiz, ya’ni
(a, b) (b, a)
bo‘lsa,
(a,b)
juftlikka yo‘naltirilmagan
(oriyentirlanmagan) qirra (yoki, qisqacha, qirra) deyiladi. Agar bu tartib
muhim, ya’ni
(a, b) (b, a)
bo‘lsa, u holda
(a,b)
juftlikka yoy yoki yo‘naltirilgan
(oriyentirlangan) qirra deyiladi.
U kortejning tarkibiga qarab, uni yo grafning qirralari korteji, yo yoylari korteji, yoki qirralari va yoylari korteji deb ataymiz.
Grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi.
G (V ,U )
graf elementlarining soni (|V | | U | )ga tengdir, bu yerda G grafning
uchlari soni | V | 0
va | U |
bilan uning qirralari (yoylari) soni belgilangan.
Grafning qirrasi (yoyi), odatda, uni tashkil etuvchi uchlar yordamida (a,b) ,
yoki ab , yoki
(a;b)
ko‘rinishda belgilanadi. Boshqa belgilashlar ham ishlatiladi:
masalan, yoy uchun
(a, b)
yoki
(a, b) , qirra uchun
(a, b) , yoy yoki qirra uchun u
(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
(a,b)
va (b, a)
yozuvlar bir-biridan farq qiluvchi yoylarni
ifodalaydi. Agar yoy
(a,b)
ko‘rinishda ifodalangan bo‘lsa, u holda a uning
|
