Toxirov javohirning diskret tuzulmalar fanidan mustaqil ishi

1.1.1-lemma. Ixtiyoriy orientirlanmagan grafda barcha uchlar darajalari yig’indisi qirralar sonining ikki baravariga teng.
Agar grafning uchlar to’plamini o’zaro kesishmaydigan shunday qisim to’plamlarga ajratish mumkin bo’lib, grafning ixtiyoriy qirrasi bu to’plamlarning biridan olingan qandaydir uchni ikkinchi to’plamdan olingan biron uch bilan tutashtiradigan bo’lsa, u holda bunday grafga ikki bo’lakli graf deyiladi. Agar ikki bo’lakli grafning turlibo’laklariga tegishli istalgan ikki uch qo’shni bo’lsa, u holda bugraf to’la ikki bo’lakli graf deyiladi.
To’la ikki bo’lakli grafni K_m,n bilan belgilaymiz, bu yerda m va n bilan grafning bo’laklaridagi uchlar sonini belgila K_m,n=(V,U) graf uchun
bo’lishi ravshan, bu yerda grafning uchlari soni, uning qirralari soni. Ikkinchidan katta ixtiyoriy natural k soni uchun k bo’lakli graf tushunchasini ham shunga o’xshash kiritish mumkin.


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.

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
   

G=(V,U) deb belgilaymiz.
Berilgan G 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 uchun G orientirlangan 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 lar  qirragaintsident, va aksincha,  qirra 2 va 3 uchlarga insident.
Bu yerda va qirralar qo’shni qirralar, chunki ular umumiy 3 uchga ega  va  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
 bilan belgilaymiz, buyerda
 yoki
 Berilgan G 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  bo’lgan  graf berilgan bo’lsin .  grafning yakkalangan uchlari yo’q deb faraz qilamiz. Bu graf m ta  o’zgaruvchilarga bog’liq:

Ko’rinishdagi ko’phad yordamida tasvirlash mumkin, bu yerda ko’paytma
 shartni qanoatlantiruvchi barcha  juftlar bo’yicha amalga oshiriladi,  o’zgaruvchi uchga mos keladi,  va  uchlarni tutashtiruvchi qirralar  uchdagisirtmoqlar soni.
 ko’phad G grafga izomorflik aniqligida mos kelishini isbotlash mumkin.
1.5- misol. Maskur chizmada tasvirlangan G 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. G 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 G 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 m, 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.

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

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