7- misol.
Yuqoridagi 2- shaklda tasvirlangan grafni qaraymiz. Uning uch va
qirralaridan tuzilgan ketma-ketlik oriyentirlanmagan marshrut va zanjirdir, lekin u
oddiy zanjir bo‘la olmaydi. Bu ketma-ketlik oriyentirlangan marshrut ham bo‘la
olmaydi, chunki unda marshrut yo‘nalishiga teskari yo‘nalishga ega yoylar bor ().
Qaralayotgan graf uchun ketma-ketlik oriyentirlangan marshrutni tashkil etadi. Bu
marshrut yo‘ldir, lekin u kontur emas. Berilgan grafda faqat bitta kontur bo‘lib, bu
konturni
yoki
ko‘rinishda ifodalash mumkin.
17
Xulosa:
Faraz qilaylik, berilgan sirtmoqsiz va karrali qirralari bo‘lmagan grafning
ixtiyoriy uchi bo‘lsin. Qaralayotgan uchga qo‘shni uchni va bu uchga dan farqli
boshqa qo‘shni uchni, uchga esa dan farqli boshqa qo‘shni uchni, va hakoza, uchga
an farqli boshqa qo‘shni uchni, va hakoza, tanlab qirralar ketma-ketligini tuzamiz.
Teoremaning shartlariga ko‘ra yuqoridagi jarayonni amalga oshirish va talab etilgan
xossaga ega uchni topish mumkinligini ta’kidlaymiz.
Oriyentirlangan graflar uchun ham undagi yoylarning yo‘nalishini
(oriyentatsiyasini) inobatga olmasdan oriyentirlanmagan marshrut, zanjir va oddiy
zanjir tushunchalarini kiritish mumkin. Lekin, oriyentirlangan graflar uchun
oriyentirlangan marshrut tushunchasini kiritish tabiiydir.
Foydalangan adabiyotlar
1.
Андерсон Дж. Дискретная математика и комбинаторика. — М. Вильямс.
2006. — 960 с.
2.
Зыков А.А. Основы теории графов. - М: Вузовская книга, 2004. - 664 с.
3.
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по
теории графов. М.: Наука, 1990. 384с.
4.
Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980. — С. 336
|
