4-мавзу. Graflar nazariyasining asosiy tushunchalari.
Graflar.
Masalalarni yechishda ob’ektlarni nuqtalar, ular orasidagi bog‘lanishlarni esa chiziqlar bilan tasvirlash ancha qo‘laylik tug‘diradi.
1-masala. Mahallada 9 ta xonadon bor. Ma’lumki, Ikrom va Alisher – Pulatning qoʻshnilari, Murod - Ikrom va Samandarning qoʻshnisi, Vali – Doniyor va Nozimning qoʻshnisi, Erkin esa Nozimning qoʻshnisi. Boshqa qoʻshnilar yoʻq. Poʻlat devorlardan oshib Nozimnikiga bora oladimi?
(Umumiy devorga ega boʻlgan honadonlar qoʻshni hisoblanadi.)
Yechilishi. Xonadonlarni nuqtalar bilan tasvirlaymiz va qoʻshni honadonlarni kesishmaydigan chiziqlar bilan tutashtiramiz (1-rasm). Rasmdan Poʻlat devorlardan oshib Nozimnikiga bora olmasligi koʻrinib turibdi.
1-rasm
Nuqtalar va ularning ayrimlarini tutushtirishgan chiziqlardan tashkil topgan shakl graf deyiladi. Nuqtalar grafning uchlari, tutashtiruvchi chiziqlar esa qirralari deyiladi.
|
Grafning qirra bilan tutashtirilgan ikkita uchi qoʻshni uchlar deyiladi. Ikkita uchni tutashtirgan qirralar ketma-ketligi yoʻl deyiladi.
1-masalada grafning va uchlarini tutashtiruvchi yoʻl mavjud emasligi isbotlangan.
Graflar nazariyasi hozirgi kunda matematikaning eng jadal rivojlanayotgan sohasiga aylandi. Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo‘llaniladi. Ulardan ba’zilari quyidagilardir: boshqotirmalarni hal qilish; qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral sxemalar va boshqarish tizimlarini loyihalashtirish; avtomatlar, blok-sxemalar va kompyuter dasturlarini tadqiq qilish va hokazo.
2-masala. 5 nafar bolalar guruhida har bir bola aynan 2 nafar bola bilan tanish boʻlishi mumkinmi?
Yechilishi.
Tegishli graf chizaylik:
yoki .
Demak, masaladagi vaziyat boʻlishi mumkin ekan.
Graf uchidan chiqqan qirralar soni uning darajasi deyiladi. Masalan, 2- rasmda tasvirlangan grafda uchning darajasi 3 ga, uchning darajasi 2 ga, uchning darajasi esa 1 ga teng.
2-rasm
Dostları ilə paylaş: |
