Graflar uning turlari. Daraxtlar. Graflar va ularning turlari

Daraxtlar

Ta’rif. Siklga ega bo’lmagan bog’langan graf daraxt deb ataladi, uning qirralari esa shoxlaridir.
n-uchli daraxtda (n-1) ta qirra border. (2.14-a rasm) Haqiqatdan ham, agarda daraxtning ikki uchuni birlashtiruvchi bitta qirra qo’shilsaa, grafda sikl paydo bo’ladi.(2.14-b rasm). Agar bir qovurg’ani olib tashlasa, graf bog’lanmagan bo’lib qoladi. (2.14-v rasm).

2.14-rasm
Shunday qilib n uchni birlashtirish uchun (n-1) ta qovurg’a kerakdir.
Siklsiz bog’lanmagan graf o’rmon deb ataladi. Bunda o’rmonning har qanday bog’langan qismi daraja bo’ladi. (2.15rasm). Orientirli daraxt Y “predaraxt” deyiladi, agarda Y uchlari orasida doimo yo’l bo’lsa.(2.16rasm)
2.15-rasm

S=(G, C) juftlik to’r deb ataladi, Bu yerda G=(X,A) ixtiyoriy orientirlangan (yo’naltirilgan)dir.

C esa grafning har bir yoyiga manfiy bo’lmagan haqiqiy sonni moslaydi.
C(d_i d_j ) buni yechilayotgan masala shartiga ko’ra turlicha atashadi: yoy og’irligi, o’tkazish qobiliyati. “To’r” deb bir xilda o’lchangan grafni atashadi, yoylarni yig’indisini graf og’irligi deyiladi.
“mo’ljallanmagan”, “orientirlanmagan”, “yo’naltirilmagan” graf berilgan bo’lsin.
D(Y,J) daraxt grafning qoplovchi daraxti deyiladi, agarda X=Y va J Ening qismi bo’lsa.
Shunday qilib qoplovchi daraxt berilgan grafning barcha uchlarini bog’laydi, ammo barcha qovurg’alarini o’z ichiga olmaydi. (2.17-a rasm) berilgan grafga (2.17-b) qoplovchi daraxt ko’rsatilgandir. Har qanday bog’langan graf kamida bir qoplovchi daraxtga egadir.

2.17-rasm

Example 10.1.2 Drawing More Than One Picture for a Graph Consider the graph specified as follows: vertexset ={ v1,v2,v3,v4} edge set ={ e1,e2,e3,e4} edge-endpoint function:³

Berilgan masalada grafni chizing

Quyidagi rasmlarning bir xil ekanligini ko’rsating

Quyidagi graflarning qaysi biri bog’langan.

Graflar izomorfmi?

GLOSSARIY