20-MAVZU. O„rmon. Daraxtlar. Daraxtlarning xossalari. Daraxtlar haqidagi
teoremalar.
|
Rеja:
O„rmon.
Daraxtlar.
Daraxtlarning xossalari.
Daraxtlar haqidagi teoremalar.
|
Tayanch ibоra va tushunchalar: Graf, uch, qirra, daraxt, o„rmon, asiklik graf,
marshrut, sikl, zanjir, oddiy zanjir, ko„prik, grafning sinch daraxti, grafning sinch o„rmoni, grafning siklomatik soni.
|
Daraxtlar(Trees)
A tree is a connected undirected graph with no simple circuits.
Alfred Joyce Kilmer (December 6, 1886 – July 30, 1918)graflarda daraxtlarni tuzilishi haqida aytib o`tgan.
Ta`rif. Yo`nalishga ega bo`lmagan
graf daraxt deyiladi, agar u bog`lamli va sikl bo`lmasa.
Quyidagi shakllardan o`ng tomondagi graf daraxtni tashkil qiladi. Chunki ixtiyoriy nuqtasidan ikkinchisiga o`tsa bo`ladi, chap tomondagi shaklda sikl bo`lgani uchun daraxt emas.
Forest is a graph with no simple circuits, which is not necessarily connected.
Agar bir nechta daraxtlar o`rmon deyiladi. Sikl bo`lmaydi, bog`lamlilik bo`lishi shart emas.
Every connected component of a forest is a tree.
