|
Reja: Yo’l, zanjir, sikl
|
| bet | 2/2 | | Sana | 15.05.2024 | | Hajmi | 309,71 Kb. | | #236518 |
Bog'liq diskretd(i, j) minl [i, j] ga aytiladi, bu yerda l [i, j] [i, j] zanjirning uzunligi va minimum barcha [i, j]
zanjirlar bo’yicha olinadi (albatta bu minimum sodda zanjirlarda erishiladi).
Kiritilgan d(i, j) uchun masofaning barcha xossalari (aksiomalari) bajariladi:
1)d (i,i )=0; d(i,j)>0 ( i j);
2) d(i, j) d( j,i);
3) d(i, j) d( j, k) d(i, k) .
Demak, X to’plam metrik fazoni tashkil etadi.
G (X ,U,) mulьtigraf berilgan bo’lsin, bu yerda X {x1 , x2 ,..., xn } ,
U {u1 ,u2 ,..., um } va A(G) (i j ) qo’shnilik matritsasi.
Grafning xi va x j uchlarini tutashtiruvchi uzunligi l 1 bo’lgan turli xil
marshrutlar sonini va o’zlarini aniqlash masalasini qaraymiz. Bu son
[A(G)]l (i ( j l) ) matritsaning i ( j l) elementiga teng.
Haqiqatan ham l 1 bo’lganda o’z-o’zidan ravshan. Faraz qilaylik ( )
l
i k
uzunlikdagi l teng xi va xk uchlarni tutashtiruchi marshrutlar soni bo’lsin. Unda xi
va x j uchlarni tutashtiruvchi uzunliklari l 1 (oxiridan oldingi xk uchni tanlab
olgan holda) marshrutlar soni ( )
l
i k k j ga teng, umumiy holda esa barcha
marshrutlar soni matritsalar ko’paytmasi qoidasiga asosan ( 1)
1
( )
k j i l j
n
k
l
i k ga teng.
11-shakl.
12-shakl.
3. . Eyler graflari G grafning barcha uchlarini o’z ichida saqlovchi qism graflarini qaraymiz. G ning barcha qirralari kabi tartiblangan bo’lsin. G grafning har qanday G qismiga 0 va 1 lardan iborat o’lchovli vektorni mos qo’yamiz: 0, . 1, , agar u H agar u H a i i i (N ning xarakteristik vektori). Bu moslik o’zaro bir qiymatlidir, shu bilan birga qism graflarning 2 modul bo’yicha yig’indisiga ularning xarakteristik vektorlarining yig’indisi mos keladi. Barcha qism graflar to’plami yig’indi amaliga nisbatan abelь gruppasini tashkil etadi. Bu gruppa {0,1} koeffiitsentlar maydoni ustida chiziqli fazoni tashkil etadi (istalgan N qism grafning 1 ga ko’paytmasi N ni beradi, 0 ga ko’paytmasi esa bo’sh grafdir). Ko’rinib turibdiki G graf qismlarining fazosi ularning xarakteristik vektorlarining fazosiga izomorf va m o’lchovli. Agar grafning barcha uchlarining darajalari (ya’ni ularga intsident bo’lgan qirralar soni) juft bo’lsa, graf ham juft deyiladi. Juft grafda istalgan sodda zanjirni (tsikldan farqli) unga kirmagan qirra bilan davom ettirish mumkin. Haqiqatan ham, zanjirda oxirgi uchning darajasi 1 ga teng, lekin graf juft bo’lganligi sababli bu uchga intsident bo’lgan kamida bitta qirra mavjud. Agar graf chekli bo’lsa, zanjirni ketma-ket davom ettirib, avval bosib o’tgan uchlarning biriga kelamiz, ya’ni sodda tsiklni hosil qilamiz. Bu tsiklning barcha qirralarini grafdan olib tashlaymiz. Uning qolgan qismi yana juft grafdir, chunki uchlarning darajalari 2 ga kamayadi (agar undan zanjir o’tsa) yoki o’zgarmaydi (agar zanjir o’tmasa). Bu grafda yana tsiklni ajratamiz va hokazo. Yuqoridagi protsessni yana davom etamiz, toki unda birorta ham tsikl qolmasin (ya’ni bo’sh graf hosil bo’lguncha). SHunday qilib, chekli juft graf o’zaro qirralar bo’yicha kesishmaydigan sodda tsikllar yig’indisiga yoyiladi. Bundan uning barcha qirralari tsiklik ekanligi kelib chiqadi. Agar chekli juft graf bog’liqli bo’lsa, u holda osongina ko’rsatish (sodda tsikllar soni bo’yicha induktsiyani qo’llab) mumkinki unda barcha qirralarini o’z ichiga olgan sodda tsikl mavjud. Bunday tsikl Eyler tsikli, grafning o’zi esa Eyler grafi deyiladi. Yuqorida aytilganlardan quyidagi teorema kelib chiqadi. Teorema. CHekli bog’liqli graf Eyler grafi bo’lishi uchun u juft bo’lishi zarur va yetarli. Istalgan chekli juft grafning har bir bog’liqli komponentasi Eyler grafidir. Ixtiyoriy grafning har qanday ikkita N1 va N2 juft qism graflarining yig’indisi yana juft qism grafdir. Haqiqatan ham, uchning darajasi S() N1+N2 qism grafda 1 2 2 12 s s s ga teng. Bu yerda s1 va s2 uchning mos ravishda N1 va N2 lardagi darajalari, s12 esa ning ularning N1 N2 kesishmasidagi darajasi. SHunday qilib, juft qism graflar to’plami barcha qism graflar fazosining qism fazosidir. Bu qism fazoning o’lchovi ni aniqlaymiz. G bog’liqli, m qirrali, n uchli graf D uning xtiyoriy asosi bo’lsin. Vatarlar soni m n 1 ga teng. Har bir vatar yagona sodda [ , ] D zanjir bilan sodda tsiklni hosil qiladi. Barcha tsikllarning vektorlari bog’liqmas sistemani hosil qiladi. CHunki har bir tsikl sistemaning boshqa tsikllariga tegishli bo’lmagan qirraga (o’zining vatariga) ega. Demak m n 1. Ikkinchi tomondan har qanday juft qism graf, xususiy holda istalgan sodda tsikl sistemaning tsikllari orqali ifodalanadi. Haqiqatan ham juft N qism grafga vatarlari unga tegishli sistemaning tsikllarini qo’shamiz. Hosil bo’lgan yig’indi birorta ham vatarga ega emas. Demak, bu yig’indi D daraxtning qism grafi, ya’ni u bo’sh grafdir. Aks holda sodda tsikllarga ega juft qism graf (N va tsikllarning yig’indisi) daraxtning qism grafi bo’lar edi. Bundan m n 1 kelib chiqadi va yuqoridagi tengsizlikni inobatga olgan holda m n 1. Bog’liqli bo’lmagan k komponentali grafning juft qism graflari fazosining bazisi uning barcha bog’liqli komponentalari bazislarining yig’indisidan iborat. Qirralar va uchlar soni ham komponentalar bo’yicha qo’shiladi.
XULOSA
Men “Graf zanjir, marshrut, sikl tushunchalari. Eyler Gamilton sikllari va graflari.” Mavzusidan ko’p narsalarni va ma’lumotlarni o’rgandim.Bu mavzuda Eyler Gamilton sikllari mavzusi bilan tanishib chiqdim va bu mavzuga doir misollarni domlamiz bilan ko’rib chiqdik.Yana marshrut haqida ham ma’lumotlarga ega bo’ldim.Mavzuda graf zanjiri nima va u qandayligi haqida ko’plab teoremalar bilan tanishib chiqdik va graflar haqidagi ta’riflarni tushunib yod oldik.
Foydalanilgan adabiyotlar:
1. Toʼraev X. Matematik mantiq va diskret matematika. T.: “Oʼqituvchi”, 2003. 2. Sudoplatov S. V., Ovchinnikova Ye. V. Elementii diskretnoy matematiki – M.: «Infra-M», 2002 g. 3. Аseev G.G., Аbramov O.M., Sitnikov D.E. Diskretnaya matematika. – Rostov – na-Donu, «Feniks», 2003 g. 4. Kulabuxov S.Yu. Diskretnaya matematika – Taganrogskiy radiotexnicheskiy universitet, Taganrog, 2001 g. 5. Gavrilov G.P. , Sapojchenko А.А. Zadachii uprajneniya po diskretnoy matematiki.M.:Nauka.2005. 6. Erussalimskiy Ya.M. Diskretnaya matematika teoriya, zadachi, prilojeniya.- M. «Vuzovskaya kniga» , 2002 g. 7. Shaporev S.D. Diskretnaya matematika. Kurs lektsiy i praticheskix zanyatiy. Sankt-Peterburg «BXV- Peterburg» 2009 g. 8. Emelichev V.А., Melnikov O.I., Sarvanov V.I., Tishkevich R.I. Teoriya grafov. M.: «Nauka» 1991. 9. Аbduraxmanova Yu.M., Sadaddinova S.S., Raximova F.S. Diskret matematika,o`quv qo`llanma,Toshkent, “ALOQACHI” nashriyoti, 2014 y. 10. Payzieva M.T., Raximova F.S. Diskret matematikaning graflar nazariyasiga doir uslubiy korsatma,Toshkent, “ALOQACHI” nashriyoti, 2015y. 11. Qalandarov O.N., Abduvaitov X.A. Diskret matematika fanidan oraliq nazoratlari uchun topshiriqlar va ularni bajarish uchun uslubiy korsatmalar, Toshkent, “ALOQACHI” nashriyoti, 2011y. 12. Qalandarov O`.N.,AbduvaitovX.A. matematik mantiq masalalari tatbiqlari va ularni yechish uchun uslubiy ko`rsatmalar. Toshkent, “ALOQACHI” nashriyoti 2012 .
|
| |
