Nizomiy nomidagi toshkent davlat pedagogika universiteti tabiiy fanlar fakulteti

Graf qirralari

Faqat yakkalangan uchlardan tashkil topgan grafni nol graf deyiladi va orqali belgilanadi.

Ikkita chetki ya’ni boshlang’ich va oxirgi qirralari ustma-ust tushga qirra sirtmoq deyiladi va uni kabi yoziladi (1.2–rasm).
Agar grafning ikiita uchi o’zaro bir necha qirralar orqali tutashgan bo’lsa bunday qirralarni parallel yoki karrali qirralar deyiladi (1.3–rasm).
Bunda agar graf yo’naltirilgan bo’lsa, hr bir qirra uchun yo’nalish aniqlanadi. Misol sifatida, jamoaviy musobaqani olish mumkin. Bunda jamoalar mos ravishda grafning uchlari hisoblanadi. Ikkita va jamoalar har safar bir-biri bilan o’ynaganda ular qirra orqali tutashtiriladi. Agar jamoa ni yutsa u holda yo’nalish dan tomon yoki, aksincha yo’naltiriladi. Durang natija esa yo’naltirilmagan qirrani ifodalaydi.

1.2–rasm 1.3–rasm

• 
  Graf yoylari
  

Tarmoq bo'ylab o'tkazish mumkin bo'lgan oqimlar orasida miqdori eng katta (maksimal) oqimni topish amaliyot nuqtayi nazaridan katta ahamiyatga egadir. Bunday oqimlar maksimal oqimlar , deb ataladi. 1-misolda keltirilgan oqim maksimal oqim emas, chunki berilgan tarmoq uchun miqdori 5 bo'lgan oqim bor. Albatta, umumiy holda tarmoqda bir necha turli maksimal oqimlar bo'lishi mumkin.
Maksimal oqimni o'rganishda quyidagi tushunchalarni kiritish maqsadga muvofiqdir. To'yingan yoy- bu yoy bo'ylab oqim miqdori uning o'tkazish qobiliyatidan kichik.
2-misol. Birinchi misolda qaralgan tarmoq uchun aniqlangan X oqimda bo'lgani uchun to'yinmagan, esa to'yingan yoylardir.
Tarmoqdagi oqimlarni o'rganishda, zanjir tushunchasi muhim rol o'ynaydi. Bu yerda zanjir deganda tarmoqdagi yo'nalishi e'tiborga olinmasdan bir-biriga ulangan yoylar ketma-ketligini tushunamiz. Biron zanjirga tegishli yoyning yo'nalishi zanjirdagi uchlar ketma-ketligini o'tish yo'nalishiga mos tushsa, bu yoyni to'g'ri yoy deb, aks holda esa, uni teskari yoy deb ataymiz.
Tarmoqdagi oqimlarni tadqiq qilganda kesim tushunchasi ham muhim hisoblanadi. T tarmoqning G orgrafi uchlari to'plami V ni o'zaro kesishmaydigan hamda har biri bo'sh bo'lmagan ikkita qism to'plamlarga ajratamiz, ya'ni .

•