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. Gamilton grafi. Sodda zanjirlarni aniqlash
Yo'naltirilmagan G graf berilgan bo`lsin. Eyler sikli shunday siklki, unda grafning ma'lum bir uchidan chiqib, barcha qirralardan faqat bir marta o'tib, yana shu uchga qaytib kelishi kerak.
Grafda Eyler sikli mavjud bo`lishi uchun:
Graf bog`langan bo`lishi;
Grafning barcha uchlarining darajalari juft bo`lishi kerak; Grafda Eyler zanjiri mavjud bo`lishi uchun:
Graf boglangan bo`lishi;
Grafning 2 ta uchi darajalari toq bo`lib, qolgan barcha uchlarining darajalari juft bo`lishi kerak.
Grafning barcha qirralaridan bir martadan o`tgan zanjir
eyler zanjiri
deyiladi
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.
