1-ma’ruza. Graflar nazariyasi elementlari va o'tish algoritmlari. Grafni aniqlanishi.
orientirlangan va orientirlanmagan graflar. Lokal daraja. Yo`l va sikl. Grafni mashina
xotirasida ifodalash usullari
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 {
𝑣
1
, 𝑣
2
, 𝑣
3
, 𝑣
4
, 𝑣
5
}.
Uning barcha ikki elementli
𝑉
(2)
ichki toʻplamlari toʻplamini yozamiz. Bizning misolimiz
uchun ushbu toʻplam quyidagicha boʻladi:
Ixtiyor ravishda ba’zi bir
𝐸 ⊆ 𝑉
(2)
ni olamiz, masalan:
〈
𝑉, 𝐸〉 juftligi yoʻnaltirilmagan
G grafi deb nomlanadi, unda 𝑉 - uchlar toʻplami, 𝐸 -
qirralarning toʻplami,
𝑉
(2)
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.
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.
