Ma’ruza 4. Grafiklar

4.1.Grafiklar. Grafiklarning ta'rifi, turlari

4.2. Grafiklarning xossalari

Dastur qoidalari

Grafiklar nazariyasiga qiziqish ortib borishining bir qancha sabablari bor. Grafik nazariyasi fizika, kimyo, aloqa nazariyasi, kompyuter dizayni, elektrotexnika, mashinasozlik, arxitektura, operatsiyalarni tadqiq qilish, genetika, psixologiya, sotsiologiya, iqtisod, antropologiya va tilshunoslik kabi sohalarda qo‘llanilishi inkor etilmaydigan haqiqatdir. Bu nazariya, shuningdek, matematikaning ko'pgina tarmoqlari, jumladan, guruhlar nazariyasi, matritsalar nazariyasi, sonli tahlil, ehtimollar nazariyasi, topologiya va kombinatoryal tahlil bilan chambarchas bog'liq. Grafiklar nazariyasi ikkilik munosabatlarga ega bo'lgan har qanday tizim uchun matematik model bo'lib xizmat qilishi ham aniq. Grafiklar diagrammalar sifatida taqdim etilishi tufayli qiziqarli va estetik jihatdan yoqimli. Grafik nazariyasi tabiatan elementar bo'lgan ko'plab natijalarni o'z ichiga olgan bo'lsa-da, u eng murakkab matematiklar e'tiboriga loyiq bo'lgan juda ko'p juda nozik kombinatoryal muammolarni ham o'z ichiga oladi. (F.Xarari “Grafik nazariyasi”)

Amaliy masalalarda grafiklardan keng foydalanish qulayligi va imkoniyatlariga e'tibor bering

Adabiyot

Xavfsizlik masalalari

1. Grafik nima?
2. Grafikning tepasi va cheti nima deyiladi?

3. Ushbu diagrammani qalamni ko'tarmasdan va hech qanday chekkadan ikki marta o'tkazmasdan chizish mumkinmi?

1. Grafik cho'qqilarining darajalari yig'indisi toq son bo'lishi mumkinmi?
2. Har bir jamoa roppa-rosa 5 tadan o‘yin o‘tkazishi uchun 11 ta jamoa o‘rtasida turnir tashkil qilish mumkinmi?

6. 4.1.(6)-banddagi ta'riflarning ekvivalentligini ko'rsating (ular bir xil ob'ektni tavsiflaydi)

7.Grafiklar izomorf ekanligini ko'rsating

8. Grafiklarda izomorfizm ekvivalentlik munosabati ekanligini ko‘rsating.

9. Kub ramka yasash uchun sim bo‘lagini eng kam qancha qismlarga bo‘lish kerak?

10. Grafikning tekis ekanligini ko'rsating

Grafiklar. Grafiklarning ta'rifi, turlari

Grafiklar nazariyasining otasi L. Eyler A707-1782), u 1736 yilda o'sha davrda keng ma'lum bo'lgan, Königsberg ko'priklari muammosi deb nomlangan muammoni hal qildi.

Koenigsberg shahrida Pregolya daryosining qirg'oqlari va bir-biri bilan ettita ko'prik orqali bog'langan ikkita orol bor edi. 4.1.(1) (A,D – orollar, B,C – daryo sohillari). Vazifa quyidagicha edi: quruqlikning barcha to'rt qismidan o'tadigan marshrutni topish, ularning har qandayidan boshlanib, bir qismda tugaydi va har bir ko'prikdan bir martadan o'tadi. Albatta, bu muammoni empirik tarzda hal qilishga urinish, barcha yo'nalishlarni izlash oson, ammo barcha urinishlar muvaffaqiyatsiz tugaydi. L. Eyler bunday marshrutning mumkin emasligini isbotlab, bu muammoning yechimini topishga muvaffaq bo'ldi.

Muammoning yechimi yo'qligini isbotlash uchun Eyler quruqlikning har bir qismini nuqta (cho'qqi) bilan va har bir ko'prikni tegishli nuqtalarni bog'laydigan chiziq (qirra) bilan belgiladi. Natijada "grafik" paydo bo'ladi. Ushbu grafik rasmda ko'rsatilgan. 4.1.(2), bu yerda ball

rasmdagi to'rtta sushi bo'lagi bilan bir xil harflar bilan belgilangan. 4.1(1). Ushbu muammoning "ijobiy" yechimining yo'qligi haqidagi bayonot 1-rasmda keltirilgan grafikni maxsus tarzda kesib o'tishning mumkin emasligi haqidagi bayonotga tengdir. 4.1(2).

Bunday holda, muammo quyidagi formulani oladi: har qanday cho'qqidan boshlab, har bir chekkadan faqat bir marta o'tib, asl cho'qqiga qayting.

Grafik nazariyasi yordamida modellashtirilishi mumkin bo'lgan yana bir muammoning misoli - uchta uyni uchta turdagi kommunal xizmatlar bilan ta'minlash muammosi. Muammoga ko‘ra, uchta uyning har biri er osti quvurlari va kabellar orqali uch turdagi kommunal tarmoqlarga, masalan, suv, gaz va elektr tarmoqlariga ulangan bo‘lishi kerak. Bu uchta uyga ta'minot tarmoqlarini kesib o'tmasdan kommunal xizmatlar ko'rsatish mumkinmi, degan savol tug'iladi. Ushbu muammoni modellashtirish grafigi rasmda ko'rsatilgan. 4.1(3) (Ushbu mashhur model muammosi ba'zan uylar va quduqlar muammosi sifatida shakllantiriladi)

Amaliy xarakterdagi shunga o'xshash muammo mikrosxemalarni yaratishda paydo bo'ladi. Ularda har bir darajadagi simlarni kesib o'tish istalmagan.

Ta'rif 4.1(1)

Grafik chekli V to‘plam bo‘lib, cho‘qqilar to‘plami deb ataladi va V to‘plamning ikki elementli kichik to‘plamlari E to‘plami. E to‘plam qirralar to‘plami deyiladi. E to'plamning elementi chekka deyiladi. Grafik G(V, E) bilan belgilanadi. V to'plamning a va b elementlari bog'langan deb ataladi yoki chekka (a, b), agar bo'lsa.

Boshqacha qilib aytganda, grafik nuqtalardan tashkil topgan diagramma bo'lib, ularning ba'zilari segmentlar bilan bog'langan.

Grafiklarga misollar: metro xaritasi, oila daraxti, yo'l xaritasi va boshqalar.

Ta'riflar 4.1(2)

Agar (a, b) chekka bo'lsa, u holda a va b uchlari chetning uchlari (a, b) deb ataladi. Qirra (a, b) ham deyiladi tasodifiy a va b uchlariga. Aksincha, a va b uchlari chetiga (a, b) tushadi deb aytamiz. Ikki cho'qqi deyiladi qo'shni (qo'shni), agar ular chekka uchlari bo'lsa, yoki bir xil bo'lsa, ular bir xil chekkaga tushsa. Ikki chekka umumiy cho'qqiga to'g'ri keladigan bo'lsa, qo'shni deyiladi.

Ikki nuqta o'rtasida bir nechta qirralarga ruxsat berilsa, grafik chaqiriladi multigraf.

Agar grafikning barcha cho'qqilari qo'shni bo'lsa, grafik deyiladi to'liq.

Bir cho'qqisi bo'lgan va qirralari bo'lmagan (1 nuqtadan iborat - cho'qqi) grafik deyiladi. ahamiyatsiz.

Ta'rif 4.1(3)

V cho'qqisining darajasi deg(v) bilan belgilanadi, ya'ni bu cho'qqiga tushadigan (undan chiqadigan) qirralarning soni.

0 darajali cho'qqi (ya'ni, cho'qqidan hech qanday chekka chiqmaydi, bu "yolg'iz" nuqta) izolyatsiya qilingan deb ataladi.

1-darajali cho'qqi osilgan cho'qqi deyiladi.

Cho'qqilar juft yoki toq bo'lishi mumkin.

Ta'riflar 4.1.(4)

Yo'l (cho'qqilar orasidagi) - ularni bog'laydigan qirralar va oraliq cho'qqilar ketma-ketligi

