Axborotlarga ishlov berish va boshqarish” kafedrasi tizimlarnazari ya s I fanidan Sirtqi ta’lim yo‘nalishi uchun Ma’ruza matni 5330200-«Informatika va axborot texnologiyalari»

3.1.1-misol:
Agar va bo`lsin, u holda va to`plam grafni hosil qiladi.
G rafning uchlarini tugunlar, 2 ta uchini birlashtiruvchi chiziqni yoylar deb ataymiz.

3.1.1-rasm. Graf.

Grafning ikkita tuguni umumiy yoy bilan o`zaro bog`langan bo`lsa, ular qo`shni tugunlar deyiladi.
A gar ning 2 ta yoyi umumiy tugunga ega bo`lsa, ular qo`shma yoylar deyiladi.

3.1.2-rasm. Qo`shma yoyli graf.

Bu erda yoy yoyga qo`shma, chunki umumiy tugunga ega.
B irorta tugunni o`zini - o`ziga bog`laydigan yoyga halqa deyiladi.
3.1.3-rasm. Halqa.

Agar tugun hech qanday yoyga insedent bo`lmasa, u holda bu tugun izolyatsiyalangan tugun deyiladi. Faqat izolyatsiyalangan tugunlardan iborat graflar 0 graflar yoki bo`sh to`plamlar deyiladi va G₀ bilan belgilanadi.

3.1.4-rasm. Nol` (bo`sh) graf.

Agar grafning barcha tugunlari o`zaro bog`langan bo`lsa, bunday graf to`liq graf deyiladi.

3.1.5-rasm. To`liq graf.

Agar grafning barcha qirralarida yo`nalish ko`rsatilgan bo`lsa bunday graf yo`naltirigan graf deyiladi.

3.1.6-rasm. Yo`naltirilgan graf.

Agar grafning qirralarida yo`naltirish ko`rsatilmagan bo`lsa, u holda graf yo`naltirilmagan graf deyiladi.

3.1.7-rasm. Yo`naltirilmagan graf.

Agar ning tugunlari to`plami ga tegishli, ya`ni bo`lsa, hamda ning barcha qirralari ning ham qirralari bo`lsa, ya`ni , u holda graf grafning qismi deyiladi.

3.1.8-rasm. Qism graf.

Agarda ning barcha tugunlari grafga tegishli bo`lib, birorta ham yoyi ga tegishli bo`lmasa. graf grafning to`ldiruvchisi deyiladi.

3.1.9-rasm. To`ldiruvchi graf.

A gar 2 ta yoy umumiy tugunga ega bo`lsa ular bir biriga aloqador (smejniy) deyiladi.(3.1.10-rasm)

3.1.10-rasm. Graf.

Agar X tugun U yoyning boshi yoki oxiri bo`lsa, u holda shu yoy uchi X tugun insedenti deyiladi. O`z navbatida tugun uchun yoy ham insedent hisoblanadi.

X tugunga insedent bo`lgan yoylar soni shu tugunning darajasini bildiradi va bilan belgilanadi.
Masalan: 3.1.10-rasmdan qarasak, <sub>, ,</sub>
Agar graf tugunlarning barchasi bir xil darajaga ega bo`lsa, bunday graflar bir jinsli graf deyiladi.
Masalan:

3.1.11-rasm.Bir jinsli graf.

tugun darajalari ikkiga bo`linadi va ular tugunga kirish yarim darajasi, hamda tugundan chiqish yarim darajasidan iboratdir. Tugundan chiqish yarim darajasi deb shunday qiymatga aytiladiki, bu qiymat ushbu tugundan chiqib ketayotgan yoylar soniga tengdir. Tugunga kirish yarim darajasi deb shunday qiymatga aytiladiki, bu qiymat ushbu tugunga kirib ketayotgan yoylar soniga tengdir.
(3.1)