Mustaqil ish fan nomi: Algoritmlash va loyihalash Guruh: 042 –19 Bajardi: Maxmudov X tekshirdi: Mamadaliyev X mavzu

O’zbekiston Respublikasi Toshkent Shahridagi Muhammad Al-Xorazmiy

nomidagi Toshkent Axborot Texnologiyalari Universiteti
Telekommunikatsiya Texnologiyalari fakulteti
MUSTAQIL ISH

Fan nomi:

Algoritmlash va loyihalash
Guruh: 042 –19
Bajardi: Maxmudov X
Tekshirdi: Mamadaliyev X

Mavzu: Graflarni eniga va bo‘yiga aylanishi (tekshirish).

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.

1. 
   
   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.

1. 
   
   chizmada tasvirlangan grafni
   
2. 
   
   1.1- chizma
   

_{_x0007_}deb belgilaymiz.
Berilgan _{_x0007_} graf belgilangan graf bo’lib, 4 ta uch va 6ta qirraga ega.

Demak, (4,6) grafdir.

Bu graf uchun:_x0007_

qirralar orientirlangan (chunki uchlarini tutashtiruvchichiziqlarda yo’nalish ko’rsatilmagan ) bo’lgani uchun_{_x0007_}orientirlangan grafdir. Grafning qirralaridan biri aniqrog’I, _{_x0007_}sirtmoqdir ._{_x0007_}va_{_x0007_} 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 lar_{_x0007_}qirragaintsident, va aksincha,_{_x0007_}qirra 2 va 3 uchlarga insident.

Bu yerda_{_x0007_}va_{_x0007_} qirralar qo’shni qirralar, chunki ular umumiy 3 uchga ega _{_x0007_} va _{_x0007_} qirralar qo’shni emas.

1. 
   
   misol . Giometrik ifodalanishi 1.2- chizmada berilgan orientirlangan
   

grafni qaraymiz. Bu grafda 11 ta element bor: 5 ta uch, 6 ta yog’. Bu grafni_{_x0007_}bilan belgilaymiz, buyerda_{_x0007_} yoki _{_x0007_} Berilgan _{_x0007_}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’plami_{_x0007_}bo’lgan _{_x0007_}graf berilgan bo’lsin . _{_x0007_}grafning yakkalangan uchlari yo’q deb faraz qilamiz. Bu graf_{_x0007_}ta_{_x0007_}o’zgaruvchilarga bog’liq:

Ko’rinishdagi ko’phad yordamida tasvirlash mumkin, bu yerda ko’paytma _{_x0007_}shartni qanoatlantiruvchi barcha_{_x0007_}juftlar bo’yicha amalga oshiriladi,_{_x0007_}o’zgaruvchi_{_x0007_}uchga mos keladi, _{_x0007_} va_{_x0007_} uchlarni tutashtiruvchi qirralar_{_x0007_} uchdagisirtmoqlar soni.

_{_x0007_}ko’phad_{_x0007_}grafga izomorflik aniqligida mos kelishini isbotlash mumkin.
1.5- misol. Maskur chizmada tasvirlangan _{_x0007_} grafga mos ko’phadni aniqlaymiz.

Berilgan orientirlanmagan grafga 7 ta uch va 8 ta qirra bor. Uning har bir uchiga _{_x0007_} o’zgaruvchini mos qilib qo’yamiz. _{_x0007_}grafda karrali qirralar yo’q, uning uchta qirrasi sirtmoqlardan iborat bo’lib, ulardan ikkitasi 3 uchga, biri esa 5 uchga intsidentdir. Shuning uchun

_{_x0007_} qolgan barcha _{_x0007_}bo’ladi .Berilgan _{_x0007_} grafga mos ko’phad _{_x0007_} ko’rinishga ega bo’ladi.
Endi grafning boshqa bir berilish usuli negizida yotuvchi graf uchlari qo’shnilik matritsasi tushunchasini qaraymiz.


_{_x0007_}uchlari soni _{_x0007_} da, teng bo’lgan belgilangan sirtmoqsiz va karrali qirralarsiz graf bo’lsin.
Elementlari

ko’rinishda aniqlangan _{_x0007_} 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


_{_x0007_} 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=(_{_x0007_}), i,j=1,…m matrisaga aytiladi. _{_x0007_}1.3-chizilmada tasvirlangan orgrafning uchlari qo’shniligi matritsasi quydagicha bo’ladi:

Endi G uchlari 1,…,m bo’lgan belgilangan orientirlanmagan multigraf bo’lsin. _{_x0007_} elementlari G grafning i va j uchlarini tutashtiruvchi qirralar soniga teng bo’lgan _{_x0007_} 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.

_{_x0007_}qirralarga ega yakkalangan uchlari, sirtmoq va karralari qirralari bo’lmagan graf uchun elementlari
kabi aniqlangan _{_x0007_} matritsa grafning qirralari qo’shniligi matritsasi deyiladi.

1. 
   
   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 _{_x0007_}va qirralari _{_x0007_}bo’lgan belgilangan graf berilgan bo’lsin. Bu grafning uchlariga satrlari, qirralariga esa ustunlari mos keluvchi va elementlari
Kabi aniqlangan _{_x0007_}

matritsa grafning intsidentlik matritsasi deyiladi .

1. 
   
   - chizmada tasvirlangan grafning intsidentlik matritsasi quyidagicha bo’ladi.
   

Endi uchlari _{_x0007_}va qirralari _{_x0007_} bo’lgan belgilangan sirtmoqsiz orgrafni qaraymiz. Elementlari

kabi aniqlangan _{_x0007_} 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.

