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.
