9-mavzu: Graflar nazariyasining asosiy tushunchalari. Graflarning ba’zi turlari. Graflarning berilish usullari. Qo`shnilik va insidentlik matritsalari. Graflarning izomorfligi. Qoshnilik. Insidentlik. Uchning darajasi

Graflarning berilish usullari. Qo`shnilik va insidentlik matritsalari. Graflarning izomorfligi.

Qoshnilik. Insidentlik. Uchning darajasi
G grafning V- uchlar to’plamidan olingan v_i€V va v_j€V uchlar qirra bilan birlashtirilgan bo`lsa, bunday uchlar qo`shni uchlar deyiladi.

Masalan : 7- rasmda 3 va 4, 3 va 6, 4 va 6 va boshqalar qo`shni uchlar bo`ladi.

2 ta qirra qo`shni deyiladi agar ular umumiy uchga ega bo`lsa.

7- rasmda qo`shni qirralar {3,4}, {3,6}, {4,5}, {2,5} va boshqalar.

Agar uch biror qirraning oxiri bo`lsa shu uch va qirra insident deyiladi.

7- rasmda {3,4} qirra 3 uchga insident bu qirra 4- uchga ham insident.

Berilgan uchga insident bo`lgan qirralar soni shu uchning darajasi deyiladi.

Masalan, 7- rasmdagi grafda 3 uchning darajasi 2 ga 4- ucning darajasi 3 ga teng.

Yakkalangan uchning darajasi 1 ga teng.

Grafning barcha uchlari darajalari yig`indisi juft son bo`lib, bu sonning yarmi grafning qirralari soniga teng (bu xossa barch graflar uchun o`rinli).

Masalan:

9- rasm
9-rasmdagi grafning uchlari darajalari yig`indisi

ρ(1)+ρ(2)+ρ(3)+…..ρ(7) = 0+2+2+3+2+3+0 = 12 ga teng.

Agar uchning darajasi juft bo`lsa, u juft, darajasi toq bo`lsa, u toq uch deyiladi.

Har qanday grafda toq uchlar soni juft bo`ladi. Graflarda juft uchlar soni juft bo`lishi ham, toq bo`lishi ham mumkin.