_{_x0007_} 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.

_{_x0007_}va_{_x0007_} graflar berilgan bo’lsin. Agar _{_x0007_}va_{_x0007_} grafning barcha qirralari _{_x0007_} grafning ham qirralari bo’lsa _{_x0007_} bo’lsa, u holda _{_x0007_} graf _{_x0007_} grafning qism grafi deyiladi.

Agar _{_x0007_} graf karrali qirralarga ega bo’lmasa u holda uchlari _{_x0007_} grafning barcha uchlaridan iborat bo’lgan shunday yagona _{_x0007_} graf mavjudki ,_{_x0007_} grafdagi barcha juft uchlar faqat va faqat _{_x0007_} grafda qo’shni bo’lmagandagina qo’shnidir. Bunday _{_x0007_} graf berilgan _{_x0007_} grafning to’ldiruvchi grafi deyiladi. Berilgan graf uchun to’ldiruvchi grafni qurish jarayonini ham graflar ustida bajariladigan amallar qatoriga qo’shish mumkin. _{_x0007_}graf uchun to’ldiruvchi grafni qurish amalini qo’llash natijasida _{_x0007_} graf hosil bo’ladi._{_x0007_}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 _{_x0007_} uchni berilgan grafda qo’shish shu grafning _{_x0007_} va _{_x0007_} uchlariga intsident bo’lgan qandaydir _{_x0007_} qirrasiga qo’shish orqali quyidagicha 2 bosqichda bajarilishi mumkin

1. 
   
   _{_x0007_} qirra berilgan grafdan olib tashlanadi
   
2. 
   
   Hosil bo’lgan grafga ikkita yangi qirralar _{_x0007_}va_{_x0007_} uchlarida intsident _{_x0007_} qirra hamda _{_x0007_} va _{_x0007_} uchlarga intsident _{_x0007_} 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 _{_x0007_} graf _{_x0007_} grafdan qirrani ikkiga bo’lish amali chekli marta ketma- ket qo’llash vositasida hosil qilingan bo’lsa, u holda _{_x0007_} graf _{_x0007_} 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 _{_x0007_}va_{_x0007_} graflar berilgan bo’lsin. Uchlari to’plami _{_x0007_}va qirralari korteji _{_x0007_} kabi aniqlangan _{_x0007_} grafga _{_x0007_} va _{_x0007_}graflarning birlashmasi (uyushmasi) deyiladi va _{_x0007_} kabi belgilanadi.

Misol: Quyidagi chizmada uchlari to’plamlari kesishmaydigan _{_x0007_}va_{_x0007_} 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 _{_x0007_}va

_{_x0007_}graflar berilgan bo’lsin. _{_x0007_}va_{_x0007_} graflar birlashtirilishi hamda_{_x0007_} grafning har bir uchi _{_x0007_} grafning har bir uchi bilan qirra vositasida tutashtirilishi natijasida hosil bo’lgan _{_x0007_} graf _{_x0007_} va _{_x0007_} graflarning birikmasi (tutashmasi) deyiladi va _{_x0007_} kabi belgilanadi.
Misol: ushbu

chizmada uchlari to’plamlari kesishmaydigan _{_x0007_} va _{_x0007_} 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 _{_x0007_}va_{_x0007_} graflar berilgan bo’lsin. Uchlari to’plami_{_x0007_} bo’lgan _{_x0007_} grafning qirralari kortejini quyidagicha aniqlaymiz: agar_{_x0007_} va _{_x0007_} yoki _{_x0007_} va _{_x0007_} bo’lsa , u holda _{_x0007_}bo’ladi, bu yerda _{_x0007_} va

_{_x0007_}. Bunday usul bilan hosil bo’lgan _{_x0007_} graf _{_x0007_} graflarning ko’paytmasi deyiladi va_{_x0007_} kabi belgilanadi.

Graflarning ko’paytmasi ta’rifiga asosan, berilgan _{_x0007_}va_{_x0007_} graflarning ko’paytmasi hisoblangan _{_x0007_} grafdagi:

• 
  
  Uchlari _{_x0007_} yoki _{_x0007_} ko’rinishdagi juftliklardan iborat, bu yerda _{_x0007_} ;
  
• 
  
  _{_x0007_} va _{_x0007_}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_{_x0007_}
  

_{_x0007_}munosabatlardan_{_x0007_}va _{_x0007_} bo’lishi kelib chiqadi.
Misol : Ushbu

Chizmada uchlari to’plamlari kesishmaydigan _{_x0007_} va _{_x0007_}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 _{_x0007_} graf _{_x0007_}va_{_x0007_} graflarning ko’paytmasi, ya’ni _{_x0007_} bo’lsa, u holda _{_x0007_} bo’ladi va _{_x0007_} kortej elementlari bilan _{_x0007_} birlashma elementlari orasida bir qiymatli moslik mavjud. Shuning uchun, agar masalan _{_x0007_}bo’lsa , u holda

_{_x0007_} bo’ladi, chunki grafning ta’rifiga ko’ra ,_{_x0007_}Demak _{_x0007_} ya’ni _{_x0007_} bo’sh graf bo’lsada, _{_x0007_} bo’sh bo’lmagan grafdir.

Graflarni ko’paytirish amalini qayta takror qo’llash usuli bilan graflar nazariyasining muhim sinfini tashkil etuvchi _{_x0007_} o’lchovli kublarni aniqlash mumkin. _{_x0007_}o’lchovli kub_{_x0007_}uchlari soni ikkiga teng bo’lgan to’la graf _{_x0007_} yordamida quyidagi rekkurent formula bilan aniqlanadi _{_x0007_}