Referati mavzu: Graf erkin uchlarini ajratish masalasi. Bajardi: 1001-20 ki uzb rajjabbayeva Maxbuba

3.Graflarning maxsus turlari.
Shuni ta'kidlash kerakki, qo'shnilik tushunchasi grafning bir jinsli, insidentlik tushunchasi esa uning turli jinsli elementlari orasidagi munosabatni ifodalaydi.
Ba'zan graf undagi elementlar soniga qarab, ya'ni uchlar soni va qirralar (yoylar) soni ga qarab belgilanadi va bu holda grafni -graf deb ataydilar.
gar grafda kortej faqat qirralardan iborat bo'lsa, u holda yo'naltirilmagan (oriyentirlanmagan) va faqat yo'naltirilgan (oriyentirlangan) qirralardan (ya'ni, yoylardan) tashkil topgan bo'lsa, u holda u yo'naltirilgan (oriyentirlangan) graf deb ataladi. Oriyentirlangan graf, qisqacha, orgraf deb ham ataladi.
Qator hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham bo'lgan graflar bilan ish ko'rishga to'g'ri keladi. Bunday graflar aralash graflar deb ataladi.
Agar grafning (orgrafning) korteji tarkibida to'plamdan olingan takrorlanuvchi elementlar bo'lsa, u holda ular karrali yoki parallel qirralar (yoylar) deb ataladi. Karrali qirralari
shartiga ko'ra , va o'zgaruvchilar butun qiymatlar qabul qilgan holda , va shartlarni qanoatlantirishlari kerak. Bu shartlarni qanoatlantiruvchi holatlar quyidagilardir:Holatlar to'plamini bilan belgilaymiz. Suyuqlikni (yoki uning bir qismini) idishlarning biridan boshqa birortasiga quyish natijasida sistema bir holatdan boshqa holatga o'tishi mumkin. Ta'kidlash kerakki, yuqoridagi holatlarning ixtiyoriysidan boshqa birortasiga bevosita yoki bilvosita o'tish imkoniyati mavjud bo'lmasligi ham mumkin. Sistemaning bir holatdan boshqa holatga bevosita o'tishlari to'plamini bilan belgilaymiz. Natijada hosil bo'lgan juftlikni graf deb qarash mumkin. Bu grafning uchlari sistema holatlariga, yoylari (qirralari) esa, bevosita o'tishlarga mos keladi.
Berilgan masalani hal qilish uchun grafning yoylaridan tashkil topgan shunday ketma-ketlik tuzish kerakki, bu ketma-ketlikning birinchi hadi , oxirgi hadi esa bo'lsin. Bunday ketma-ketliklardan biri quyida keltirilgan:
4.Graflarning berilish usullari
1- misol. 1- shaklda tasvirlangan grafni deb belgilaymiz. Berilgan graf belgilangan graf bo'lib, 4ta uch va 6ta qirraga ega. Demak, u (4,6)-grafdir. Bu graf uchun: , , , , , , . grafning barcha ( ) qirralari oriyentirlanmagan (chunki uchlarini tutashtiruvchi chiziklarda yo'nalish ko'rsatilmagan) bo'lgani uchun oriyentirlanmagan grafdir. Grafning qirralaridan biri, aniqrog'i, sirtmoqdir, va esa karrali qirralardir. Bu grafda, masalan, 1 va 2 uchlar qo'shni, 1 va 4 uchlar esa qo'shni emas. Undagi 2 va 3 uchlar qirraga insident va, aksincha, qirra 2 va 3 uchlarga insidentdir. Bu yerda va qirralar qo'shni qirralardir, chunki ular umumiy uchga (3 uch) ega, va qirralar esa qo'shni emas.
2- misol. Geometrik ifodalanishi 2- shakldagi ko'rinishda bo'lgan oriyentirlangan grafni qaraymiz. Bu grafda o'n bitta element bor: 5ta uch va 6ta yoy, ya'ni shaklda (5,6)-orgraf berilgan. Bu grafni bilan belgilaymiz, bu yerda ,
yoki . Berilgan orgrafda sirtmoq ham, karrali yoylar ham yo'q. Bu grafning yoyi uchun 1 boshlang'ich, 3 uch esa oxirgi uchdir.
Qo'shnilik matritsalari.
Endi grafning boshqa bir berilish usuli negizida yotuvchi graf uchlari qo'shniligi matritsasi tushunchasini qarab chiqamiz.
- uchlari soni ga teng bo'lgan belgilangan, sirtmoqsiz va karrali qirralarsiz graf bo'lsin.
Elementlari
ko'rinishda aniqlangan ( ; ) matritsani grafning uchlari qo'shniligi matritsasi deb ataymiz.
Bu ta'rifdan sirtmoqsiz va karrali qirralari bo'lmagan graf uchlari qo'shniligi matritsasining bosh diagonalida faqat nollar bo'lishi, satrlaridagi birlar soni esa mos uchlarning darajalariga tengligi kelib chiqadi.
1- misol. 1- shaklda tasvirlangan grafgning uchlari qo'shniligi matritsasi
ko'rinishda bo'ladi.
Uchlari soni ga teng bo'lgan belgilangan oriyentirlangan grafning uchlari qo'shniligi -matritsasi deb elementlari
ko'rinishda aniqlangan ( , ) matritsaga aytiladi.
2- misol. 2- shaklda tasvirlangan orgrafning uchlari qo'shniligi matritsasi quyidagicha bo'ladi:Endi uchlari bo'lgan belgilangan oriyentirlanmagan multigraf bo'lsin. elementlari grafning va uchlarini tutashtiruvchi qirralar soniga teng bo'lgan ( ) matritsa oriyentirlanmagan multigrafning uchlari qo'shniligi matritsasi deb ataladi.
3- misol. 1- shaklda tasvirlangan oriyentirlanmagan multigraf uchlari qo'shniligi matritsasi quyidagicha bo'ladi:
.Karrali yoylari bo'lgan sirtmoqsiz orgraf uchlari qo'shniligi matritsasi tushunchasini ham yuqoridagiga o'xshash ta'riflash mumkin.
Shunday qilib, manfiymas butun sonlardan tashkil topgan va graf uchun uchlari qo'shniligi matritsasi bo'lgan kvadrat matritsa bilan graf orasida bir qiymatli moslik (izomorflik aniqligida) bor degan xulosa va, bundan, graflar nazariyasi bo'yicha izlanishlar maxsus shartlarni qanoatlantiruvchi mat-ritsalarni tadqiq qilishga keltirilishi mumkinligi kelib chiqadi.
( ) qirralarga ega yakkalangan uchlari, sirtmoq va karrali qirralari bo'lmagan graf uchun elementlari
quyidagicha aniqlangan ( , ) -matritsa grafning qirralari qo'shniligi matritsasi deb ataladi.
4- misol. 1- shaklda tasvirlangan grafda 5ta qirra bo'lib, uning qirralari qo'shniligi matritsasi
ko'rinishga egadir.
Ravshanki, sirtmoqsiz va karrali qirralarsiz graf qirralari qo'shniligi matritsasi bosh diagonalga nisbatan simmetrik kvadrat matritsadir va uning bosh diagonali nollardan iborat.
Insidentlik matritsalari. Uchlari va qirralari ( ) bo'lgan belgilangan graf berilgan bo'lsin. Bu grafning uchlariga satrlari, qirralariga esa ustunlari mos keluvchi va elementlari
5- misol. 1- shaklda tasvirlangan grafning insidentlik matritsasi quyidagicha bo'ladi:
. Endi uchlari va qirralari ( ) bo'lgan belgilangan sirtmoqsiz orgrafni qaraymiz. Elementlari
ko'rinishda aniqlangan ( , ) matritsaga grafning insidentlik matritsasi deb ataladi.
6- misol. 3- shaklda tasvirlangan grafning insidentlik matritsasi quyidagicha bo'ladi:Marshrutlar va zanjirlar haqida umumiy ma'lumotlar. Uchlari to'plami va qirralar korteji bo'lgan oriyentirlanmagan graf berilgan bo'lsin. Bu grafdagi uchlar va qirralarning har ikki qo'shni qirralari umumiy chetki uchga ega
ko'rinishdagi chekli yoki cheksiz ketma-ketligi marshrut deb ataladi. Marshrutni uning uchlari ketma-ketligi yoki qirralari ketma-ketligi ko'rinishda ham belgilash mumkin.
Agar marshrutda qandaydir uchdan oldin uchlar bo'lmasa, bu
.Turli qirralardan tashkil topgan marshrutga zanjir deb ataladi. Agar zanjirning chetlaridan tashqari barcha uchlari turlicha bo'lsa, u holda uni oddiy zanjir deb ataydilar.
Berilgan zanjir yoki oddiy zanjir uchun bo'lsa, u yopiq zanjir deb ataladi. Hech bo'lmaganda bitta qirraga ega yopiq oddiy zanjir sikl deb ataladi.
Sirtmoq yoki bir juft karrali qirralar sikl tashkil etishi ravshandir.
Tushunarliki, grafdagi zanjir grafning qism grafi deb qaralishi mumkin.
6- misol. Yuqoridagi 1- shaklda tasvirlangan graf uchun
ketma-ketlik 3 belgili uchdan 4 belgili uchga yo'nalgan marshrutdir, bunda 3 - boshlang'ich uch, 4 - oxirgi uchdir. Bu marshrutda 1, 2 va 3 belgili uchlar oraliq uchlar hisoblanadi. Qaralayotgan marshrutning uzunligi 6a teng bo'lib, u zanjir bo'la olmaydi, chunki unda 1 belgili uch 2 marta (bir marta oraliq uch sifatida, ikkinchi marta esa oxirgi uch sifatida) qatnashmoqda.
Yana o'sha graf uchun zanjirning oxirgi bo'g'ini sifatida yoki qirralardan qaysisi olinishiga bog'liqsiz ravishda, u yopiq zanjir va sikldir.
Oriyentirlangan graflar uchun ham undagi yoylarning yo'nalishini (oriyentatsiyasini) inobatga olmasdan oriyentirlanmagan marshrut, zanjir
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 dan 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.