Yo'l uzunligi - yo'lga kiritilgan qirralarning soni

Oddiy yo'l - barcha qirralari va cho'qqilari aniq bo'lgan yo'l

Tsikl (loop) - nolga teng bo'lmagan uzunlikdagi yopiq yo'l bo'lib, unda boshidan tashqari barcha uchlari farqlanadi va oxiriga to'g'ri keladi.

Misollar 4.1(1).

1. V = (a,b,c) uchlari to‘plami va E (a, b), (b, c)) qirralari to‘plamiga ega bo‘lgan grafik 4.1(4)-rasmda ko‘rsatilganidek tasvirlanishi mumkin (oddiy). ) a va c cho'qqilari orasidagi yo'lga (a,b), (b,c) va c uchlari kiradi

Eslatma: ikkala rasm ham bir xil vaziyatni aks ettiradi. Grafiklar nuqtai nazaridan, birinchi navbatda nuqtalar orasidagi bog'lanishning mavjudligi, uning geometriyasi emas.

2. V = (a,b,c,d,e) va E = ((a, b), (a, e), (b, e), (b, d), (b, c) bo‘lgan grafik. ), (c, d)),

rasmda ko'rsatilgan diagrammada tasvirlanishi mumkin. 4.1.(5). Grafikda ikkita sikl (b, e, a), (b, c, d) mavjud.

3. Rasmda. 4.1.(6) a va c uchlari qo‘shni va e 1, e 2 va e 3 qo‘shni qirralar, a va f uchlari qo‘shni emas, e 2 va e 5 esa qo‘shni qirralar emas. b, c va d cho'qqilari 2 darajaga, a va f uchlari esa 3 darajaga ega.

Keling, Eyler muammosiga qaytaylik. Grafikni kesib o'tishda 2 ta holat mumkin: yo'lning boshi va oxiri bir xil, kirish va chiqish boshqacha. Grafikni mos ravishda ko'rib chiqish uchun (qalamni ko'tarmasdan, hech qanday chekkalarini ikki marta o'tkazib yubormasdan yoki chizmasdan chizmani aylantiring):

Birinchi holda, barcha cho'qqilar teng darajaga ega bo'lishi kerak, ikkinchidan, kirish va chiqishdan tashqari barcha uchlari teng bo'lishi kerak.

Misol 4.1.(2)

Rasmdagi grafik orqali o'tish mumkinmi? 4.1(4), hech qanday chekkadan ikki marta o'tmasdan yoki o'tmasdan?

Barcha cho'qqilarning darajalari juft, 3 darajali c va j cho'qqilardan tashqari. Shunga ko'ra, yagona o'tish yo'li boshi va oxiri c va j uchlari (yoki aksincha) bo'lgan yo'ldir.

Ko'p hollarda sizga chekkalari bir tomonlama ko'cha bo'lgan grafiklar kerak bo'ladi. Bu shuni anglatadiki, agar chekka a cho'qqidan b cho'qqiga o'tish deb hisoblansa, u holda uni b cho'qqidan a cho'qqisiga chiqish deb hisoblash mumkin emas. Misol uchun, grafik quvur liniyasidagi neft oqimini modellashtirsa va neft a nuqtadan b nuqtaga oqib chiqsa, biz uning teskari yo'nalishda, b nuqtadan a nuqtaga oqishini xohlamaymiz.

Ta'rif 4.1(5)

Yo'naltirilgan grafik yoki digraf G, G(V, E) bilan belgilanadigan V cho’qqilar to’plami va Y dan tartiblangan juft elementlarning E to’plamidan iborat bo’lib, agar grafik yo’naltirilganligi aniq bo’lsa, yo’naltirilgan qirralar to’plami yoki oddiygina qirralar deyiladi. E to'plamning elementi yo'naltirilgan chekka deyiladi. Agar , u holda a chetning (a, b) boshlang’ich cho’qqisi deyilsa, b oxirgi cho’qqisi deyiladi.

Misol 4.1(3)

V = (a, b, c, d] va E = ((a, b), (b, c), (c, c), (c, d), (d, b),() bo'lgan digraf. c,d),(d,a)) rasmda ko'rsatilgan.

Ta'rif 4.1.(6)

Keling, daraxt grafigining bir nechta ekvivalent ta'riflarini ko'rib chiqaylik.

1) Bu hech qanday tsiklga ega bo'lmagan bog'langan grafikdir (ulanish xususiyati haqida, 4.2. ga qarang).

2) Har qanday 2 ta uchi oddiy yo'l bilan bog'langan grafik

3) Har qanday chekka olib tashlanganida ulanishni yo'qotadigan bog'langan grafik

4) Qirralari cho'qqilarga nisbatan 1 ta kam bo'lgan grafik

Daraxtlarga misollar:

Etarli darajada rivojlangan oila daraxti daraxt hosil qiladi. Agar siz ma'lum (taniqli) shaxsdan boshlasangiz va har bir ota-ona va har bir o'g'il yoki qiz o'rtasida qirralarni chizsangiz, bu daraxt hosil qiladi. Biroq, oila daraxtini qurishda, uzoq qarindoshlar o'rtasidagi nikoh tsikllarni shakllantirmasligiga katta e'tibor berish kerak.

Grafiklarning xossalari

4.2(1) teorema.

Grafik cho'qqilarining darajalari yig'indisi har doim juft bo'ladi.

Isbot

Grafikning har bir chetining ikkita uchi bo'lganligi sababli, har bir uchining darajasi bir cheti hisobiga 1 ga ortadi. Shunday qilib, har bir chekka barcha cho'qqilarning darajalari yig'indisiga 2 birlik hissa qo'shadi, shuning uchun yig'indi qirralarning sonidan ikki barobar bo'lishi kerak. Shuning uchun yig'indi juft sondir.

4.2.(2) teorema

Har qanday grafikda toq darajali uchlari soni juft.

Isbot

Biz isbotni qarama-qarshilik bilan bajaramiz: teorema to'g'ri emas deb faraz qilsak, biz qarama-qarshilikni topamiz, undan teorema haqiqat ekanligi kelib chiqadi. Agar teorema to'g'ri bo'lmasa, u holda darajalari toq bo'lgan toq sonli uchlari mavjud. Ammo darajalari juft bo'lgan cho'qqilarning darajalari yig'indisi juft. Barcha cho'qqilarning darajalari yig'indisi toq gradusli cho'qqilarning darajalari yig'indisi va juft darajali cho'qqilarning darajalari yig'indisidir. Toq son va juft sonning yig'indisi toq son bo'lgani uchun barcha cho'qqilarning darajalari yig'indisi toq bo'ladi. Ammo bu 4.1(1) teoremaga zid keladi, shuning uchun biz ziddiyatga keldik. Shunday qilib, biz teorema to'g'ri degan xulosaga kelamiz.

Misol 4.2.(1)

Har bir jamoa roppa-rosa 3 tadan o'yin o'tkazishi uchun 7ta jamoa o'rtasida futbol turnirini tashkil qilish mumkinmi?

Yo'q, chunki agar biz 7 ta burchakli grafik tuzsak va har bir cho'qqidan 3 ta chekka chiqarishga harakat qilsak. 4.2(2) teoremaga ko'ra, bunday grafikni qurish mumkin emas.

Ta'rif 4.2(1).

Bir xil tuzilishga ega grafiklar izomorf deyiladi. Ikki grafik G va H izomorf (yoki baʼzan G=H deb yoziladi), agar ularning choʻqqilari toʻplamlari oʻrtasida qoʻshnilikni saqlaydigan birma-bir moslik mavjud boʻlsa. Masalan, shakldagi G va H. 4. 2(2) moslik ostida izomorf .

Boshqacha qilib aytganda, bunday grafiklarning har birining cho'qqilarini shunday raqamlash mumkinki, uning cho'qqilari ikkinchisida qo'shni bo'lgan taqdirdagina qo'shni bo'ladigan tarzda raqamlanishi mumkin.

E'tibor bering, izomorfizm grafiklardagi ekvivalentlik munosabatidir.

Ta'riflar 4.2(2)

