23. Graflar izomorfizmi

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: .