23. Graflar izomorfizmi

23. Graflar izomorfizmi

Biz bilamizki ikki xil rasm bitta grafni tasvirlashi mumkin, masalan quyidagi rasmlar

grafni tasvirlaydi, bunda



grafni ko‘rib chiqaylik

H graf G grafdan farq qiladi. Masalan, uchga qo‘shni bo‘lgan uchlar bilan, G grafda va , H grafda esa va . Shuning uchun ham H graf G grafga teng emas. H grafni quyidagicha rasmda tasvirlash mumkin.

Ko‘rishimiz mumkinki, agar belgilashlarga e’tibor berilmasa, G va H graflarni bir xil rasmda tasvirlash mumkin. Bu esa, ushbu graflarning bittasi uchlarini shunday qayta belgilash mumkinki, graflar teng bo‘lib qoladi. Bunday graflar izomorf graflar deyiladi.