Shunday qilib n uchni birlashtirish uchun (n-1) ta qovurg’a kerakdir

1 amaliy mashg’ulot.Graflar nazariyasiga kirish. Tushuncha va ta’riflar. Juftlashtirish. Daraxtlar

Bizga orientirlanmagan graf berilgan bo’lsin, m uzunlikdagi marshrut deb grafning qirralarini shunday ketma ketligiga aytiladiki yonma-yon bo’lgan qirralarini uchlari uchma-uch tushishlari kerak. Graflarning marshrutiga misol sifatida quyidagi ketma-ketlik bo’lishi mumkin.

va . Birinchi marshrut lar orqali o’tadi. Ikkinchi marshrut lar orqali o’tadi va yopiq marshrut tashkil qiladi.Grafning ikki uchi bog’langan deyiladi, agar shu uchlarni birlashtiruvchi yo’l bo’lsa. Agar grafning har qanday uchini birlashtiruvchi marshrut mavjud bo’lsa, bunday graf bog’langan graf deyiladi. 2.6 rasmdagi grаf bog’langan bo’lmaydi. Chunki rasmda marshrut yo’q.

Barcha qirralari turli bo’lgan (yo’l) marshrut zanjir deb ataladi. Agar zanjir turli uchlardan o’tsa, u oddiy zanjir deb ataladi. Yopiq zanjir “sikl” deb ataladi, turli uchlardan o’tuvchi “sikl”, oddiy “sikl”dir.

Grafning barcha qirralarini o’zida mujassam qilgan sikl Eylerov deyiladi, Eylerov siklga ega graf Eylerov grafi deyiladi.

2.10-rasm

1. 
   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?

1^ Susanna S. Epp. Discrete Mathematics with Applications, Fourth Edition. Printed in Canada 2011p.p.627