6-ma’ruza. Graflar nazariyasi elementlari va o'tish algoritmlari

20-rasm. Regulyar graflar
Uchinchi darajali graflar kubik deb nomlanganiga e’tibor bering. –rasmdagi _{ } va –rasmdagi _{ }. Shubhasiz, d darajali regulyar grafdagi qirralarning soni _{ } ga teng. Bundan kelib chiqadiki, toq sonli uchlar uchun regulyar graf faqat juft darajaga, toq daraja uchun esa faqat uchlar soni boʻlishi mumkin. Shuning uchun har qanday kubik graf uchlarning juft soniga ega.

6.3. Grafni tasvirlash usullari

Grafni tasvirlash uchun bir nechta usullardan foydalaniladi. Graflardan oʻtish uchun siz oʻzingizning muammoingizni eng samarali hal qiladiganlardan foydalanishingiz kerak. Koʻpincha, tanlov qoʻshnilik matritsasi va qoʻshnilik roʻyxati oʻrtasida boʻladi (quyidagi jadval ikkala yondashuvning samaradorligini taqqoslaydi). Shu bilan birga, oʻrnatilgan C-massivga tayanib, oʻzingizning ma’lumotlar tuzilmalaringizni modellashtirishingiz va STD-da mavjud boʻlgan turli xil konteynerlardan foydalanishingiz mumkin.

Qoʻshnilik matritsasi. Qoʻshnilik matritsasini n-tartibli _{ } nosimmetrik kvadrat matritsa sifatida aniqlaymiz, unda _{ } elementlar 1 ga teng, agar grafda {_{ }} qirrasi boʻlsa, ya’ni _{ } va _{ } qoʻshni boʻlsa, 0 ga teng, agar bunday qirra mavjud boʻlmasa.
Ta’rifdan kelib chiqadiki, har qanday i uchun _{ }, har qanday j uchun _{ } va _{ }, ya’ni qoʻshnilik matritsasining har qanday qatori yoki ustunidagi birlar soni grafning tegishli vertikal darajasiga teng va ularning umumiy soni uning qirralarining ikki baravariga teng.
Misol sifatida –rasmda berilgan _{ } grafning A qoʻshnilik matritsasini _{ } darajalar ketma-ketligini yozamiz.



21-rasm. Grafni qo’shnilik matritsasi orqali tasvirlash

Graflarning ayrim turlarining qoʻshnilik matritsalarini qarab chiqaylik. Boʻsh graf _{ } qoʻshnilik matritsasi faqat nollardan iborat, ya’ni A (_{ }) = _{ }.

_{ } toʻliq grafning qoʻshnilik matritsasi faqat dioganal elementlari birlardan iborat, qolgan elementlari nolga teng boʻladi. Buni _{ } = _{ } - _{ } deb yozamiz. Agar graf bogʻlanmagan boʻlsa _{ } komponentlarga ega boʻlsa, unda satrlar va ustunlarni qayta tartibga solish orqali uning qoʻshnilik matritsasisini blok-diagonal shaklga keltirilishi mumkin:

Bu yerda har bir _{ } diagonal bloki _{ } komponentining qoʻshnilik matritsasi. _{ }-qismli graf holatida qoʻshnilik matritsasini blokli shaklga keltirish mumkin, agar asosiy diagonal boʻylab faqat "nol" bloklar kelsa:

Masalan, 22-rasmda _{ }, _{ }, _{ } boʻlaklar va unga qoʻshnilik matritsasi A boʻlgan uch qismli G graf koʻrsatilgan.