Navzu: Bog`langan graflar. Marshrut, zanjir, sikllar. Eyler va




Download 132,99 Kb.
bet1/3
Sana08.02.2024
Hajmi132,99 Kb.
#153003
  1   2   3
Bog'liq
graflar

22-23-navzu: Bog`langan graflar. Marshrut, zanjir, sikllar. Eyler va


Gamilton graflari

Bog`langan graflar. Marshrut, zanjir, sikllar


Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf bog‘langan graf deb ataladi.


Agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo`lsa, u holda bu ikkita uch bog‘langan deyiladi. Bunday uchlar to‘plami grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. Uchlar to‘plami bo‘yicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni bog‘lamlilik komponentlari deb ataluvchi bog‘lamli qismlarning birlashmasi deb qarash mumkin.

Tekis
G  (V ,U )
graf uchun
m r 1 n k
tenglik o`rinlidir, bunda
m V ,

n U , r yoqlar soni, k bog‘lamlilik komponentalar soni.


n uzunlikdagi marshrut deb n ta qirraning bo`sh bo`lmagan ketma-ketligiga aytiladi. Qo`shni yoylar ketma-ketligi yo`l, qo`shni qirralar ketma-ketligi zanjir deyiladi. Boshqacha ta’riflansa, takroriy qirralarga ega bo`lmagan marshrut zanjir deyiladi. Yopiq zanjir esa sikl deyiladi.
Teorema. Agar grafdagi har bir uchning lokal
darajasi ikkidan kichik bo‘lmasa, u holda bu
graf siklga ega.
Yoylarning oriyentatsiyalari hisobga olingan yoylar va uchlar ketma-ketligi
oriyentirlangan marshrut deb ataladi.
Oriyentirlangan marshrut uchun zanjir tushunchasiga o‘xshash yo‘l (yoki

Download 132,99 Kb.
  1   2   3




Download 132,99 Kb.

Bosh sahifa
Aloqalar

    Bosh sahifa



Navzu: Bog`langan graflar. Marshrut, zanjir, sikllar. Eyler va

Download 132,99 Kb.