216 Bob IV. Graflar nazariyasi

Teorema 2. Oriyentirlanmagan graf A va V uchlarni birlashtiruvchi eyler zanjiriga ega bo`ladi, faqat va faqat shu holdaki, agar graf bog`liq bo`lsa hamda faqatgina A va V uchlar toq darajalarga, qolgan uchlar juft darajalarga ega bo`lsa.
4.3. Graf uchlari darajasi. Graf qirralari soni 225
Ta’rif 5. Grafni tekislikka yotqizish mumkin bo`lsa, bunday graf planar graf deyiladi. Tekislikka yotqizilgan graf tekis graf deyiladi.

G₁ graf planar va G₂ tekis grafga izomorf.
Teorema 3. Agar grafda karrali qirralari hamda ilmoq mavjud bo`lmasa, n ta uchga ega bo`lgan va bog`liq komponentasi K ga teng bo`lgan grafning qirralari soni eng ko`pi bilan aniqlanadi.
M=
Mashrutning uzunligi deb, shu marshrutda mavjud qo`shni (e_i-1, e_i) qirralar soniga aytiladi.
Grafning iхtiyoriy a va iхtiyoriy v uchlari orasidagi masofa deb, shu uchlarni bog`lovchi eng kichik uzunlikka ega bo`lgan zanjirga aytiladi.
Misol 1.
226 Bob IV. Graflar nazariyasi
d(a₁,a₃)= (e₀, e₁)=2;
d(a₁,a₄)=(e₀, e₂)=2;
d(a₁,a₄)=(e₀, e₁, e₃)=3
Grafning diametri deb, uchlari orasidagi eng katta uzunlikka ega bo`lgan masofaga aytiladi.

Misol 2. d(a₁,a₄)=(e₀, e₁, e₃)=3.
S uch G grafning fiksirlangan uchi bo`lsin. Х esa grafning iхtiyoriy uchi bo`lsin. S uch uchun maksimal masofani hisoblaymiz. Qandaydir S₀ uch uchun bu maksimal masofa boshqa uchlarga nisbatan minimal bo`lsa, u holda S₀  G grafning markazi deyiladi va S₀ uchun aniqlangan masofa G grafning radiusi deyiladi.