Grafik deyiladi izchil, har qanday ikkita cho'qqi o'rtasida yo'l bo'lsa.

Ulanish komponenti- grafikning o'zi bog'langan, lekin u bilan bog'liq bo'lib qolishi uchun kengaytirib bo'lmaydigan qismi

G grafigining x=x(G) bog‘lanish qobiliyati - bu eng kichik cho‘qqilar soni bo‘lib, ularning olib tashlanishi uzilgan yoki ahamiyatsiz grafikga olib keladi. Ta'rifdan kelib chiqadiki, uzilgan grafikning ulanishi 0 ga, tutashuv nuqtasiga ega bo'lgan bog'langan grafikning ulanishi esa 1 ga teng. To'liq grafikni qancha cho'qqi olib tashlanganidan qat'i nazar, uzilgan qilib bo'lmaydi. bu.

GRAFIKLAR

Grafiklar XVIII asrda mashhur matematik Leonhard Eyler Königsberg ko'priklarining hozirgi klassik muammosini hal qilishga uringanida paydo bo'lgan. O'sha paytda Konigsberg shahrida rasmda ko'rsatilganidek, Pregol daryosi qirg'og'iga va bir-biriga ettita ko'prik bilan bog'langan ikkita orol bor edi. 7.1. Vazifa quyidagilardan iborat: shahar bo'ylab shunday yurish kerakki, har bir ko'prikdan bir marta o'tib, piyoda boshlangan joyga qaytasiz. Bu masalani yechishda Eyler Koenigsbergni grafik sifatida tasvirlab, uning uchlarini shahar qismlari bilan, chekkalarini esa bu qismlarni bog‘lovchi ko‘priklar bilan aniqladi. § 7.1 da ko'rsatamizki, Eyler shahar bo'ylab kerakli marshrut mavjud emasligini isbotlay oldi.

7.1-rasm. Eski Koenigsberg sxemasi

Ushbu bobda biz grafiklar nazariyasida qo'llaniladigan standart terminologiya bilan tanishamiz va grafiklar yordamida hal qilinishi mumkin bo'lgan bir nechta maxsus muammolarni ko'rib chiqamiz. Xususan, biz daraxtlar deb nomlangan grafiklar sinfi bilan tanishamiz. Daraxtlar ierarxik tizimda tashkil etilgan ma'lumotlarni ifodalovchi tabiiy modeldir. Alohida elementlarni ajratib olish uchun daraxt qidirish va daraxtdagi ma'lumotlarni saralash informatika fanida muhim harakatlardir. Ushbu bobning ilovasida biz daraxtlarga ajratilgan ma'lumotlarni saralash va qidirishni ko'rib chiqamiz.

Grafiklar va terminologiya

Shaklda. 7.1 Königsbergning ettita ko'prigini shunday ko'rsatadi. ular XVIII asrda qanday joylashganligi. Eyler ko'rib chiqqan muammo shunday savol tug'diradi: har bir ko'prikdan bir marta o'tadigan va shaharning bir joyidan boshlanib, tugaydigan piyoda marshrutini topish mumkinmi?

