| 1.2. Graflarning berilish usullari.
Avvalo graflarning giometrik ifodalanishiga to’xtalamiz.Graflarning turlicha berilish usullari mavjud.Grafningabstrakt matematik ta’rifi uning berilish usullaridabiridir.Grafning boshqa berilish usullaridan ham foydalanish mumkin. Masalan,grafning elementlarini, ya’ni uchlari va qirralarini yozish yoki aytish grafning berilishusuli sifatida qaralishi mumkin. Grafning boshqa berilishiusullari ham mavjud.
Grafning uchlarini tekislikda yoki fazoda nuqtalar bilan, qirralarini esa mos uchlarini tutashtiruvchi uzluksiz chiziqlar bilan ifodalab, qandaydir diogrammani – grafning ko’rgazmali tasvirini hosil qilamiz.
Ba’zi hollarda diogrammada grafuchlari doiralar yordamida yoki qandaydir boshqa usulda ifodalanadi. Grafning qirralariga mos chiziqlarning to’g’ri yoki egri bo’lishi va ularning uzunligiahamyatga ega emas.Muximi bu chiziqlar uzluksiz bo’lib, grafning qandaydir ikkita uchlarini tutashtirishi lozim.
Ixtiyoriy grafuchun bunday diogrammalarni istalgancha tuzish mumkinligi ravshan.Agarbirordiogrammadagrafninguchlariga mos keluvchi nuqtalar ustma-ust tushmasa qirralariga mos keluvchi chiziqlar, chetki nuqtalarini hisobga olmaganda umumiy nuqtalargaega bo’masa, bunday diogramma grafning giometrik ifodalanishi deyiladi. Bitta graf turlicha giometrik ifodalanishi mumkin.
1-1.Teorema
Har qanday chekli grafni uch o’lchovli yevkilid fazosida giometrik ifodalash mumkin.
Teoremadagi uchni ikkiga almashtirib bo’lmaydi, chunki tekislikda
qirralarni ifodalovchi kesishmaydigan chiziqlar yordamida tasvirlash imkoniyati faqat ba’zi graflarga xos, yani har qanday grafning ikki o’lchovli Yevkilid fazosida giometrik ifodalanishi mavjud bo’lavermaydi.
Graflarning giometrik ifodalanishiga misollar keltiramiz
1.1 misol.
chizmada tasvirlangan grafni
1.1- chizma
deb belgilaymiz.
Berilgan graf belgilangan graf bo’lib, 4 ta uch va 6ta qirraga ega.
Demak, (4,6) grafdir.
Bu graf uchun:
qirralar orientirlangan (chunki uchlarini tutashtiruvchichiziqlarda yo’nalish ko’rsatilmagan ) bo’lgani uchunorientirlangan grafdir. Grafning qirralaridan biri aniqrog’I, sirtmoqdir .va lar esa karrali qirralardir. Bu grafda, masalan 1 va 2 uchlar qo’shni, 1 va 4 uchlar esa qo’shni emas. Undagi 2 va 3 larqirragaintsident, va aksincha,qirra 2 va 3 uchlarga insident.
Bu yerdava qirralar qo’shni qirralar, chunki ular umumiy 3 uchga ega va qirralar qo’shni emas.
misol . Giometrik ifodalanishi 1.2- chizmada berilgan orientirlangan
grafni qaraymiz. Bu grafda 11 ta element bor: 5 ta uch, 6 ta yog’. Bu grafnibilan belgilaymiz, buyerda yoki Berilgan orgrafda sirtmoq karrali yoylar ham yo’q. Bu grafning (1,3) yoyi uchun 1 boshlang’ich, 3 esa oxirgi uchdir.
1.3-misol Ushbu chizmada tasvirlangan graflar bir- biriga izomorfdir.
1.4 – misol Ushbu
chizmada tasvirlangan graflarning har biri 6ta uch va 7 ta qirraga ega bo’lib, ular izomorf emas.
Hammasi bo’lib, 5 ta qavariq muntazam ko’pyoqni mavjudligi Yevkilid tomonidan isbotlangan. Bular: tetraedr, kub, oktaedr, dodakaedr, ikosaedr.
Bu ko’pyoqlarning umumiy nomihambor – Ploton jismlari. Barcha Ploton jismlariga mos graflar tekislikda giometrik ifodalanadi. Masalan, tetraedr va kubga mos graflarninggiometrikifodalanishi ushbu chizmada tasvirlangan.
Ploton jismlaridan tetraedr , kub, dodakaedr kubik grafga misol bo’ladi.
Agar graf tekislikda giometrik ifodalanishga ega bo’lsa, u holdda bunday graf tekis graf deyiladi.
Ploton jismlariga mos graflarning barchasi tekis graflardir.Tekis graflarga izomorf graf planargraf deyiladi.
Tekis bo’lmagan grafga ajoyibmisoluch uy va uchquduq haqidagi boshqotirma masalaga mos keluvchi grafdir.
Endi grafnimaxsus turdagi ko’phad yordamida berish masalisini qaraymiz. Bizga uchlarito’plamibo’lgan graf berilgan bo’lsin . grafning yakkalangan uchlari yo’q deb faraz qilamiz. Bu graftao’zgaruvchilarga bog’liq:
Ko’rinishdagi ko’phad yordamida tasvirlash mumkin, bu yerda ko’paytma shartni qanoatlantiruvchi barchajuftlar bo’yicha amalga oshiriladi,o’zgaruvchiuchga mos keladi, va uchlarni tutashtiruvchi qirralar uchdagisirtmoqlar soni.
ko’phadgrafga izomorflik aniqligida mos kelishini isbotlash mumkin.
1.5- misol. Maskur chizmada tasvirlangan grafga mos ko’phadni aniqlaymiz.
Berilgan orientirlanmagan grafga 7 ta uch va 8 ta qirra bor. Uning har bir uchiga o’zgaruvchini mos qilib qo’yamiz. grafda karrali qirralar yo’q, uning uchta qirrasi sirtmoqlardan iborat bo’lib, ulardan ikkitasi 3 uchga, biri esa 5 uchga intsidentdir. Shuning uchun
qolgan barcha bo’ladi .Berilgan grafga mos ko’phad ko’rinishga ega bo’ladi.
Endi grafning boshqa bir berilish usuli negizida yotuvchi graf uchlari qo’shnilik matritsasi tushunchasini qaraymiz.
uchlari soni da, teng bo’lgan belgilangan sirtmoqsiz va karrali qirralarsiz graf bo’lsin.
Elementlari
ko’rinishda aniqlangan matritsaning grafning uchlari qo’shniligi matritsasi deb ataymiz.
Bu tarifdan sirtmoqsiz karrali qirralari bo’lmagan graf uchlari qo’shniligi matritsasining bosh diaganalida faqat nollar bo’lishi satirlaridagi 1 lar soni esa mos uchlarning darajalariga tengligi kelib chiqadi.
1.6-misol. Ushbu
1.3 chizma
Grafning uchlari qo’shniligi matrisasi
ko’rinishda bo’ladi.
Uchlari soni m ga teng bo’lgan belgilangan oryantirlangan G=(V,U) grafning uchlari qo’shniligi mxm – matritsasi deb elementlari
Ko’rinishida aniqlangan A=(), i,j=1,…m matrisaga aytiladi. 1.3-chizilmada tasvirlangan orgrafning uchlari qo’shniligi matritsasi quydagicha bo’ladi:
Endi G uchlari 1,…,m bo’lgan belgilangan orientirlanmagan multigraf bo’lsin. elementlari G grafning i va j uchlarini tutashtiruvchi qirralar soniga teng bo’lgan i,j=1,…m matrisa orientrlanmagan multigrafning uchlari qo’shnilik matritsasi deyiladi.
1.8-misol. 1.3 chizmada tasvirlangan orientirlangan multigraf uchlari qo’shniligi matritsasi quyidagicha bo’ladi:
Karrali yoylari bo’lgan sirtmoqsiz orgraf uchlari qo’shniligi matritsasi tushunchasini ham yuqoridagidek ta’riflash mumkin.
1.3-Teorema Graflar faqat va faqat uchlari qo’shniligi matritsalari bir- biriga satrlarining o’rinlarini va ustunlarining o’rinlarini mos almashtirishlar yordamida hosil bo’lsagini izomorf bo’ladi.
qirralarga ega yakkalangan uchlari, sirtmoq va karralari qirralari bo’lmagan graf uchun elementlari
kabi aniqlangan matritsa grafning qirralari qo’shniligi matritsasi deyiladi.
Chizmada tasvirlangan grafda 5 ta qirra bo’lib uning qirralari qo’shniligi matritsasi
ko’rinishga egadir.
Sirtmoqsiz va qirralari qirralarsiz graf qirralari qo’shniligi matritsasi dioganalga nisbatan simmetrik kvadrat matritsadir va uning bosh dioganali nollardan iborat.
Endi intsedentlik matritsalarga to’xtalamiz. Uchlari va qirralari bo’lgan belgilangan graf berilgan bo’lsin. Bu grafning uchlariga satrlari, qirralariga esa ustunlari mos keluvchi va elementlari
Kabi aniqlangan
matritsa grafning intsidentlik matritsasi deyiladi .
- chizmada tasvirlangan grafning intsidentlik matritsasi quyidagicha bo’ladi.
Endi uchlari va qirralari bo’lgan belgilangan sirtmoqsiz orgrafni qaraymiz. Elementlari
kabi aniqlangan matritsaga grafning intsentlik matritsasi deyiladi.
Ushbu
Grafning intsidentlik matritsasi quyidagicha bo’ladi.
1.3- Teorema.Graflarfaqat va faqat intsidentlik matritsalari bir – biridan satrlarining o’rinlarini va ustunlarining o’rinlarini mos almashtirishlar yordamida hosil bo’lsagina izomorf bo’ladi.
Graflar ustida amallar .
Graflar ustida turli amallar bajarish mumkin. Masalan, graflarning birlashtirish, biriktirish, ko’paytirish, grafni qismlarga ajratishva hokazo.
Eng sodda amallardan biri sifatida grafdan uchni olib tashlash amalini keltirsa bo’ladi. Bu amalni qo’llash berilgan grafning uchlari to’plamidan biror element yo’qotishni anglatadi.
Natijada uchlari soni 1 taga kam yangi graf paydo bo’ladi. Bu amalni uchlari soni ikkitadan kam bo’lmagan graflarga qo’llash mumkin bo’lib, uni bajarish jarayonida olib tashlanayotgan uch bilan birgalikda shu uchga intsident bo’lgan barcha qirralar ham olib tashlanadi.
Eng sodda amallar qatoriga grafdan qirrani olib tashlash amalini kiritish mumkin. Bu amalga ko’ra, berilgan grafning qirralari to’plamidan birorta element olib tashlanadi. Berilgan grafda qirralarini olib tashlashda shu qirraga intsident uchlarni grafda qoldirish ham, yo’qotish ham mumkin.
va graflar berilgan bo’lsin. Agar va grafning barcha qirralari grafning ham qirralari bo’lsa bo’lsa, u holda graf grafning qism grafi deyiladi.
Agar graf karrali qirralarga ega bo’lmasa u holda uchlari grafning barcha uchlaridan iborat bo’lgan shunday yagona graf mavjudki , grafdagi barcha juft uchlar faqat va faqat grafda qo’shni bo’lmagandagina qo’shnidir. Bunday graf berilgan grafning to’ldiruvchi grafi deyiladi. Berilgan graf uchun to’ldiruvchi grafni qurish jarayonini ham graflar ustida bajariladigan amallar qatoriga qo’shish mumkin. graf uchun to’ldiruvchi grafni qurish amalini qo’llash natijasida graf hosil bo’ladi.munosabatni isbotlash mumkin. Graflar ustida shunday amallarni bajarish mumkin, ular elementlari soni berilgan grafdagidan ko’proq bo’lgan boshqa graflarning hosil bo’lishiga olib keladi. Bunday amallar qatoriga uchni qo’shish amali yoki qirrani qo’shish amalini kiritish mumkin.
Grafga yangi uchni qo’shishni turli usul bilan amalga oshirish mumkin. Masalan, yangi uchni berilgan grafda qo’shish shu grafning va uchlariga intsident bo’lgan qandaydir qirrasiga qo’shish orqali quyidagicha 2 bosqichda bajarilishi mumkin
qirra berilgan grafdan olib tashlanadi
Hosil bo’lgan grafga ikkita yangi qirralar va uchlarida intsident qirra hamda va uchlarga intsident qirra qo’shiladi.
Bu jarayon grafda qirraga darajasi ikki bo’lgan yangi uchni qo’shish yoki qirrani 2 ga bo’lish amali deb ataladi.
Agar graf grafdan qirrani ikkiga bo’lish amali chekli marta ketma- ket qo’llash vositasida hosil qilingan bo’lsa, u holda graf grafning bo’linish grafi deyiladi. Bo’linish graflari izomorf bo’lgan graflar gomeomorf graflar deyiladi. Ushbu
shaklda tasvirlangan graflar izomorf emas, lekin ular gomeomorf, chunki bu graflarning har biri ushbu
Shaklda tasvirlangan bo’linish grafga ega.
Bizga va graflar berilgan bo’lsin. Uchlari to’plami va qirralari korteji kabi aniqlangan grafga va graflarning birlashmasi (uyushmasi) deyiladi va kabi belgilanadi.
Misol: Quyidagi chizmada uchlari to’plamlari kesishmaydigan va graflarning birlashma amali tasvirlangan:
Misol: uchlari to’plamlari kesishadigan graflarning birlashmasi quyidagi chhizmada tasvirlangan
Agar birlashtirilayotgan graflarning uchlari to’plamlari kesishmasa, u holda bu graflarning birlashmasi dizyunkt birlashma deyiladi. Masalan, 1.4-chizmada tasvirlangan birlashma dizyunkt, 1.5-chizmadagi birlashma esa dizyunkt emas.
Graflarni biriktirish amalini qaraymiz. Bizga va
graflar berilgan bo’lsin. va graflar birlashtirilishi hamda grafning har bir uchi grafning har bir uchi bilan qirra vositasida tutashtirilishi natijasida hosil bo’lgan graf va graflarning birikmasi (tutashmasi) deyiladi va kabi belgilanadi.
Misol: ushbu
chizmada uchlari to’plamlari kesishmaydigan va graflarning birikmasi amali tasvirlangan.
Agar uchlari to’plamlari kesishmasi bo’sh bo’lmagan graflarni birlashtirish zarur bo’lsa , u holda hal qilinayotgam masala xossalarini e’tiborga olish kerak.
Graflarni ko’paytirish amali. Bizga va graflar berilgan bo’lsin. Uchlari to’plami bo’lgan grafning qirralari kortejini quyidagicha aniqlaymiz: agar va yoki va bo’lsa , u holda bo’ladi, bu yerda va
. Bunday usul bilan hosil bo’lgan graf graflarning ko’paytmasi deyiladi va kabi belgilanadi.
Graflarning ko’paytmasi ta’rifiga asosan, berilgan va graflarning ko’paytmasi hisoblangan grafdagi:
Uchlari yoki ko’rinishdagi juftliklardan iborat, bu yerda ;
va uchlar faqat va faqat shu holda qo’shni bo’ladiki, qachonki bu uchlarni (juftliklarni) tashkil qiluvchi elementlarning biri unga mos element bilan ustma-ust tushgan holda boshqa elementlarda o’z grafiga qo’shni bo’lishsa, bu yerda
munosabatlardanva bo’lishi kelib chiqadi.
Misol : Ushbu
Chizmada uchlari to’plamlari kesishmaydigan va graflarning ko’paytmasi amali tasvirlangan.
Dekartko’paytmalar bilan bog’liq tuzilmalar ustida bajariladigan amallar boshqalardan o’ziga xosligi bilan ajralib turadi. Bu o’ziga xoslik graflarni ko’paytirish amalida namoyon bo’ladi. Graflar ko’paytmasida qatnashgan bironta grafning qirralari katreji bo’sh bo’lsada, ko’paytirish amalini qo’llash natijasida hosil bo’lgan grafning qirralari kotreji bo’sh bo’lmasligi ham mumkin. Xaqiqatan ham, yuqorida keltirilgan graflarningko’paytmasi ta’rifidan kelib chiqadiki, agar graf va graflarning ko’paytmasi, ya’ni bo’lsa, u holda bo’ladi va kortej elementlari bilan birlashma elementlari orasida bir qiymatli moslik mavjud. Shuning uchun, agar masalan bo’lsa , u holda
bo’ladi, chunki grafning ta’rifiga ko’ra ,Demak ya’ni bo’sh graf bo’lsada, bo’sh bo’lmagan grafdir.
Graflarni ko’paytirish amalini qayta takror qo’llash usuli bilan graflar nazariyasining muhim sinfini tashkil etuvchi o’lchovli kublarni aniqlash mumkin. o’lchovli kubuchlari soni ikkiga teng bo’lgan to’la graf yordamida quyidagi rekkurent formula bilan aniqlanadi
Yuqorida graflar ustidagi ba’zi amallar haqida qisqacha ma’lumot berildi. Shuni ta’kidlash lozimki, graflar ustida bundan boshqa bir qator amallar ham bor.
| 