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.

Izomorf graflarning ayrim invariantlari.:

1. uchlar soni;

2. qirralar soni;

3. uchlar darajalari ketma-ketligi;

4. qo‘shni uchlar darajalari;

5. bog‘liqlik;

6. k uzunlikdagi oddiy sikllar soni;

7. Eyler sikli;

8. Gamilton sikl.

Kvadrat matrisada qatorlarni o‘rin almashtirish deganda, matrisa qatorlari o‘rin almashinuvi bilan matrisa xuddi shunday ustunlarini o‘rin almashinuvi birlashuvi tushuniladi. Qo‘shnilik matrisasidagi qatorlar o‘rin almashinuvi, graflar uchlarining qayta nomerlanishiga mos keladi. Shuning uchun ham, agar biror bir graf qo‘shnilik matrisasi qatorlarining o‘rin almashinuvi orqali ikkinchi grafning qo‘shnilik matrisasiga kelinsa, bunday graflar izomorf bo‘ladi.

n ta uchli to‘liq graf qirraga ega bo‘ladi. Ushbu uchlardagi har qanday oddiy graf berilgan to‘liq grafning grafosti bo‘ladi. To‘liq grafning qirralarini 1 dan gacha nomerlab chiqsak, u holda har qanday grafostiga razryadli ikkilik kod mos qo‘yish mumkin. Har bir razryad aniq bir qirraga mos keladi. Agar razryad 1 ga teng bo‘lsa, u holda grafosti ushbu qirrani o‘z ichiga oladi, agar 0 bo‘lsa – o‘z ichiga olmaydi. Bundan kelib chiqadiki, berilgan n ta uchdagi oddiy graflar soni razryadli ikkilik kodlar soniga teng bo‘ladi, ya’ni . Masalan n=3 bo‘lganda 8 ta grafga ega bo‘lamiz.



Ushbu graflar ichida izomorflari mavjud: va . Bundan kelib chiqadiki 3 ta uchda 4 ta juft-jufti bilan izomorf bo‘lmagan oddiy graflar mavjud: .