Vazifa modeli grafik, ko'pdan iborat cho'qqilari va ko'p qovurg'alar uchlarini ulash. A, B, C cho'qqilari va D daryo va orollarning qirg'oqlarini va qovurg'alarni ramziy qiladi a, c, c,d,f Va g etti ko'prikni ifodalaydi (7.2-rasmga qarang). Kerakli marshrut (agar u mavjud bo'lsa) grafikning chetlarini ularning har biri faqat bir marta bosib o'tadigan tarzda kesib o'tishga mos keladi. Qovurg'aning o'tishi, shubhasiz, daryoning ko'prik orqali o'tishiga to'g'ri keladi.

7.2-rasm. Königsberg ko'prigi muammosi modeli

Marshrut mavjud bo'lgan, bir xil cho'qqidan boshlanuvchi va tugaydigan va grafikning barcha qirralari bo'ylab aynan bir marta o'tadigan marshrut mavjud bo'lgan grafik deyiladi. Seiler grafigi. Istalgan marshrut, xuddi marshrutning o'zi kabi o'tadigan cho'qqilar ketma-ketligi (ehtimol takrorlashlar bilan) deyiladi. Eyler tsikl. Eyler, agar grafikda Eyler sikli mavjud boʻlsa, u holda qaysidir choʻqqiga olib boruvchi har bir chekka uchun bu choʻqqi 1dan chiqadigan yana bir chekka boʻlishi kerakligini payqagan va bu oddiy kuzatishdan u quyidagi xulosaga kelgan: agar grafada Eyler sikli mavjud boʻlsa. berilgan grafik , keyin har bir cho'qqi teng sonli qirralarga ega bo'lishi kerak.

Bundan tashqari, Eyler qarama-qarshi fikrni isbotlay oldi, shuning uchun har qanday uchlari juftligi qandaydir qirralarning ketma-ketligi bilan bog'langan grafik, agar uning barcha uchlari juft darajaga ega bo'lsa, Eyler hisoblanadi. Daraja uchlari v d(v) raqami deyiladi. qovurg'alar, uning voqea 2 .

Endi ko'rinib turibdiki, Königsberg ko'prigi muammosini modellashtirish grafigida Eyler siklini topib bo'lmaydi. Darhaqiqat, uning barcha cho'qqilarining darajalari g'alati: δ(B) = d(C)= d(D) = 3 va δ(A) = 5. Eyler yordamida koʻpriklar masalasini yechishda biz oʻrgangan grafiklarga oʻxshash grafiklar koʻplab amaliy masalalarni yechishda qoʻllanila boshlandi va ularni oʻrganish matematikaning muhim sohasiga aylandi.

Oddiy grafik G = (V,) juftligi sifatida aniqlanadi. E), bu yerda V - chekli cho'qqilar to'plami, va E- chekli qirralar to'plami va ularni o'z ichiga olmaydi halqalar(qirralar bir xil cho'qqida boshlanadigan va tugaydigan) va bir nechta qirralar(bir nechta qirralar - bir xil juft uchlarni bog'laydigan bir nechta qirralar). Shaklda ko'rsatilgan grafik. 7.2. oddiy emas, chunki, masalan, uchlari A Va IN ikkita qirra bilan bog'langan (bu qirralar ko'p deb ataladi).

Ikki cho'qqi u Va v oddiy grafikda deyiladi qo'shni, agar ular qandaydir chekka bilan bog'langan bo'lsa e, ular bu haqida aytishadi tasodifiy cho'qqi u (va v ). Shunday qilib, biz ko'p narsalarni tasavvur qilishimiz mumkin E qirralarning qo'shni cho'qqilar juftligi to'plami sifatida, shu bilan to'plamda refleksiv bo'lmagan, simmetrik munosabatni aniqlaydi. V. Reflektorning yo'qligi oddiy grafikda ilmoqlar, ya'ni qirralarning yo'qligi, ularning ikkala uchi bir xil cho'qqida joylashganligi bilan bog'liq. O'zaro munosabatlarning simmetriyasi chekka ekanligidan kelib chiqadi e, cho'qqisini ulash Va Bilan v, bog'laydi va v Bilan Va(boshqacha aytganda, qirralari yo'naltirilmagan, ya'ni ularning yo'nalishi yo'q). Bir juft cho'qqini bog'laydigan oddiy grafikdagi bitta chekka u Va v, deb belgilaymiz va v(yoki vi).

Grafikning qirralari bilan aniqlangan cho'qqilar to'plamidagi munosabatlarning mantiqiy matritsasi deyiladi. , qo'shnilik matritsasi. M qo'shnilik matritsasi nuqtai nazaridan munosabatning simmetriyasi M asosiy diagonalga nisbatan simmetrik. Va M matritsasining asosiy diagonalidagi bu munosabatlarning refleksivligi tufayli "L" belgisi mavjud.

7.1-misol. G(V, E) grafigini chizing uchlari to'plami bilan V = (a, b, c, d, e) va E qirralari to'plami = (ab, ae, bc, bd, ce, de). Uning qo'shnilik matritsasini yozing.

Yechim. Grafik G rasmda ko'rsatilgan. 7.3.

7.3-rasm.

Uning qo'shnilik matritsasi quyidagi ko'rinishga ega:

Grafikni tiklash uchun bizga faqat asosiy diagonaldan yuqori bo'lgan qo'shni matritsaning elementlari kerak.

Subgraf grafik G = (V, E) grafik G’ = (V’, E’) deyiladi, unda E’ C E va V’ C V.

7.2-misol Rasmda ko'rsatilgan H, K va L grafiklardan toping. 7.4, G grafikning kichik bandlari.

Yechim. G, H va K grafiklarning uchlarini rasmda ko'rsatilganidek belgilaymiz. 7.5. Bizning yozuvimizdan ko'rinib turibdiki, H va K grafiklari G ning pastki grafalaridir. L grafigi G ning pastki grafigi emas, chunki u 4 indeksli tepaga ega, G esa yo'q.

Marshrut uzunligi k G grafigida shunday cho'qqilar ketma-ketligi deyiladi v 0 , v 1 , …, v k , har bir i = 1, …, k juftlik uchun v i – 1 v i grafikning chetini hosil qiladi. Biz bunday marshrutni bilan belgilaymiz v 0 v 1 … v k . Masalan, 1 4 3 2 5 - 7.2-misoldagi G grafikdagi 4 uzunlikdagi marshrut.

G H

K L

7.4-rasm.

Velosiped grafikda cho'qqilar ketma-ketligini chaqirish odatiy holdir v 0 , v 1 , … , v k , ularning har bir jufti bir chekkaning uchlari va v 0 = v 1 , va qolgan uchlari (va qirralari) takrorlanmaydi. Boshqacha qilib aytadigan bo'lsak, tsikl - bu uning har bir uchi va chekkasidan faqat bir marta o'tadigan yopiq marshrutdir

1 2 1 2 3

7.5-rasm

7.3-misol. 7.2-misoldan G grafikdagi sikllarni toping.

Yechim. Ushbu grafikda 5 uzunlikdagi ikki xil tsikl mavjud:

1 3 2 5 4 1 va 1 2 5 4 3 1

Biz tsiklning o'zboshimchalik bilan yuqorisidan boshlab, bu tsikllarni bir yo'nalishda yoki boshqa yo'nalishda o'tkazishimiz mumkin. Bundan tashqari, grafik 4 uzunlikdagi uch xil tsiklga ega:

1 2 5 4 1, 1 2 3 4 1 va 2 5 4 3 2,

va uzunligi 3 bo'lgan ikkita halqa:

1 2 3 1 va 1 3 4 1.

Tsikllari bo'lmagan grafik deyiladi asiklik. Hisoblashda paydo bo'ladigan daraxt tuzilmalari asiklik grafiklarning alohida holatidir. Biz ular bilan ushbu bobda keyinroq gaplashamiz.

Hisob, chaqirildi izchil, agar uning cho'qqilarining biron bir jufti qandaydir marshrut bilan bog'langan bo'lsa. Har qanday umumiy grafik subgraflarga bo'linishi mumkin, ularning har biri bog'langan bo'lib chiqadi. Bunday ulangan komponentlarning minimal soni deyiladi ulanish raqami grafik va bilan belgilanadi c(G) . Ulanish masalalari grafik nazariyasini kompyuter tarmoqlariga tatbiq etishda muhim ahamiyatga ega. Grafikning ulanish raqamini aniqlash uchun quyidagi algoritm qo'llaniladi.

Ulanish algoritmi.

G = (V, E) grafik bo‘lsin. Algoritm qiymatni hisoblash uchun mo'ljallangan c = c(G), bular. berilgan grafikning bog'langan komponentlari soni G.

V' :=V;

esaV’≠ øqilmoq

y Ê ni tanlang V’

Marshrutni y ga tutashtiruvchi uchlarini toping;

dan tepalikni olib tashlangV' Va

E dan mos keladigan qirralar;

c:= c+1;

7.4-misol. Rasmda ko'rsatilgan grafikda ulanish algoritmining ishlashiga qarang. 7.6.

7.6-rasm.

Yechim. Jadvalga qarang. 7.1.

7.1-jadval.

Dastlabki qiymatlar	{1,2,3,4,5,6,7,8}
Tanlov y = 1
Tanlov y = 2
Tanlov y = 7

Shunday qilib, c(G) = 3. Tegishli ulangan komponentlar rasmda ko'rsatilgan. 7.7.

5

Asosiy savollar:

Grafiklar tarixidan ma'lumotlar. Hisoblash va
uning elementlari.
Grafiklardagi yo'llar va marshrutlar
Bog'langan grafikalar. Daraxtlar
Grafiklar ustida amallar.

Grafik nazariyasi
ega bo'lgan matematikaning bo'limi
keng amaliy dasturlar.
Grafik nazariyasi - maydon
diskret matematika,
qaysi xususiyat
o'rganishga geometrik yondashuv
ob'ektlar.

Grafiklar tarixi

Birinchi marta grafik nazariyasi asoslari
Leonardning asarlarida paydo bo'lgan
Eyler (1707-1783;
Shveytsariya, nemis va
rus matematigi)
u yechimni tasvirlab berdi
jumboq va matematika
ko'ngilochar vazifalar.
Grafik nazariyasi bilan boshlangan
Eyler tomonidan muammoning yechimi
etti ko'prik
Koenigsberg.

Quyidagi topishmoq uzoq vaqtdan beri Königsberg aholisi orasida keng tarqalgan:
barcha ko'priklarni (Pregolya daryosi bo'ylab) hech qanday kesib o'tmasdan qanday o'tish kerak
ulardan ikki marta? Ko'pchilik bu muammoni nazariy jihatdan ham, ham hal qilishga harakat qildi
amalda, yurish paytida. Lekin hech kim muvaffaqiyatga erisha olmadi, lekin yo'q
Bu hatto nazariy jihatdan mumkin emasligini isbotlash mumkin edi.
Qismlarning soddalashtirilgan diagrammasida
shahar (tuman) ko'priklar
chiziqlarga mos keladi (yoylar
soni) va shahar qismlari -
chiziqli ulanish nuqtalari
(grafikning uchlari).
Mulohaza yuritish jarayonida Eyler o'ziga keldi
quyidagi xulosalar: o'tish mumkin emas
barcha ko'priklardan hech biriga o'tmasdan
ularni ikki marta.

Grafiklar tarixi

"Grafik" atamasi birinchi marta kitobda paydo bo'lgan
1936 yilda venger matematigi D. Koenig, garchi
grafiklar haqidagi dastlabki eng muhim teoremalar
L. Eyler sahifasiga qaytish.

Nazariya grafik tushunchasiga asoslanadi.

- chekli sonlar to'plami
nuqtalar grafaning uchlari deb ataladi va
bularning ba'zilarini juftlik bilan bog'laydi
qirralar yoki deb ataladigan chiziqlarning uchlari
grafik yoylari. Ba'zan butun grafik
bitta bosh harf bilan belgilanishi mumkin
xat.
G V , X ikkita juftlik deyiladi
chekli to'plamlar: V nuqtalar to'plami va
X chiziqlar to'plami (qirralar, yoylar),
ba'zi juft nuqtalarni ulash.

Grafikning tarkibi

Grafik chiziqlar bilan bog'langan cho'qqilardan iborat. Cho'qqilar
ustun A, B, C, D yoki lotin harflari bilan belgilanadi
raqamlarda.
Yo'naltirilgan chiziq (o'q bilan) yoy deb ataladi.
Yo'nalishsiz chiziq (o'qsiz) chekka deyiladi.
Muayyan cho'qqidan chiqib, a kiruvchi chiziq
u halqa deb ataladi.
yoy
A
chekka
IN
halqa
BILAN

Yo'naltirilgan grafik -

cho'qqilari yoylar bilan bog'langan grafik. BILAN
Bunday grafiklar yordamida tasvirlash mumkin
bir tomonlama munosabatlar sxemalari.
Yura
Anya
Masha
Kolya
Vitya

Og'irlangan grafik

