20-mavzu. O„rmon. Daraxtlarning xossalari. Daraxtlar haqidagi teoremalar. Rеja

^{bo„lsin deb faraz qilamiz. Endi uchlari soni} m  k 1 ^{va qirralari soni n bo„lgan}

daraxtni qaraymiz. Bu daraxtning ixtiyoriy qirrasini

(v₁, v₂ )
bilan belgilab, undan bu

qirrani olib tashlasak,

v₁ uchdan v₂
uchgacha marshruti (aniqrog„i, zanjiri) mavjud

bo„lmagan grafni hosil qilamiz, chunki agar hosil bo„lgan grafda bunday zanjir bor bo„lsa edi, u holda G daraxtda sikl topilar edi. Bunday bo„lishi esa mumkin emas.

Hosil bo„lgan graf ikkita

G₁ va G₂
bog„lamli komponentalardan iborat

bo„lib, bu komponentalarning har biri daraxtdir. Yana shuni ham e‟tiborga olish

kerakki, G₁ va G₂

^{daraxtlarning har biridagi uchlar soni} k ^{dan oshmaydi.}

Matematik induksiya usuliga ko„ra, bu daraxtlarning har birida qirralar soni

uning uchlari sonidan bitta kam bo„lishini ta‟kidlaymiz, ya‟ni ^G_i

graf

^(m_i ^{, n}_i ⁾ -graf

bo„lsa, quyidagi tengliklar o„rinlidir:

i  1, 2 ). Bu tengliklardan

n  n₁  n₂ 1 ,

k 1  m₁  m₂
va n_i  m_i 1 (

n  n₁  n₂ 1  m₁ 1 m₂ 11  (m₁  m₂ ) 1  (k 1) 1

bo„lishi kelib chiqadi. Demak,

m  k 1 ^{bo„lganda ham}

n  m 1 tenglik o„rinlidir.

Bu esa, matematik induksiya usuliga ko„ra, kerakli tasdiqning isbotlanganligini anglatadi.

Endi daraxtlar haqidagi asosiy teoremaning 2) tasdig„idan uning 3) tasdig„i kelib chiqishini isbotlaymiz. G graf asiklik, ya‟ni u siklga ega bo„lmagan graf va n  m 1 bo„lsin. G grafning bog„lamli bo„lishini isbotlash kerak.
Agar G graf bog„lamli bo„lmasa, u holda uni har bir bog„lamli

^{komponentasi siklsiz graf Gi (ya‟ni, daraxt) bo„lgan qandaydir} k ^{ta (} k 1^{) graflar}

k

diz‟yunktiv birlashmasi sifatida

G  _G_i

i 1
tenglik bilan ifodalash mumkin. Har bir

i  1, k
uchun G_i
graf daraxt bo„lgani uchun, yuqorida isbotlagan tasdiqqa ko„ra,

agar unda