2. Элементы теории множеств

Zanjirning oxirgi uchlari boshqacha bo'lsa, oddiy deyiladi ( v 1 , e 1 , v 2 , e 2 , v 3 , e 8 , v 6 , e 11 , v 3 ).

zanjirning oxirgi uchlari (v 1 ,e 1 ,v 2 ,e 2 ,v 3 ,e 7 , v 5 ,e 3 ,v 2 ,e 4 ,v 4 , e 5 , v 1 ) mos kelsa zanjir yopiq deb ataladi . .

G

yo'l, halqa

agar uning barcha uchlari har xil bo'lsa ( v 1 , e 1 , v 2 , e 2 , v 3 ) yo'l deyiladi .

Tsikl yopiq sxema ( agar sxema oddiy bo'lsa oddiy sikl) ( v 1 , e 1 ,v 2 ,e 3 ,v 5 ,e 6 ,v 4 ,e 5 ,v 1 ) .

Yo'ldagi qirralarning soni deyiladi yo'l uzunligi . Tsikl uzunligi ham xuddi shunday tarzda aniqlanadi .

G

Yo'llar va halqalarning xossalari

1. Yo'lning har bir terminal bo'lmagan cho'qqisining darajasi 2 ga, terminal cho'qqilari 1 ga teng darajaga ega.

2. Har bir tsikl cho'qqisi 2 daraja yoki boshqa tekis darajaga ega. Ushbu bayonotning teskari o'zgarishi, ya'ni har bir tepasi teng darajaga ega bo'lgan pastki grafikning qirralari tsiklni tashkil qiladi, degani noto'g'ri.

3. Yo'ldagi cho'qqilar soni qirralarning sonidan bitta kattaroqdir, tsiklda esa qirralarning soni cho'qqilar soniga teng.

Grafiklarning ulanishi, ulanish komponenti

Ikki burchak v i va v j grafigda V i — v j yo'li mavjud bo'lsa, G grafikda bog'langan deyiladi . Yuqori qismi o'zi bilan bog'langan.

Grafik har bir juft cho'qqi o'rtasida yo'l bo'lsa, ulangan deb ataladi.

Komponent ulanish - grafikdagi maksimal bog'langan pastki grafik.

G
1 komponent ulanish : {v 1 , v 2 , v 3 , e 1 , e 2 , e 3 }
2 ta ulanish komponentlari : {v 4 , v 5 , v 6 , e 4 , e 5 , e 6 }
3 ta ulanish komponentlari : {v 7 , v 8 , e 7 }
4 ta ulanish komponentlari: { v9 }