23. Graflar izomorfizmi

Mashqlar

1. Quyidagi ikkita oddiy graflar o‘rtasida izomorfizm qurilib, ular izomorf ekanligi isbotlansin

2. Quyidagi ikkita graf o‘rtasida izomorfizm qurilib, ular izomorf ekanligi isbotlansin

3. Agar ikkita graf uchlar darajalari ketma-ketligi ustma-ust tushsa, ularni izomorf deyish mumkinmi? Misol keltiring.

4. Quyidagi graflar izomorfmi?

5. Quyidagi graflar izomorfmi?

6. Quyidagi graflar izomorfmi?

7. Quyidagi graflar izomorfmi?

8. Quyidagi graflar izomorfligi isbotlansin.

9. Berilgan 4 ta uchda nechta nechta oddiy graf mavjud?

10. 4 ta uchda 11 ta izomorf bo‘lmagan oddiy graflar mavjud. Grafda

a) qirralar bo‘lmaganda; b) 1 ta qirra; c) 2 ta qirra; d) 3 ta qirra; e) 4 ta qirra; f) 5 ta qirra; g) 6 ta qirra bo‘lgan hollarda, ularni rasmlarda tasvirlang.

11. Uchta uch va ikkitadan ortiq bo‘lmagan qirraga ega bo‘lgan barcha izomorf bo‘lmagan graflarni tasvirlang.

12. To‘rtta uchda barcha ikkinchi darajali izomorf bo‘lmagan regulyar graflarni tasvirlang.

13. Oddiy graflarning izomorfizmi ekvivalentlik munosabati ekanligi isbotlansin.

14. Agar ikkita oddiy graf izomorf bo‘lsa, ularning to‘ldiruvchilari ham izomorfligi isbotlansin.

15. Ikki ulushli grafga izomorf bo‘lgan grafning o‘zi ham ikki ulushli bo‘lishi isbotlansin. Ya’ni grafning ikki ulushliligi izomorf graflarning invarianti hisoblanadi.

16. Izomorfizm graf sikllarini saqlashi isbotlansin.

17. Ikkita grafning qo‘shnilik matrisasi berilgan. Izomorf graflarning invariantlaridan foydalanib, graflarni izomorf emasligi isbotlansin.

,

18. Ikkita grafning qo‘shnilik matrisasi berilgan. Izomorf graflarning invariantlaridan foydalanib, graflarni izomorf emasligi isbotlansin.

,

19. Ikkita grafning qo‘shnilik matrisasi berilgan. Bitta matrisa qatorlarini o‘rin almashtirish hisobiga ikkinchisiga olib kelib, ushbu graflarning izomorfligi isbotlansin.

,

20. Ikkita grafning qo‘shnilik matrisasi berilgan. Bitta matrisa qatorlarini o‘rin almashtirish hisobiga ikkinchisiga olib kelib, ushbu graflarning izomorfligi isbotlansin.

,

21. Ikkita izomorf graflarning qo‘shnilik matrisalari berilgan. Graflarni rasmda tasvirlab, bitta matrisani ikkinchisiga olib keladigan qator o‘rin almashtirishini amalga oshiring.

,

22. Ikkita izomorf graflarning qo‘shnilik matrisalari berilgan. Graflarni rasmda tasvirlab, bitta matrisani ikkinchisiga olib keladigan qator o‘rin almashtirishini amalga oshiring.

,

23. Kvadrat matrisa yoyiladigan deyiladi, agar qatorlarni o‘rin almashtirish hisobiga ko‘rinishga olib kelishni imkoni bo‘lsa. Bunda A va B kvadrat matrisalar, O matrisaning barcha elementlari nolga teng. Quyidagi matrisalar yoyiladigan ekanligi isbotlansin.

1) , 2)

Ko‘rsatma. Har qanday matrisa biror bir grafning qo‘shnilik matrisasi bo‘ladi. Ushbu graflarni rasmda tasvirlang.