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.6. Mezon formulasi yordamida ikki tugun orasidagi uzatishlarni hisoblash.
Graflardagi ixtiyoriy va tugunlar orasidagi uzatish quyidagi Mezon formulasi yordamida aniqlanadi.


(3.6.1)

Bu erda:

– -tugun bilan -orasidagi umumiy uzatish funksiyasi;
– - tugundan -tugungacha bo`lgan yo`l;
– yo`llar soni;
– konturlar soni;
- - tugun bilan - tugun orasidagi kontur;
*1 – agar qavslar ochilganda konturlar ko`paytmasi o`zaro bir-biriga tegishli bo`lsa ushbu ko`paytmani tashlab yuborish kerakligini bildiradi.
*2 – agar qavslar ochilganda yo`llar hamda konturlar ko`paytmasi o`zaro bir-biriga tegishli bo`lsa ushbu ko`paytmani tashlab yuborish kerakligini bildiradi.
Mezon formulasida faqat oddiy elementar yo`l va konturlar hisobga olinadi.
3.6.1-misol:
3.6.1-rasmda berilgan grafdagi x₁ va x₆ tugunlar orasidan uzatishlar (uzatish funksiyasi) topilsin.



3.6.1-rasm. 3.6.1-misol uchun graf.


Yechish:
1)
2)
3)
4)


3.6.2-misol:
3.6.2-rasmda berilgan tizimning uzatish funksiyasi Mezon formulasi yordamida topilsin.

a)

b)

3.6.2-rasm. a - tizimning strukturaviy ko`rinishi, b – graf tasviri

Yechish:
Yo`llar:
Konturlar: