216 Bob IV. Graflar nazariyasi

Nazorat uchun savollar:
1. Siklik qirra nima?
2.  Atsiklik qirra nima?
3.  Siklomatik sonni formula orqali ifodalang.
4.  Qanday graf daraхt deb ataladi?
5.  Pog`ona uchlari deb nimaga aytiladi?
6.  Grafning asosi deb nimaga aytiladi?
7. Chekli grafda qirralar va uchlar soni orasidagi munosabatni keltiring.
8. Keli teoremasini ayting.
4.5. Daraxtlarlar 235
Mustaqil yechish uchun masalalar:
1. Chizmada keltirilgan grafning xromatik sonini toping:

2. Chizmada keltirilgan grafning xromatik sonini toping:

4.6. Qo`shnilik matritsasi
Faraz qilaylik, G graf yo`naltirilmagan bo`lsin. Grafning qo`shnilik matritsasida A_ij ning ustunlariga ham qatorlariga ham grafning uchlarini mos qo`yamiz. U holda
A<sub>ij</sub>=
qoidadan foydadanib qo`shnilik matritsasini hosil qilamiz.
236 Bob IV. Graflar nazariyasi
Misol.
Rasmda keltirilgan yo`naltirilmagan graf uchun qo`shnilik matritsasi quyidagicha bo`ladi.

G yo`naltirilgan graf bo`lsin. U holda qo`shnilik matritsasi A<sub>ij</sub> ning ustunlariga ham satrlariga ham grafning uchlarini mos qo`yamiz. U holda quyidagi qoidadan foydadanib qo`shnilik matritsasini hosil qilamiz.
A<sub>ij</sub>= 
4.6. Qo`shnilik matritsasi  237
Qo`shnilik matritsasining diagonalida turgan birlar grafning ilmoqlariga mos keladi.
Izolyatsiyalangan uchga nollardan tashkil topgan satr va ustun mos keladi.
Qo`shnilik matritsasidagi birlar soni grafdagi qirralar soniga teng.