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

Grafik turlari

Grafik G=(V,E) oddiy deyiladi , agar u pastadir va parallel qirralarni o'z ichiga olmasa.

Grafik G=(V,E) oddiy bo'lsa va har bir juft cho'qqi qo'shni bo'lsa, to'liq deyiladi .

Grafik turlari

Null grafik - chekkalari to'plami bo'sh bo'lgan grafik.
Hisob G bir nechta qirralari bilan multigraf deb ataladi .

Grafik turlari

Hisob G ilmoqlar va bir nechta qirralar bilan psevdograf deb ataladi .

Daraxtlar deb ataladigan bog'langan asiklik grafiklar alohida qiziqish uyg'otadi. P cho'qqilar to'plamidagi daraxt har doim q=p-1 qirralarni o'z ichiga oladi, ya'ni. grafik ulanishi uchun zarur bo'lgan minimal qirralarning soni. Daraxtga chekka qo'shilsa, tsikl hosil bo'ladi va kamida bitta chekka olib tashlanganida, daraxt tarkibiy qismlarga bo'linadi, ularning har biri ham daraxt yoki izolyatsiya qilingan cho'qqi hisoblanadi. Komponentlari daraxtlar bo'lgan bog'lanmagan grafik o'rmon deyiladi.

Daraxtlar deb ataladigan bog'langan asiklik grafiklar alohida qiziqish uyg'otadi. P cho'qqilar to'plamidagi daraxt har doim q=p-1 qirralarni o'z ichiga oladi, ya'ni. grafik ulanishi uchun zarur bo'lgan minimal qirralarning soni. Daraxtga chekka qo'shilsa, tsikl hosil bo'ladi va kamida bitta chekka olib tashlanganida, daraxt tarkibiy qismlarga bo'linadi, ularning har biri ham daraxt yoki izolyatsiya qilingan cho'qqi hisoblanadi. Komponentlari daraxtlar bo'lgan bog'lanmagan grafik o'rmon deyiladi.

Grafik turlari

Amalda daraxtlar va pratrelar kabi grafik turlari keng qo'llaniladi.

Amalda daraxtlar va pratrelar kabi grafik turlari keng qo'llaniladi.

Daraxt - bu kamida ikkita cho'qqidan iborat bo'lgan va tsikllarni o'z ichiga olmaydigan chekli bog'langan yo'naltirilmagan grafik. Bunday grafikda ilmoqlar yoki bir nechta qirralar yo'q.