• 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
oriyentirlangan zanjir) tushunchasini ham kiritish mumkin. Boshlang‘ich va
oxirgi uchlari ustma-ust tushadigan oriyentirlangan zanjir
kontur deb ataladi.
• Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy
ikkita uchlari bog‘langan graf
bog‘lamli graf deb
ataladi.
• Agar grafdagi ikkita uchni biror oddiy zanjir bilan
tutashtirish mumkin bo‘lsa, u holda bu ikkita uch
ekvivalent (
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
komponentalari (qisqacha,
komponentalari)
deb ataluvchi bog‘lamli qismlarning birlashmasi
deb qarash mumkin. Bu yerda berilgan graf
bog‘lamlilik komponentalariga bo‘laklandi
(ajratildi) deb aytish mumkin
• Eyler grafi: Bizga yo'naltirilmagan G graf berilgan
bo'lsin. Eyler tsikli shunday tsiklki, unda grafning
ma'lum bir tugunidan chiqib, barcha qirralardan faqat
bir marta o'tib, yana shu tugunga qaytib kelishi kerak.
•
Grafda Eyler tsikli mavjud bulishi uchun:
• a) Graf bog`langan bo'lishi;
• b) Grafning barcha tugunlarining lokal darajalari juft
• bo`lishi kerak;
•
Grafda Eyler zanjiri mavjud bo`lishi uchun:
• Graf boglangan bo'lishi;
• b) Grafning 2 ta tuguni(boshlanish va oxirgi) lokal
darajalari tos bo`lib, solgan barcha tugunlarining lokal
darajalari juft bo`lishi kerak.
•
Agar G yo'naltirilmagan grafda Eyler tsikli
mavjud bo'lsa, bunday grafga Eyler grafi deyiladi.
• Gamilton grafi. Agar grafda oddiy cikl mavjud
bo'lib, bu ciklda grafning barcha tugunlari
qatnashsa, bunday tsikl Gamilьton tsikli
deyiladi.
• Oddiy zanjir Gamilton zanjiri deyiladi, agar
bunday grafda tugunlarning hammasi ishtirok
etsa. Tugun va qirralar takrorlanmasligi kerak.
•
Grafda Gamilьton tsikli mavjud bo'lsa, bu
graf Gamilьton grafi deyiladi.
