Termiz davlat universiteti pedagogika fakulte

Graf marshruti (yo’li)

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

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 graflarning qaysi biri bog’langan.

Quyidagi rasmlarning bir xil ekanligini ko’rsating

Graflar izomorfmi?