Graflar uning turlari. Daraxtlar. Graflar va ularning turlari



Yüklə 0,76 Mb.
səhifə2/8
tarix08.05.2023
ölçüsü0,76 Mb.
#109282
1   2   3   4   5   6   7   8
37295 1Graflar maruza (1)

0 2 1 0 0
2 0 4 0 0
С= 1 4 0 0 1
0 0 0 0 0
0 0 1 0 0

0 4 0 1 1
4 0 0 0 2
С1= 0 0 0 0 0
1 0 0 0 0
1 2 0 0 0

Graf uchlarini turlicha nomerlash mumkindir. 2.6-rasmdagi grafni quyidagicha nomerlaymiz: masalan



Bunda ichki matritsa o’zgaradi. C va C1 matritsalarni solishtiramiz.
Graflar uchun uchlar soni va qirralar soni muhimdir hamda uchlar va qirralar “insindent” ekanligi ham.
Demak,
2.7rasmda G1 va G2 izomorf graflar jufti ko’rsatilgandir.

2.7-rasm


Ko’pincha masalalarda uchlar orasidagi munosabat muhim rol o’ynamaydi. Bunga misol tariqasida tartib munosabat bo’lishi mumkin. Masalan, dan katta bu holda dan katta bo’lishi mumkin emas. Demak, uchlar orasidagi munosabat ma'lum’mo’ljalga egadir. Bunday graflarni mo’ljalga ega graflar yoki orientirli graflar deymiz.

Ta’rif Orientirli D graf deb, bir juft D=(X,A) ga aytamiz. Bu yerda X uchlarning ixtiyoriy to’plami va A –uchlarning tartiblangan juftligini to’plamidir, uchlarning tartiblangan juftligini “yoylar” deymiz. juftlikda birinchi x yoy uchi, ikkinchi uch xj yoyning oxiridir. 2.8ramda yoylar strelka bilan bezatilgandir.


2.8-rasm


Ta’rif. Graf ning qisman grafi deb ataladi, agarda u berilgan grafning barcha uchlariga ega bo’lib, ammo barcha qirralariga ega bo’lmasa, balki qisman qirralariga ega bo’lsa, ya’ni
Ta’rif. ning graf ostisi deb shunday grafga aytiladiki, bunda ular qism bo’ladi,
2.9 rasmda qisman grafga, grafostiga va grafga misol keltirilgan.



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




  1. Yüklə 0,76 Mb.

    Dostları ilə paylaş:
1   2   3   4   5   6   7   8




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin