Graflarni bo'yash. Graf xromatik sinfi va xromatik soni. Bixromatik graflar

- **Misol 2(Graflar Izomorfligi):** Ikki grafi G1 va G2 o'zaro izomorfizmga ega bo'lsa, ularning tushunchalari va bog'lanishlari bir-biriga mos keladi. Ya'ni, G1 va G2 ikkala grafning yo'nalishlari va aloqalari bir-biriga amos keladi.

• - **Misol 2(Graflar Izomorfligi):** Ikki grafi G1 va G2 o'zaro izomorfizmga ega bo'lsa, ularning tushunchalari va bog'lanishlari bir-biriga mos keladi. Ya'ni, G1 va G2 ikkala grafning yo'nalishlari va aloqalari bir-biriga amos keladi.
• Ushbu ma'lumotlar graf teoriyasi haqida asosiy tushunchalar va masalalar bilan bog'liqdir. Izomorfizmni aniqlash va graf tushunchalarini o'rganish uchun ko'p qiziqarli amaliyotlar va algoritmalar mavjud.

Planar graflar. Pontryagin-Kuratovskiy teoremasi

• Planar graflar. Pontryagin-Kuratovskiy teoremasi
• Planar grafik bo'lgan grafik nazariyasi bir grafik bir-biriga sodir qirralarning har qanday holda tekisligida chizilgan mumkin. Planar bo'lmagan grafikni bunday usulda chizish mumkin emas. A tekislik grafik bir emas samolyot grafik tekislikda chiziladi. Tekis grafikni chorak burchakdan ikki o'lchovli fazodagi nuqtagacha va har bir chetidan tekislik egri chizig'igacha bo'lgan tasvirga ega tekis grafik sifatida belgilash mumkin , shunda har bir egri chiziqning so'nggi nuqtasi oxiri pozitsiyalariga mos keladi.

Grafning har bir qirrasidan faqat bir marta o'tadigan zanjir Eyler zanjiri, deb ataladi. Yopiq Eyler zanjiriga (ya'ni Eyler sik~ liga) ega graf Eyler graft, deb ataladi. Agar grafda yopiq bo'lmagan Eyler zanjiri topilsa, u holda bunday graf yarim Eyler graft, deb ataladi. 1-teorema. Bog'lamli graf Eyler graft bo'lishi uchun undagi barcha uchlarning darajalari juft bo 'lishi zarur va yetarlidir. Isboti.Zarurligi.G Eyler grafida C—Eyler sikli bo'lsin.

Grafning har bir qirrasidan faqat bir marta o'tadigan zanjir Eyler zanjiri, deb ataladi. Yopiq Eyler zanjiriga (ya'ni Eyler sik~ liga) ega graf Eyler graft, deb ataladi. Agar grafda yopiq bo'lmagan Eyler zanjiri topilsa, u holda bunday graf yarim Eyler graft, deb ataladi. 1-teorema. Bog'lamli graf Eyler graft bo'lishi uchun undagi barcha uchlarning darajalari juft bo 'lishi zarur va yetarlidir. Isboti.Zarurligi.G Eyler grafida C—Eyler sikli bo'lsin.