Bu qirralari yoki yoylari tayinlangan grafik
raqamli qiymatlarga mos keladi (ular mumkin
masalan, shaharlar orasidagi masofani ko'rsating
yoki transport xarajatlari).
Grafikning og'irligi uning qirralari og'irliklarining yig'indisiga teng.
4
B
C
2
3
2
A
1
E
D
A
B
C
D
E
A B C D E
3 1
4
2
3 4
2
1
2 2
jadval (bu vazn jadvali deb ataladi)
matritsa) grafikga mos keladi.

Agar
Grafikning G cheti uning ikkitasini bog'laydi
uchlari V va W, (ya'ni V , W X), keyin ular aytadilar
bu chekka ular uchun tasodifiy ekanligini.
Grafikning ikkita cho'qqisi qo'shni deyiladi,
unga chekka hodisa bo'lsa: on
rasmda A va B cho'qqilari qo'shni,
A va S.
A
BILAN
IN

Agar G grafigining boshi cheti bo'lsa
va oxiri mos keladi, keyin bu chekka deyiladi
halqa. Rasmda chekka q(C, C) halqadir.
q
E
BILAN
A
D
B

Ikki chekka, agar ular qo'shni bo'lsa, deyiladi
umumiy uchi bor.
Rasmda qo'shni, masalan,
qirralarning x1 va x2 umumiy uchi C.
D
x5
x1
F
BILAN
x4
x2
G
x7
x3
E
x6
B
H
A

Bir va ichida boshlanadigan qovurg'alar
bir xil cho'qqi, xuddi shu tarzda tugaydi
bir xil cho'qqidagilar deyiladi
ko'p yoki parallel.
Turdagi bir xil juftliklar soni
(V , Vt) chekkaning ko'pligi (V , Vt) deyiladi.
A cho'qqisiga tushadigan qirralarning soni
bu cho'qqining darajasi va deyiladi
deg(A) bilan belgilanadi (inglizcha darajadan -
daraja).

Rasmda ko'paytmalar, masalan,
qirralarning x1 (A, B), x2 (A, B). A va C cho'qqilari
x3, x4, x5 qirralari tushdi. Demak,
chekka AC ko'pligi 3 ga va chekkaga ega
AB - ko'plik 2 ga teng.
A
x4
x1
x3
BILAN
x2
x5
IN

Rasmda A tepasi darajaga ega
1 ga teng, cho'qqisi C - 4, cho'qqisi D - 2.
Bu quyidagicha yoziladi: deg(A)=1, deg(C)=4,
deg(D)=2.
D
x5
x1
F
BILAN
x4
x2
G
x7
x3
E
x6
B
H
A

Grafikning nol darajasiga ega cho'qqisi
izolyatsiya qilingan deb ataladi.
Izolyatsiya qilingan uchlardan tashkil topgan grafik
null grafik deb ataladi.
Grafikning 1 darajali cho'qqisi
osish deb ataladi.
Qirralari (yoylari) bo'lmagan grafik deyiladi
bo'sh.
E
C
A
D
B
Rasmda tepada
E - izolyatsiyalangan:
deg(E)=0.

Rasmda A, B, E, G, H cho'qqilari kulondir.
D
x5
x1
F
BILAN
x4
x2
G
x7
x3
E
x6
B
H
A

Teorema 1. Grafikda G V , X yig'indisi
uning barcha uchlari darajalari juft son,
grafik qirralari sonining ikki barobariga teng:
n
daraja(V) 2m
men 1
i
Har qanday grafikdagi qirralarning soni teng
uning uchlari darajalari yig'indisining yarmi.
qaerda n V
- uchlari soni;
m X - grafikning qirralari soni.

Cho'qqi juft (toq) deb ataladi,
agar uning darajasi juft (toq) son bo'lsa.
Rasmda deg(D)=2, deg(F)=3, bu degani
Grafikning D cho'qqisi juft, F esa
g'alati.
x5
D
x1
F
BILAN
x4
x2
G
x7
x3
E
x6
B
H
A

Vazifa. Malenkiy shahrida 15 ta telefon mavjud. Har bir telefon aniq beshga ulangan bo'lishi uchun ularni simlar bilan ulash mumkinmi?

boshqalar?

Teorema 2. Har qanday (yo'naltirilmagan)
grafik juft sonni o'z ichiga oladi
cho'qqilari
Natija. U bilan grafik chizish mumkin emas
toq cho'qqilarning toq soni.
Grafik G to'liq deb ataladi,
agar ikkitasi boshqacha bo'lsa
uchlari bitta va bilan bog'langan
faqat bitta chekka.

Vazifa. Sinfda 30 kishi bor. 9 kishining 3 ta, 11 kishining 4 ta, 10 kishining 5 ta doʻsti boʻlishi mumkinmi?

Grafikning to'ldiruvchisi G V , X deyiladi
grafigi G V , X bir xil uchlari V bilan
grafigi G va faqat shu va faqat X qirralarga ega,
Buni G grafigiga qo'shish kerak, shunda u
to‘la bo‘ldi. Rasmda G1 grafigini qo'shish orqali
Grafik G - bu grafik
G1
G
G1
G1

Shakl 1.
Shakl 2.
Verteks darajalari
Darajalar yig'indisi
to'liq grafik
bir xil, va
ularning har biri 1 ta
kamroq raqam
buning tepalari
grafik
grafik uchlari soni
teng, teng
raqamni ikki baravar oshiring
grafik qirralari. Bu
naqsh
adolatli emas
faqat to'liq uchun
balki hamma uchun ham
grafik.

Shakl 3.
Shakl 4.
G'alati soni
Mumkin emas
har qandayning uchlari
ustun tekis.
bilan grafik chizing
toq raqam
g'alati uchlari.

Shakl 5.
Shakl 6.
Agar barcha uchlari bo'lsa
Hammasi bilan grafik
u holda ustun juft bo'ladi
uni yirtib tashlamasdan mumkin
qog'oz qalam
("bir zarba bilan"),
har birini surish
faqat bir marta qovurg'a,
ushbu grafikni chizing.
Harakat qilish mumkin
har qandayidan boshlang
tepalar va tugatish
u xuddi shu cho'qqida.
ikkita g'alati
cho'qqilar, mumkin
chizish, emas
qalamni yirtib tashlash
qog'ozdan, esa
harakat zarur
biri bilan boshlang
bu g'alati
tepalar va tugatish
ulardan ikkinchisida.

Shakl 7.
Ko'proq narsaga ega bo'lgan grafik
ikkita g'alati
cho'qqilar, mumkin emas
chizish "bir
gullab-yashnashi bilan." Rasm
(grafik), bo'lishi mumkin
ko'tarmasdan chizish
qog'oz qalam,
chaqirdi
unikursal.

Grafiklardagi yo'llar va marshrutlar

Yo'naltirilgan grafikdagi yo'l deyiladi
final bo'lgan yoylar ketma-ketligi
oxirgisidan boshqa har qanday yoyning tepasi,
keyingi yoyning boshlang‘ich cho‘qqisi hisoblanadi.
Marshrut yotqizilgan cho'qqi,
yo'lning boshi deb ataladi, tepasi oxirida
marshrut - yo'lning oxiri.
Har bir cho'qqi ishlatiladigan yo'l
bir martadan ko'p bo'lmagan, oddiy deb ataladi
yo'l.
Grafikdagi yo'lning uzunligi yoylar soni
bu yo'lni tashkil etuvchi (qirralar).

Misol sifatida, digrafni ko'rib chiqing
rasmda keltirilgan. Mavjudlardan biri
1 va 3 uchlarini bog'lovchi yo'llar
1, 2, 1, 4, 3 uchlari ketma-ketligi. Yagona
bir xil juft cho'qqilar uchun oddiy yo'l
ketma-ketlik 1, 4, 3. 1-cho'qqigacha bo'lgan yo'llar
5-vertex bir xil grafik uchun mavjud emas.

Yo'naltirilmagan grafik deyiladi
kamida bitta yo'l bo'lsa ulanadi
har bir juft cho'qqi o'rtasida.
Digraf bog'langan bo'lsa, bog'langan deyiladi
yo'naltirilmagan grafik
asl yo'naltirilganidan olinadi
barcha yoylarni qirralar bilan almashtirish.

Yo'l agar yopiq deb ataladi
boshlang'ich va oxirgi uchlari bir xil.
Yopiq yo'l, agar hammasi bo'lsa, tsikl deb ataladi
uning uchlari (boshlang'ich va oxirgilardan tashqari)
har xil.
Grafikni ko'rib chiqing. Uning uchun yo'l 2, 1, 6, 5, 4, 1,
2 yopiq; va yo'l 1, 6, 5, 4, 1
sikldir.

Qo'shni juftliklar ketma-ketligi
yo'naltirilmagan grafikning uchlari, ya'ni.
qirralarning ketma-ketligi
yo'naltirilmagan grafik, unda ikkinchisi
bilan oldingi chekkaning tepasi mos keladi
keyingisining birinchi uchi deyiladi
marshrut.
Marshrutdagi qirralarning soni uzunlik deb ataladi
marshrut.
Agar marshrutning boshlang'ich cho'qqisi mos kelsa
oxirgi bilan, keyin bunday marshrut deyiladi
yopiq yoki pastadir.

Rasmda HCDFD 4 uzunlikdagi marshrutdir.
Belgilanishi: |HCDFD|=4. Marshrut qabul qilindi
so'rang
Qanaqasiga
keyingi ketma-ketlik
qovurg'alar,
chunki bu ko'paytmalar bo'lganda qulay
qovurg'alar
X
D
x1
5
F
BILAN
x4
x2
G
x7
x3
E
x6
B
H
A

Rasmdagi grafikda (t, s, p, r), (u, s, t, r) sikllar
uzunligi 4, (r, t, q, s, u) – sikl uzunligi 5, (t, s, u, r, t, s, p, r)
– 8 davrli, (p, u) – 2 davrli, halqa (q) – 1 davr.
E
q
C
s
A
p
t
D
r
B
u

Grafiklar ustida amallar

Yagona operatsiyalar
1. Grafikning chetini olib tashlash - bu holda, grafikning barcha uchlari
saqlanadi
2. Ikkisi orasiga grafik chetini qo'shish
mavjud cho'qqilar.
3. Cho'qqini o'chirish (hodisalar bilan birga
qovurg'alar).
4. Cho'qqi qo'shish (u bilan bog'lanishi mumkin
grafikning ba'zi uchlari).
5. Qirraning qisqarishi - bir juft tepalikni aniqlash, ya'ni.
bir juft qo'shni cho'qqilarni olib tashlash va yangisini qo'shish
bo'lgan cho'qqilarga ulashgan cho'qqilar
uzoq cho'qqilarning kamida bittasiga ulashgan)
6. Chetni bo‘laklarga bo‘lish - chetini olib tashlash va qo‘shish
har biriga chekka bilan bog'langan yangi cho'qqi
uzoq chekkaning uchlari.

Grafiklar ustida amallar

Ikkilamchi operatsiyalar
G1 (V1, X 1) va G2 (V2, X 2) grafiklarini birlashtirish orqali
Grafik G G1 G2 deb ataladi, cho'qqilar to'plami
qaysi V V1 V2, va qirralarning to'plami X X 1 X 2.
G1 va G2 grafiklarining kesishishi deyiladi
grafigi G G1 G2 buning uchun X X 1 X 2 qirralar to'plami, V V1 V2 esa cho'qqilar to'plamidir.
Ikki grafikning halqa yig'indisi grafik deyiladi
G G1 G2 cho'qqilar to'plami tomonidan yaratilgan
bular.
V V1 V2 va qirralar to'plami (X1 X 2) \ (X1 X 2) ,
G1 yoki ichida joylashgan qirralarning to'plami
G2, lekin G1 G2 da emas.

V4
V2
x3
x2
V3
x4
V1
x1
V5
x2
x7
x3
x4
x4
V1
x7
V1
G=G1UG2
V3
x4
V5
x2
V1
x3
G=G1∩G2
V2
x1
G2
V4
V2
x5 x6
x6
V3
V1
V4
V3
V4
x5
x3
x1
G1
V2
V5
V2
V4
x5 x6V
3
x7
G=G1 G2

Grafiklarni qo'llash

BILAN
yordami bilan
grafiklar
soddalashtirilgan
matematik masalalar, boshqotirmalar,
zukkolik.
yechim
uchun vazifalar
yana

Grafiklarni qo'llash

Labirint - bu grafik. Va uni o'rganish - uni topishdir
Ushbu grafikdagi yo'l.
yana

Grafiklardan foydalanadi va
zodagonlik.
Rasmda ko'rsatilgan
genealogiyaning bir qismi
daraxt
mashhur
zodagon oila L.N.
Tolstoy. Mana
cho'qqilar buning a'zolaridir
mehribon va ularni bog'laydiganlar
segmentlar - munosabatlar
qarindoshlik,
ota-onadan olib boradi
bolalar.
yana

Grafiklarni qo'llash

Grafiklar - bu dasturlarning blok diagrammasi
KOMPYUTER.
yana

Grafiklarni qo'llash

Oddiy grafiklar yoqilgan
geografik xaritalar
temir yo'l rasmlari.
yana

Grafiklarni qo'llash

Shahar xaritalaridagi odatiy grafiklar
shahar transporti shakllari
transport.
yana

Xulosa

Grafiklar ajoyib matematik
siz hal qilishingiz mumkin bo'lgan ob'ektlar
matematik, iqtisodiy va mantiqiy
vazifalar. Shuningdek, siz turli xil muammolarni hal qilishingiz mumkin
boshqotirmalar va ko'ra vazifalarni shartlarini soddalashtirish
fizika, kimyo, elektronika, avtomatlashtirish. Grafiklar
ishlatiladi
da
chizish
kart
Va
genealogik daraxtlar.
Hatto matematikada maxsus bo'lim ham mavjud
"Grafik nazariyasi" deb ataladi.
mazmuni

To'liq uzilgan grafiklar . Ko'p qirralari bo'sh bo'lgan grafik deyiladi juda mos kelmaydigan(yoki bo'sh) grafik. To'liq uzilgan grafikni n ta burchakli N n bilan belgilaymiz; N 4 rasmda ko'rsatilgan. 1. Shuni esda tuting da butunlay uzilgan grafikning barcha uchlari ajratilgan. To'liq uzilgan grafiklar alohida qiziqish uyg'otmaydi.

To'liq grafikalar . Har qanday ikkita cho'qqi qo'shni bo'lgan oddiy grafik deyiladi to'liq grafik. n ta burchakli to'liq grafik odatda bilan belgilanadi. Grafiklar va rasmda ko'rsatilgan. 2 va 3. aniq n (n - 1)/2 chekkaga ega.

Oddiy grafiklar . Barcha uchlari bir xil darajaga ega bo'lgan grafik deyiladi muntazam grafik. Agar har bir cho'qqining darajasi r bo'lsa, u holda grafik deyiladi muntazam daraja r. 3-darajali muntazam grafiklar, shuningdek, deyiladi kub(yoki uch valentli) grafiklar (masalan, 2 va 4-rasmga qarang). Kub grafigining yana bir mashhur misoli bu deyiladi graf Petersen, shaklda ko'rsatilgan. 5. E'tibor bering, har bir to'liq uzilgan grafik 0 daraja regulyar, har bir to'liq grafik K n esa n - 1 daraja regulyardir.

Platonik grafiklar . Muntazam grafiklar orasida Platonik grafiklar deb ataladigan grafiklar ayniqsa qiziq - beshta muntazam ko'pyoqlamaning uchlari va qirralari tomonidan hosil qilingan grafiklar - Platonik qattiq jismlar: tetraedr, kub, oktaedr, dodekaedr va ikosahedr. Grafik tetraedrga mos keladi (2-rasm); kub va oktaedrga mos keladigan grafiklar rasmda ko'rsatilgan. 5 va 6;

Ikki tomonlama grafiklar . Faraz qilaylik, grafikning cho'qqilari to'plamini ikkita ajratilgan V 1 va V 2 kichik to'plamlarga bo'lish mumkin, shunda G ning har bir chekkasi V 1 dan qandaydir cho'qqi bilan V 2 dan qandaydir cho'qqi bilan bog'laydi (7-rasm);

u holda G ikki tomonlama grafik deyiladi. Bunday grafiklar ba'zan G (V 1, V 2) deb belgilanadi, agar ikkita ko'rsatilgan kichik to'plamni ajratmoqchi bo'lsa. Ikki tomonlama grafik boshqa yo'l bilan ham aniqlanishi mumkin - uning uchlarini ikkita rang bilan bo'yash nuqtai nazaridan, masalan, qizil va ko'k. Grafik ikki qismli deb ataladi, agar uning har bir uchi qizil yoki ko'k rangga bo'yalgan bo'lsa, har qanday chekkaning bir uchi qizil va ikkinchisi ko'k bo'lishi mumkin. Shuni ta'kidlash kerakki, ikki tomonlama grafikda V 1 dan har bir cho'qqi V 2 dan har bir cho'qqi bilan bog'lanishi shart emas; agar shunday bo'lsa va G grafigi oddiy bo'lsa, u deyiladi to'liq ikki tomonlama grafik va odatda bu erda m, n mos ravishda V 1 va V 2 cho'qqilari soni bilan belgilanadi. Misol uchun, rasmda. 8 da K 4, 3 grafigi ko'rsatilgan. E'tibor bering, grafikning aniq m + n uchlari va mn qirralari bor. Shaklning to'liq ikki tomonlama grafigi yulduzli grafik deb ataladi; rasmda. 9 yulduzli grafikni ko'rsatadi.

Bog'langan grafikalar . Grafik ulangan, agar uni ikkita grafikning birlashmasi sifatida tasvirlash mumkin bo'lmasa va mos kelmaydigan aks holda. Shubhasiz, har bir uzilgan grafik G chekli sonli bog'langan grafiklarning birlashmasi sifatida ifodalanishi mumkin - bunday bog'langan grafiklarning har biri deyiladi. komponent (ulanish) grafik G. (10-rasmda uchta komponentli grafik ko'rsatilgan.) Ko'pincha ixtiyoriy grafiklar uchun ma'lum bayonotlarni bog'langan grafiklar uchun avval isbotlash va keyin ularni har bir komponentga alohida qo'llash qulay.

"Izolyatsiya qilingan" cho'qqilardan tashkil topgan grafik diagramma deyiladi nol grafik. (2-rasm)

Barcha mumkin bo'lgan qirralari tuzilmagan grafiklar deyiladi to'liq bo'lmagan grafiklar. (3-rasm)

Barcha mumkin bo'lgan qirralar tuzilgan grafiklar deyiladi to'liq grafiklar. (4-rasm)


Agar grafikning chetlarida qirralarning yo'nalishini ko'rsatadigan o'qlar mavjud bo'lsa, unda bunday grafik deyiladi. yo'naltirilgan.

Rasmda ko'rsatilgan grafikdagi bir ishdan ikkinchisiga o'q ishlarning ketma-ketligini bildiradi.

Tugatishni boshlash uchun poydevor qurishni tugatmasdan devorlarni o'rnatishni boshlay olmaysiz, zaminlarda suv bo'lishi kerak va hokazo.

Cho'qqilarning darajalari va qirralarning sonini hisoblash.

Grafikning tepasidan chiqadigan qirralarning soni cho'qqining darajasi deb ataladi. Grafikning toq darajaga ega bo'lgan cho'qqisi toq deyiladi, juft darajaga ega bo'lgan cho'qqi esa juft deyiladi.

Agar grafikning barcha cho'qqilarining darajalari teng bo'lsa, u holda grafik deyiladi bir hil. Shunday qilib, har qanday to'liq grafik bir hil bo'ladi.

5-rasmda beshta burchakli grafik ko'rsatilgan.

A cho'qqi darajasini St.A deb belgilaymiz.

Rasmda:
St.A = 1, St.B = 2, St.B = 3, St.G = 2, St.D = 0.

Keling, ma'lum grafiklarga xos bo'lgan ba'zi qonuniyatlarni shakllantiraylik.

Shakl 1. To'liq grafikning cho'qqilarining darajalari bir xil va ularning har biri ushbu grafikning uchlari sonidan 1 ga kam.

Shakl 2. Grafik cho'qqilarining darajalari yig'indisi - bu grafik qirralari sonining ikki barobariga teng bo'lgan juft son.

Bu naqsh faqat to'liq grafik uchun emas, balki har qanday grafik uchun ham to'g'ri keladi.

Har qanday grafikdagi toq uchlari soni juft.

E'tibor bering, agar to'liq grafik n ta uchga ega bo'lsa, unda qirralarning soni n (n-1)/2 ga teng bo'ladi.

To'liq bo'lmagan grafikni etishmayotgan qirralarni qo'shish orqali bir xil uchlari bilan to'ldirish uchun to'ldirish mumkin. Misol uchun, 3-rasmda beshta cho'qqi bilan to'liq bo'lmagan grafik ko'rsatilgan. 4-rasmda grafikni to`liq grafikga aylantiruvchi qirralar boshqa rangda tasvirlangan, bu qirralar bilan grafikning uchlari yig`indisi grafikning to`ldiruvchisi deyiladi;

Eyler grafiklari.

Qog'ozdan qalamni ko'tarmasdan chizish mumkin bo'lgan grafik deyiladi Eyler. (6-rasm)

Bu grafiklar olim nomi bilan atalgan Leonhard Eyler.


Shakl 3.(biz ko'rib chiqqan teoremadan kelib chiqadi).
Toq sonli toq burchakli grafik chizish mumkin emas.

Shakl 4. Agar grafikning barcha cho'qqilari juft bo'lsa, siz qalamni qog'ozdan ko'tarmasdan ("bitta zarba bilan") har bir chekka bo'ylab faqat bir marta harakatlanmasdan ushbu grafikni chizishingiz mumkin. Harakat har qanday cho'qqidan boshlanib, bir xil cho'qqida tugashi mumkin.

Shakl 5. Qog'ozdan qalamni ko'tarmasdan faqat ikkita toq uchi bo'lgan grafik chizish mumkin va harakat shu toq uchlardan birida boshlanib, ikkinchisida tugashi kerak.

Shakl 6. Ikkidan ortiq toq uchlari boʻlgan grafikni chizib boʻlmaydi. bir zarba bilan».

Qog'ozdan qalamni ko'tarmasdan chizish mumkin bo'lgan rasm (grafik) deyiladi unikursal.

Grafik deyiladi izchil, agar uning istalgan ikkita uchini yo'l bilan bog'lash mumkin bo'lsa, ya'ni har biri oldingisining oxiridan boshlanadigan qirralarning ketma-ketligi.

7-rasmda uzilgan grafik aniq ko'rsatilgan.

Grafik deyiladi mos kelmaydigan, agar bu shart bajarilmasa.

Agar, masalan, rasmda D va E cho'qqilari orasiga chekka chizilgan bo'lsa, u holda grafik bog'langan bo'ladi.( 8-rasm)

Grafik nazariyasida bunday chekka (o'chirilgandan so'ng grafik ulangandan uzilganga aylanadi) deyiladi. ko'prik.

Ko'priklarga misollar 7-rasm qirralarning DE, A3, VZh va boshqalar xizmat qilishi mumkin, ularning har biri grafikning "izolyatsiya qilingan" qismlarining uchlarini bog'laydi. ( 8-rasm)

Ajratilgan grafik bir nechta "dan iborat. dona" Ushbu "bo'laklar" grafikning bog'langan komponentlari deb ataladi. Har bir bog'langan komponent, albatta, bog'langan grafikdir. E'tibor bering, bog'langan grafik bitta bog'langan komponentga ega.

Grafik, agar u bog'langan bo'lsa va ko'pi bilan ikkita toq uchi bo'lsa, Eylerian hisoblanadi.

Daraxtlar.

daraxt Hech qanday tsiklga ega bo'lmagan har qanday bog'langan grafik deyiladi.

Velosiped boshi va oxiri bir-biriga to‘g‘ri keladigan yo‘ldir.

Agar tsiklning barcha uchlari boshqacha bo'lsa, unda bunday tsikl deyiladi boshlang'ich(yoki oddiy) tsikl.

Agar tsikl grafikning barcha qirralarini bir marta o'z ichiga olsa, unda bunday tsikl deyiladi Eyler liniyasi (9a-rasm).

Yon ustunda 9b-rasm ikki davr: 1-2-3-4-1 va 5-6-7-5.

tomonidan bir cho'qqidan ikkinchisiga o'tadigan grafikda qirralarning ketma-ketligi mavjud bo'lib, ular bo'ylab ushbu cho'qqilar orasiga marshrut qo'yish mumkin.

Bunday holda, marshrutning hech qanday chekkasi bir necha marta paydo bo'lmasligi kerak. Marshrut yotqizilgan cho'qqi deyiladi sayohatning boshlanishi, marshrut oxiridagi cho'qqi - yo'lning oxiri.

osilgan tepa aynan bir cheti chiqadigan cho'qqi ( 10-rasm).
(osilgan cho'qqilar aylana bilan o'ralgan).


Daraxt cho'qqilarining har bir jufti uchun ularni bog'laydigan o'ziga xos yo'l mavjud.

Bu xususiyat shajarada barcha ajdodlarni, masalan, nasl-nasabi shajara ko'rinishida ifodalangan har qanday shaxsning erkak naslida topilganda qo'llaniladi. daraxt"va grafik nazariyasi ma'nosida.

Daraxtning har bir chekkasi ko'prikdir.

Darhaqiqat, daraxtning biron bir chetini olib tashlaganingizdan so'ng, u " parchalanadi"Ikki daraxtda.

Har qanday ikkita cho'qqi aynan bitta oddiy yo'l bilan bog'langan grafik daraxt.

(osilgan tepa haqida). Har bir daraxtning osilgan tepasi bor.

. Daraxtda uchlari soni qirralarning sonidan bittaga ko'p.

Izomorfizm. Planar grafiklar va Eyler teoremasi.

Ikkita grafik deyiladi izomorf, agar ular teng sonli uchlarga ega boʻlsa va har bir grafikning uchlarini 1 dan n gacha raqamlash mumkin boʻlsa, birinchi grafikning uchlari chekka bilan bogʻlanadi, agar ikkinchi grafning mos choʻqqilari bogʻlangan boʻlsa. chekka.

11-rasmda keltirilgan grafiklar izomorf ekanligini isbotlaylik.


Birinchi va ikkinchi grafiklarning uchlarini 1 dan 4 gacha raqamlaymiz ( 12-rasm).


Birinchi grafik 1 va 2, 2 va 3, 3 va 4, 1 va 4, 1 va 3, 2 va 4 uchlarini bog'laydi; E'tibor bering, ikkinchi grafikda 1 va 2, 2 va 3, 3 va 4, 1 va 4, 1 va 3, 2 va 4 uchlari ham bog'langan, shuning uchun bu grafiklar izomorfdir.

Ikkita grafik izomorf yoki yo'qligini bilish uchun ular borligiga ishonch hosil qilishingiz kerak:

• bir xil miqdordagi uchlari
• Agar bitta grafning uchlari chekka bilan bog'langan bo'lsa, boshqa grafning mos keladigan uchlari ham chekka bilan bog'lanadi.

Qirralari faqat cho'qqilardan boshqa joyda kesishmaydigan qilib chizilishi mumkin bo'lgan grafik deyiladi. tekis yoki tekislik.

Eyler. To'g'ri chizilgan bog'langan planar grafik uchun u tenglikka ega: V-E+F=2, bu erda V - uchlari soni, E - qirralarning soni, F - bo'laklar soni (V -E+ tengligi F=2 odatda Eyler formulasi deb ataladi).

Har bir cho'qqi boshqa har bir cho'qqining chetiga bog'langan grafik deyiladi to'liq.

Pontryagin - Kuratovskiy. Grafik, agar u (topologik ma'noda) "uy-quduq" tipidagi oltita uchli grafik va beshta uchli to'liq grafikni o'z ichiga olmasa, tekis bo'ladi.

(Asosan, uylar va quduqlar haqidagi qadimiy muammolarda qo'llaniladi, ularning mohiyati savolga aniqlik kiritish uchun mo'ljallangan - ko'rib chiqilayotgan grafik tekis yoki yo'qmi? 13-rasm)

Yo'naltirilgan grafiklar.

Ilgari muhokama qilingan grafik turlaridan foydalangan holda hal qilib bo'lmaydigan amaliy masalalarning muhim sinflari mavjud.

Masalan, shaharning yo'llari va maydonlari xaritasi tekis grafik yordamida tasvirlangan. Ammo agar siz ushbu sxemadan shahar bo'ylab avtomobilda sayohat qilishingiz kerak bo'lsa va ba'zi (yoki barcha) ko'chalarda harakatlanish bir tomonlama bo'lsa-chi?

Keyin, masalan, to'g'ridan-to'g'ri chekkalarda - ko'rib chiqilayotgan shahar diagrammasi (grafigi) ko'chalarida joylashgan o'qlar bu vaziyatni boshqarishga yordam beradi.

Chetlarida strelkalar bo'lgan grafik deyiladi yo'naltirilgan.

Chiqish darajasi Yo'naltirilgan grafikning cho'qqisi - bu tepa boshi bo'lgan qirralarning soni (qirralar soni, " chiqadi"yuqoridan).

Kirish darajasi Yo'naltirilgan grafikning cho'qqisi - bu uchi oxiri bo'lgan qirralarning soni (qirralar soni, " kiruvchi"tepaga).

Ha, yoqilgan 15-rasm yo'naltirilgan ABCD grafigini ko'rsatadi. Uning ba'zi cho'qqilarining kirish va chiqish darajalari quyidagicha:
St.in.A=2, St.out.A=1 St.in.B=2, St.out.B=0 St.in.D=1, St.out.D=3.

A1 cho'qqidan An cho'qqigacha yo'naltirilgan grafikdagi yo'l - bu yo'naltirilgan A1A2, A2A3, ..., An-1An qirralarning ketma-ketligi bo'lib, unda har bir oldingi chekkaning oxiri keyingisining boshiga to'g'ri keladi va har bir chekka quyidagicha bo'ladi. bu ketma-ketlik faqat bir marta.

Yoniq rasm.15 yo'naltirilgan grafikdagi yo'llarning misollari ko'rsatilgan. Bundan tashqari, dastlabki ikkita yo'l oddiy - hech bir cho'qqi unda bir necha marta mavjud emas. Uchinchi yo'l oddiy emas, ya'ni. G cho'qqisi orqali yo'lga. o'tdi"ikki marta.

Yo'naltirilgan tsikl yo'naltirilgan grafikda yopiq yo'l deyiladi.

Yoniq 15-rasm Yo'naltirilgan sikllarga misollar oxirgi ikki grafikda keltirilgan. Grafikdagi boshqa har qanday yo'l kabi tsikl ham shu yo'ldagi qirralarning soni bilan belgilanadigan uzunlikka ega.

Shunday qilib, 16-rasmda A dan D gacha bo'lgan yo'llar har xil bo'lishi va turli uzunliklarga ega bo'lishi mumkin.
Birinchi yo'lning uzunligi 2, ikkinchisi - 3,
uchinchisi esa 4 ta.

Ikki cho'qqi orasidagi "eng qisqa yo'l" uzunligi ular orasidagi masofa deb ataladi. Demak, 16-rasmdagi grafikdagi A va D uchlari orasidagi masofa 2 ga teng; quyidagicha yoziladi: S(BP)=2.

Agar yo'naltirilgan grafikda bir cho'qqidan ikkinchisiga "o'tish" mumkin bo'lmasa, ular orasidagi masofa cheksiz deb ataladi (cheksizlik belgisi bilan ko'rsatilgan). Shunday qilib, 17-rasmda keltirilgan grafikning B va D uchlari orasidagi masofa cheksizdir: S(DB) = ∞

Iqtisodiyotda yo'naltirilgan grafiklar tarmoqni rejalashtirishda, matematikada - o'yinlar nazariyasida, to'plamlar nazariyasida faol qo'llaniladi; ko'p muammolarni, xususan, kombinatsion muammolarni hal qilishda.