25-Graflarni bo‘yash

Grafda barqaror to‘plamlar

Barqaror to‘plamlar va ular bilan bog‘liq bo‘lgan sonli xarakteristikalar, grafning muhim tarkibiy xossalarini ifodalaydi. Tashqi va ichki barqaror to‘plamlarni farqlashadi.

Ta’rif. Graf uchlarining A to‘plamostisiga tegshli ixtiyoriy ikkita uch qo‘shni bo‘lmasa, bunday to‘plamosti ichki barqaror deyiladi. Agar ushbu xossani buzmasdan birorta ham uch bilan to‘ldirishni iloji bo‘lmasa, bu to‘plam ichki barqarorlik xossasiga nisbatan maksimal deyiladi.

Grafning quvvati bo‘yicha maksimal sondagi elementlarga ega bo‘lgan ichki barqaror to‘plamining elementlar soniga ichki barqarorlik soni deyiladi va quyidagicha belgilanadi

Bunda – G grafning ichki barqaror to‘plamostilar to‘plami.

Ta’rif. Agar grafning ixtiyoriy uchi uchun grafning B to‘plamostisida uning qo‘shnisi bo‘lsa, B to‘plamostiga tashqi barqaror deyiladi. Agar boshqa birorta ham tashqi barqaror to‘plamga ega bo‘lmasa, bu to‘plam minimal deyiladi,

Quvvati bo‘yicha minimal bo‘lgan tashqi barqaror to‘plamning elementlar soniga, tashqi barqarorlik soni deyiladi va quyidagicha belgilanadi

bunda – G grafning barcha tashqi barqaror to‘plamostilar to‘plami.

Ko‘rinib turibtiki, ichki barqaror to‘plam maksimal bo‘ladi, faqat va faqat qachonki u tashqi barqaror bo‘lsa. Lekin, tashqi barqaror to‘plam har doim ham ichki barqaror to‘plam bo‘lavermaydi.

Ta’rif. Graf uchlar to‘plamining to‘plamostisi bir vaqtnin o‘zida maksimal ichki barqaror va minimal tashqi barqaror bo‘lsa, bunday to‘plamostiga grafning yadrosi deyiladi.

Mashqlar

1. Rasmda tasvirlangan graflar uchun, barcha maksimal ichki barqaror to‘plamlarni sanab o‘ting va grafning ichki barqarorlik soni topilsin.

a) b) c)

2. Rasmda tasvirlangan graflar uchun, barcha minimal tashqi barqaror to‘plamlarni sanab o‘ting va grafning tashqi barqarorlik soni topilsin.

a) b) c)

3. Ichki barqaror bo‘lmagan, quvvati bo‘yicha eng kichik bo‘lgan tashqi barqaror to‘plamga misol keltiring.

4. Grafning barcha yadrolarini sanab o‘ting.

a) b) c)