79
6-§. Graflar nazariyasi elementlari va o'tish algoritmlari
Graflarni oʻrganish bilan shugʻullanadigan
diskret matematikaning
boʻlimi ―Graflar nazariyasi‖ deb ataladi. Graflar nazariyasida ushbu
matematik obyektlarning
asosiy tushunchalari, xususiyatlari,
tasvirlash
usullari va qoʻllanilish sohalari batafsil koʻrib chiqilgan. Bizni faqat
dasturlashda muhim boʻlgan jihatlari qiziqtiradi.
Graflar - bu chiziqlar bilan bogʻlangan nuqtalar toʻplami. Nuqtalar
uchlar (tugunlar) chiziqlar esa
qirralar (yoylar) deb nomlanadi.
Grafning ifodalanishi.
Grafning toʻplam nazariya boʻyicha ta‟rifi.
Bizga
- boʻsh
boʻlmagan toʻplam berilgan, masalan {
}.
Uning barcha ikki elementli
ichki toʻplamlari toʻplamini
yozamiz. Bizning misolimiz uchun ushbu toʻplam quyidagicha boʻladi:
Ixtiyor ravishda ba‘zi bir
ni olamiz, masalan:
〈
〉 juftligi yoʻnaltirilmagan
G grafi deb nomlanadi, unda -
uchlar toʻplami,
- qirralarning toʻplami,
toʻplamining
ichki
toʻplami hisoblanadi.
Yuqoridagilardan kelib chiqib, ushbu ta‘rif
odatda quyidagicha
shakllantiriladi: 〈
〉 oriyentirlanmagan graflar juftligi deb ataladi,
agar
uchlar deb ataladigan boʻsh boʻlmagan elementlar toʻplami boʻlsa
va
– dagi qirralar deb ataluvchi turli elementlarning tartibsiz juftlari
toʻplami boʻlsa.
80
Graflar nazariyasida turli xil munosabatlarni
yozishda VG yoki
V(G) yozuvlari, G graf qirralarining toʻplami uchun EG yoki E(G)
yozuvlari ishlatiladi.
Grafni namoyish qilishning
vizual usuli - bu chizmalar
(diagramma), unda uchlar nuqta, doiralar
yoki boshqa figuralar bilan
tasvirlangan va qirralar juft uchlari tasvirlarini bir-biriga bogʻlaydigan
chiziqlar bilan tasvirlangan. Yuqorida tavsiflangan grafni bunday
tasvirlash uchun quyidagi variantlar berilgan.
