23. Graflar izomorfizmi

Ta’rif. Agar shunday va biyeksiyalar mavjud bo‘lsaki, ixtiyoriy qirra uchun tenglik o‘rinli bo‘lsa, va graflar izomorf deyiladi, Izomorf graflar kabi belgilanadi.

Agar graf oddiy bo‘lsa, graflar izomorfizmining teng kuchli boshqa ta’rifini berish mumkin.

Ta’rif. Agar shunday biyeksiya mavjud bo‘lsaki, bo‘ladi faqat va faqat bo‘lgandagina bo‘lsa, u holda ikkita oddiy graf va lar izomorf graflar deyiladi.

Graflarning izomorfligini tekshirish uchun, ta’rifda keltirilgan biyeksiyalar qurilishi kerak. Bilamizki, agar bo‘lsa, u holda ta biyektiv funksiyalar mavjud. Agar graflar izomorf bo‘lsa, u holda bir nechta urinishlardan so‘ng kerakli biyektiv funksiyani topish mumkin. Lekin, graflarning izomorf emasligini isbotlash uchun barcha ta biyektiv funksiyalarni tekshirgandan keyingina gapirish mumkin bo‘ladi. Afsuski hozirgacha graflar izomorf emasligini isbotlashning yanada samarali umumiy usullari noma’lum.

Ayrim hollarda graflarning izomorf emasligini bir nechta oddiy testlar orqali topish mumkin. Ushbu testlar barcha izomorf graflar uchun umumiy bo‘lgan xossalarga asoslangan. Masalan, graflar izomorf bo‘lsa, ular bir xil sondagi uchlarga ega. Barcha izomorf graflar uchun umumiy bo‘lgan xossalarga invariantlar deyiladi.