Digrafning cho'qqilari uchun erishish mumkinligi munosabati. Digraflar va binar munosabatlar
Mayli V- yo'naltirilgan grafikning uchlari to'plami F, E- uning ko'p qirralari. Har bir qovurg'a eÎ E boshlanishi bor v'Î V va oxiri v''Î V. Shunday qilib, j 1 va j 2 ikkita xaritalash berilgan, bu erda v'=j 1 ( e) - qovurg'aning boshlanishi e, v''=j 2 ( e) - qovurg'aning oxiri e.
Bir nechta ta'riflarni berish mumkin yo'llari digrafda F.
1. Cho'qqilar va qirralarning yo'li- bu ketma-ketlik L(v 0 ,e 1 ,v 1 ,e 2 ,...,e n,vn), Qayerda v i- 1 =j 1 ( e i), v i=j 2 ( e i). Vertex v 0 deyiladi yo'lning boshlanishi L, cho'qqi vn - yo'lning oxiri L, raqam n qovurg'alar - uning uzunligi. Bitta tepadan iborat yo'l nolga teng uzunlikka ega.
2. Qirralarning yo'li ketma-ketlik ( e 1 ,e 2 ,...,e n). Yo'lning bu tushunchasi yo'naltirilmagan grafikdagi marshrut tushunchasiga o'xshashdir.
3. Cho'qqilardan yo'l ketma-ketlik ( v 0 ,v 1 ,...,vn). Bir nechta qirralari bo'lmagan grafiklar uchun cho'qqilardan yo'l aniqlanadi.
Amalda siz berilgan aniq vazifa uchun qulayroq bo'lgan yo'l ta'rifidan foydalanishingiz mumkin.
Yo'l deyiladi yo'naltirilgan zanjir(yoki oddiygina zanjir, faqat digraflar hisobga olinganda), agar har bir chekka unda 1 martadan ko'p bo'lmagan holda sodir bo'lsa va oddiy yo'naltirilgan zanjir, agar grafikning har bir tepasi F uning ko‘pi bilan ikkita chetiga to‘g‘ri keladi.
Misol. Yo'l ( e 5 ,e 6 ,e 7 ,e 1 ,e 4 ,e 3) (3.11-rasm) yoki.zanjir, va yo'l ( e 7 ,e 1 ,e 4 ,e 3) - oddiy op. zanjir.
| Guruch. 3.11. |
Yo'l deyiladi yo'naltirilgan tsikl(yoki oddiygina tsikl, faqat digraflar hisobga olinganda) agar u bir nechta elementlardan iborat bo'lsa va uning boshlanishi oxiriga to'g'ri kelsa. Yo'naltirilmagan grafikda bo'lgani kabi, tsiklning boshlanishi odatda aniqlanmaydi. Tsikl deyiladi oddiy, agar unga tegishli bo'lgan har bir cho'qqi uning to'liq ikkita chetiga tushsa.
Misol. Yo'l ( e 1 ,e 4 ,e 3 ,e 2 ,e 5 ,e 6 ,e 7) - tsikl, yo'l ( e 5 ,e 6 ,e 7) - oddiy tsikl.
Yo'naltirilgan zanjirlar bilan bog'liq holda, kvadrat maydonlarni o'rganishda Redei tomonidan isbotlangan teorema haqiqiydir.
Teorema 3.3. Mayli F- chekli digraf, unda har bir juft cho'qqi chekka bilan bog'langan. Keyin ichkariga F uning barcha cho'qqilari orqali o'tadigan oddiy yo'naltirilgan yo'l bor.
ÿ MI usuli yordamida isbotlashni amalga oshiramiz. Grafikning uchlari sonini bilan belgilaymiz n.
· n=2: grafikning ikkita uchini birlashtiruvchi yoy F 2 va grafikning barcha uchlari orqali o'tadigan oddiy yo'naltirilgan yo'l mavjud.
· Faraz qilaylik, qachon n= m grafik uchun Fm teorema to'g'ri.
· Qachon ekanligini isbotlaylik n= m Hisob uchun +1 Fm+1 teorema to'g'ri.
Keling, grafik tuzamiz Fm Grafikga qo'shish orqali +1 Fm qandaydir cho'qqi v m+1 , uning barcha cho'qqilariga qirralari bor v i (i=1,2,...,m) dan Fm. Taxminlarga ko'ra, grafikning barcha uchlari orqali o'tadigan oddiy yo'naltirilgan yo'l bor Fm: P m=(v 1 ,v 2 ,...,v m). Bir cho'qqiga tushadigan qirralar uchun v m+1, uchta imkoniyat mavjud.
1. yoy bor ( v m +1, v 1). Uni zanjirga qo'shish P m"chapda" biz grafikning barcha uchlari orqali o'tadigan kerakli zanjirni olamiz Fm +1: P m +1 =(v m +1 ,v 1 ,v 2 ,...,v m).
2. yoy bor ( v m , v m+1). Uni zanjirga qo'shish P m"O'ngda" biz grafikning barcha uchlari orqali o'tadigan kerakli zanjirni olamiz Fm +1: P m +1 =(v m +1 ,v 1 ,v 2 ,...,v m,v m +1).
3. Agar ustunda bo'lsa Fm+1 yoy yo'q ( v m +1 ,v 1), yoy yo'q ( v m,v m+1), keyin ba'zilari uchun k (k=2,3,...,m-1) unda albatta yoylar bo'ladi ( vk,v m+1) va ( v m +1 ,vk+1). Keling, zanjir yasaymiz
P m +1 =(v 1 ,v 2 ,...,vk,v m +1 ,vk +1 ,...,v m).
Bu zanjir grafikning barcha cho'qqilaridan o'tadi Fm +1 .
Ko'p cho'qqilarda V munosabatni belgilaymiz erishish imkoniyati R D quyidagicha: Yuqori v'Î V munosabatda bo‘ladi R D tepa bilan v''Î V(bu holda ular yuqori deb aytishadi v'' kirish mumkin tepadan v'), agar yo'l bo'lsa L(v',... ,v'') boshlanishi bilan v' va oxiri v''.
Yo'naltirilmagan grafikning uchlari uchun bog'lanish munosabatiga o'xshash munosabat erishish imkoniyati yo'naltirilgan grafikning uchlari uchun refleksli ravishda Va tranzitiv tarzda, lekin bog'lanish munosabatidan farqli o'laroq, erisha olish munosabati nosimmetrik bo'lishi shart emas.
Rivojlanish munosabatidan foydalanib, digrafning uchlari to'plamining ekvivalentlik sinflariga bo'linishi aniqlanadi: cho'qqilar v', v'' agar munosabat nosimmetrik bo'lsa, bir xil sinfga tegishli, ya'ni. v'' dan erishish mumkin v', A v' dan erishish mumkin v''.
Mayli L 1 (v', ... ,v'') Va L 2 (v'', ... ,v') bu cho'qqilarni bog'laydigan mos keladigan yo'llardir. Keyin ular birgalikda cho'qqilardan o'tadigan tsiklni hosil qiladilar v' Va v''. Shunday qilib, bir xil ekvivalentlik sinfining har qanday uchlari qandaydir tsiklga tegishli. Agar grafikda tsikllar bo'lmasa, u holda har bir ekvivalentlik sinfi bitta tepadan iborat.
| Guruch. 3.13. |
Minimal grafik F B, cho'qqilar to'plamida induktsiya V berilgan yo'naltirilgan grafik bilan bir xil erishish mumkinligi munosabati F, ya'ni. chekkalarining yana qaytarilmas to'plamiga ega bo'lgan grafik deyiladi asosiy grafik grafik uchun F.
Agar bazaviy grafik mavjud bo'lsa, u yagona bo'lishi shart emas. Shunday qilib, rasmdagi grafik uchun. 3.13, har qanday radial chekka va yo'naltirilgan ko'pburchak sikl bazis grafigini belgilaydi.
Agar F chekli digraf bo'lsa, bazis grafiklari mavjud; ularni "ortiqcha" qirralarni ketma-ket olib tashlash orqali olish mumkin ( v 0 ,vn), buning uchun cheksiz ( v 0 ,vn) yo'naltirilgan zanjir R(v 0 ,vn).
Qabul qilish imkoniyati grafigi
Grafiklarni o'rganishda paydo bo'ladigan birinchi savollardan biri bu berilgan yoki barcha cho'qqilar juftlari orasidagi yo'llarning mavjudligi masalasidir. Bu savolga javob G=(V,E) grafigining cho'qqilarida yuqorida keltirilgan erishish mumkin bo'lgan munosabatdir: agar v = w yoki G ning v dan w gacha bo'lgan yo'li bo'lsa, w cho'qqisiga v cho'qqisidan chiqish mumkin. Boshqacha qilib aytadigan bo'lsak, erisha olish munosabati E munosabatining refleksiv va o'tishli yopilishidir. Yo'naltirilmagan grafiklar uchun bu munosabat ham simmetrikdir va shuning uchun V cho'qqi to'plamidagi ekvivalentlik munosabati hisoblanadi. Yo'naltirilmagan grafikda ekvivalentlik sinflari bilan. erishish mumkin bo'lgan munosabatga bog'liq komponentlar deyiladi. Yo'naltirilgan grafiklar uchun erishish mumkinligi, umuman olganda, nosimmetrik munosabat bo'lishi shart emas. O'zaro erishish nosimmetrikdir.
Ta'rif 9.8. Yo‘naltirilgan G=(V,E) grafining v va w cho‘qqilari o‘zaro yetib borish mumkin deyiladi, agar G dan v dan w ga yo‘l va w dan v gacha bo‘lgan yo‘l bo‘lsa.
Ko'rinib turibdiki, o'zaro erishish munosabatlari refleksli, simmetrik va o'tishli va shuning uchun grafikning cho'qqilari to'plamidagi ekvivalentdir. O'zaro erishishga nisbatan ekvivalentlik sinflari kuchli bog'langan komponentlar yoki deyiladi ikki tomonlama bog'langan komponentlar grafik.
Keling, avvalo erishish mumkin bo'lgan munosabatlarni qurish masalasini ko'rib chiqaylik. Keling, har bir grafik uchun uning erishish mumkin bo'lgan grafigini (ba'zan o'tish yopilish grafigi deb ham ataladi) aniqlaylik, uning qirralari asl grafikning yo'llariga mos keladi.
Ta'rif 9.9. G=(V,E) yo‘naltirilgan grafik bo‘lsin. G uchun erishish imkoniyati grafigi G * =(V,E *) bir xil V cho'qqilar to'plamiga va keyingi qirralar to'plamiga ega E * =( (u, v) | G grafigida, v cho'qqi u cho'qqisidan chiqish mumkin) .
9.3-misol. 9.2-misoldagi G grafigini ko'rib chiqing.
Guruch. 9.2. Grafik G
Keyin biz G* uchun erishish imkoniyati grafigi quyidagicha ko'rinishini tekshirishimiz mumkin (1-5 cho'qqilarning har biri uchun yangi pastadir qirralari ko'rsatilmagan):
Guruch. 9.3. Grafik G*
G grafikdan G * grafigini qanday qurish mumkin? Buning usullaridan biri G grafigining har bir cho'qqisi uchun undan chiqish mumkin bo'lgan cho'qqilar to'plamini aniqlash, unga ketma-ket 0, 1, 2 va hokazo uzunlikdagi yo'llar orqali erishish mumkin bo'lgan cho'qqilarni qo'shishdir.
G grafigining A G qo'shnilik matritsasi va mantiqiy amallardan foydalanishga asoslangan boshqa usulni ko'rib chiqamiz. Cho'qqilar to'plami V=(v 1 , … , v n ) bo'lsin. U holda A G matritsasi n × n mantiqiy matritsadir.
Quyida matritsalar ustidagi oddiy amallar bilan oʻxshashlikni saqlab qolish uchun biz mantiqiy amallar uchun “arifmetik” yozuvdan foydalanamiz: diszyunksiyani belgilash uchun + va birikmani belgilash uchun foydalanamiz.
n × n o‘lchamdagi o‘ziga xoslik matritsasini E n bilan belgilaymiz. Keling, qo'ying 
. Bizning G * ni qurish tartibi quyidagi bayonotga asoslansin.
Lemma 9.2. Mayli. Keyin
Isbot Keling, buni k bo'yicha induksiya orqali bajaramiz.
Asos. k=0 va k=1 uchun bayonot va taʼrifi boʻyicha toʻgʻri boʻladi.
Induksiya bosqichi. Lemma k uchun to'g'ri bo'lsin. Uning k+1 uchun amal qilishini ko'rsataylik. Ta'rifga ko'ra bizda:
Faraz qilaylik, G grafikda v i dan v j gacha uzunligi k+1 bo‘lgan yo‘l bor. Keling, ushbu yo'llarning eng qisqasini ko'rib chiqaylik. Agar uning uzunligi k bo'lsa, u holda induksion gipoteza bo'yicha a_(ij)^((k))=1. Bundan tashqari, jj (1) =1. Shuning uchun a ij (k) a jj (1) =1 va a ij (k+1) =1. Agar v i dan v j gacha bo'lgan eng qisqa yo'lning uzunligi k+1 bo'lsa, u holda v r uning oxirgi uchi bo'lsin. U holda v i dan v r gacha uzunligi k va induksiya gipotezasiga ko'ra a ir (k) =1 bo'lgan yo'l bor. Chunki (v r ,v j) E, u holda a_(rj)^((1))=1. Shuning uchun a ir (k) a rj (1) =1 va a ij (k+1) =1.
Aksincha, agar a ij (k+1) =1 bo'lsa, u holda kamida bitta r uchun a ir (k) a rj (1) yig'indisi 1 ga teng. Agar bu r=j bo'lsa, a ij (k) = 1 va induktiv gipotezaga ko'ra, G uzunligi k bo'lgan v i dan v j gacha bo'lgan yo'lga ega. Agar r j bo'lsa, a ir (k) =1 va rj (1) =1. Demak, G ning v i dan v r gacha uzunligi k va qirrasi (v r ,v j) E. Ularni birlashtirib, k+1 uzunlikdagi v i dan v j gacha bo‘lgan yo‘lni olamiz.
Lemmalar 9.1 va 9.2 dan biz to'g'ridan-to'g'ri olamiz
Xulosa 1. G=(V,E) n ta uchli yo‘naltirilgan grafik va G * uning erisha olish grafigi bo‘lsin. Keyin A_(G*) =. Isbot. 5.1-Lemmadan kelib chiqadiki, agar G ning u dan v ugacha bo'lgan yo'li bo'lsa, u holda u dan v gacha bo'lgan n-1 uzunlikdagi oddiy yo'lni ham o'z ichiga oladi. Va Lemma 5.2 bo'yicha, barcha bunday yo'llar matritsada ifodalanadi.
Shunday qilib, G uchun erishish mumkin bo'lgan grafigining A G* qo'shnilik matritsasini qurish tartibi matritsani n-1 quvvatga ko'tarishgacha qisqartiriladi. Keling, ushbu protsedurani soddalashtirish uchun bir nechta sharhlarni beramiz.
bu yerda k eng kichik son, shundayki 2 k n.
Agar a ir = 1 va rj =1 bo'ladigan r topilsa, butun yig'indi a ij (2) =1 bo'ladi. Shuning uchun qolgan shartlarni e'tiborsiz qoldirish mumkin.
9.3-misol. Misol tariqasida, G grafigida keltirilgan A G* erishish mumkin bo'lgan grafigining matritsasini hisoblashni ko'rib chiqamiz. 9.2-rasm. Ushbu holatda
G ning 6 ta uchi borligi sababli, . Keling, ushbu matritsani hisoblaymiz:
va (oxirgi tenglikni tekshirish oson). Shunday qilib,
Ko'rib turganimizdek, bu matritsa haqiqatan ham taqdim etilgan grafikni aniqlaydi 9.3-rasm.
O'zaro qulaylik, kuchli bog'langan komponentlar va grafik asoslar
Erish imkoniyati grafigiga o'xshab, biz kuchli erishish grafigini aniqlaymiz.
Ta'rif 9.10. G=(V,E) yo‘naltirilgan grafik bo‘lsin. G uchun kuchli erishish mumkinligi grafigi G * * =(V,E * *) bir xil V uchlari to'plamiga va keyingi E * * =( (u, v) | grafigida V va u uchlari to'plamiga ega. o'zaro erishish mumkin).
Erish imkoniyati grafigining matritsasidan foydalanib, kuchli erishish grafigining matritsasini qurish oson. Darhaqiqat, erishish va kuchli erishish ta'riflaridan darhol shuni ko'rsatadiki, barcha (i,j), 1 i,j n juftliklari uchun elementning qiymati 1 ga teng, agar ikkala element ham A G* (i, j) va A G bo'lsa. * (j, i) 1 ga teng, ya'ni.
Matritsaga asoslanib, G grafikning kuchli bog’langan komponentlarini quyidagicha aniqlashimiz mumkin.
K 1 uchi v 1 va barcha uchlarini v j komponentiga shunday joylashtiramizki, A_(G_*^*)(1,j) = 1.
K 1, …, K i va v k komponentlari allaqachon tuzilgan bo'lsin - bu komponentlarga hali kiritilmagan minimal sonli cho'qqi. Keyin K_(i+1) komponentiga v k uchini va shu kabi barcha uchlarini v j ,
bu A_(G_*^*)(k,j) = 1.
Barcha tepaliklar komponentlar o'rtasida taqsimlanmaguncha (2) qadamni takrorlaymiz.
Bizning misolimizda G grafigi uchun 2-rasm matritsadan biz kuchli erishish grafigining quyidagi matritsasini olamiz
Yuqorida tavsiflangan protseduradan foydalanib, G grafigining uchlari kuchli bog'lanishning 4 ta komponentiga bo'linganligini aniqlaymiz: K 1 = (v 1, v 2, v 3), \ K 2 =( v 4), \ K 3 =( v 5), \ K 4 =( v 6). Kuchli bog'langan komponentlar to'plamida biz erishish imkoniyatini ham aniqlaymiz.
Ta'rif 9.11. K va K" grafigining kuchli bog'langan komponentlari bo'lsin. K komponent dan erishish mumkin K^\prime komponentlari, agar K= K" yoki ikkita u K va v K" uchlari mavjud bo'lsa, u v dan kirish mumkin. K dan qat'iy erishish mumkin K^\prime agar K K" va K bo'lsa, K" dan kirish mumkin. K komponenti deyiladi eng kam, agar unga biron bir komponentdan qat'iy erishib bo'lmasa.
Bitta komponentdagi barcha cho'qqilar o'zaro erishish mumkin bo'lganligi sababli, komponentlarga erishish va qat'iy erishish munosabatlari u K va v K uchlarini tanlashga bog'liq emasligini tushunish oson."
Ta'rifdan qat'iy erishishning quyidagi xususiyati osongina chiqariladi.
Lemma 9.3. Qattiq erisha olish munosabati qisman tartib munosabati, ya'ni. u anti-refleks, anti-simmetrik va tranzitivdir.
Bu munosabatni cho'qqilari komponentlar bo'lgan yo'naltirilgan grafik sifatida ko'rsatish mumkin va chekka (K, K) K ga K dan qat'iy ravishda erishish mumkinligini anglatadi. Yoniq guruch. 9.4 ushbu komponent grafigi yuqorida ko'rib chiqilgan G grafik uchun ko'rsatilgan.
Guruch. 9.4.
Bunday holda, bitta minimal komponent K 2 mavjud.
Ko'pgina ilovalarda yo'naltirilgan grafik ma'lum bir manbaning tarqatish tarmog'ini ifodalaydi: mahsulot, tovarlar, ma'lumotlar va boshqalar. Bunday hollarda ushbu resurs tarmoqning istalgan nuqtasiga etkazilishi mumkin bo'lgan bunday nuqtalarning (cho'qqilarning) minimal sonini topish vazifasi tabiiy ravishda paydo bo'ladi.
Ta'rif 9.12. G=(V,E) yo‘naltirilgan grafik bo‘lsin. W V cho'qqilarning kichik to'plami deyiladi hosil qiluvchi, agar grafikning istalgan cho'qqisiga V ning cho'qqilaridan chiqish mumkin bo'lsa. W V cho'qqilar to'plami, agar u yaratayotgan bo'lsa, uning asosi deyiladi, lekin uning tegishli pastki to'plami hosil bo'lmasa.
Quyidagi teorema bizga grafikning barcha asoslarini samarali topish imkonini beradi.
9.1 teorema. G=(V,E) yo‘naltirilgan grafik bo‘lsin. W V cho'qqilar to'plami G ning har bir minimal kuchli bog'langan komponentidan bitta cho'qqi bo'lsa va boshqa cho'qqilarni o'z ichiga olmasa, G ning asosi hisoblanadi.
Isbot Avvalo shuni ta'kidlaymizki, grafikning har bir cho'qqisiga qandaydir minimal komponentga tegishli cho'qqidan chiqish mumkin. Shunday qilib, har bir minimal komponentdan bitta cho'qqi bo'lgan W cho'qqilar to'plami hosil bo'ladi va undan biron bir cho'qqi olib tashlanganida, u shunday bo'lishni to'xtatadi, chunki mos keladigan minimal komponentning cho'qqilariga etib bo'lmaydi. Shuning uchun W asosdir.
Aksincha, agar W asos bo'lsa, u har bir minimal komponentdan kamida bitta cho'qqisini o'z ichiga olishi kerak, aks holda bunday minimal komponentning cho'qqilariga kirish imkoni bo'lmaydi. W boshqa cho'qqilarni o'z ichiga olmaydi, chunki ularning har biriga allaqachon kiritilgan tepalardan kirish mumkin.
Bu teoremadan G grafigining bittasini qurish yoki barcha asoslarini sanab o‘tish uchun quyidagi tartib kelib chiqadi.
G.ning barcha kuchli bogʻlangan komponentlarini toping.
Ulardagi tartibni aniqlang va ushbu tartibga nisbatan minimal komponentlarni tanlang.
Har bir minimal komponentdan bitta cho'qqini tanlab, grafikning bir yoki barcha asoslarini yarating.
9.5-misol. Keling, G da ko'rsatilgan yo'naltirilgan grafikning barcha asoslarini aniqlaymiz 9.5-rasm.
Guruch. 9.5. Grafik G
Birinchi bosqichda biz G ning kuchli bog'langan komponentlarini topamiz:
Ikkinchi bosqichda biz ushbu komponentlar bo'yicha qat'iy erishish grafigini tuzamiz.
Guruch. 9.6. G. komponentlari boʻyicha erisha olish munosabatlari grafigi
Minimal komponentlarni aniqlaymiz: K 2 = ( b ), K 4 = ( d, e, f, g) va K 7 = ( r).
Nihoyat, G ning barcha to‘rtta asosini sanab o‘tamiz: B 1 = ( b, d, r), B 2 = ( b, e, r), B 3 = ( b, f, r) va B 1 = ( b, g, r) .
Vazifalar
Muammo 9.1. Ixtiyoriy yo‘naltirilgan grafikning barcha uchlari darajalari yig‘indisi juft ekanligini isbotlang.
Bu muammoning mashhur talqini bor: buni isbotlang umumiy soni Ziyofatga kelgan odamlar o'rtasida har doim qo'l siqishlar soni teng bo'ladi.
Muammo 9.2. Ko'pi bilan to'rtta cho'qqiga ega bo'lgan barcha izomorf bo'lmagan yo'naltirilmagan grafiklarni sanab o'ting.
Muammo 9.3. Yo'naltirilmagan bog'langan grafik qaysidir chekka olib tashlangandan keyin ham bog'langanligini isbotlang ↔ bu chekka qandaydir tsiklga tegishli.
Muammo 9.4. n ta burchakli yo'naltirilmagan bog'langan grafik ekanligini isbotlang
kamida n-1 qirralarni o'z ichiga oladi,
agar u n-1 dan ortiq qirralarni o'z ichiga olsa, u kamida bitta tsiklga ega.
Muammo 9.5. 6 kishidan iborat har qanday guruhda uch juft tanish yoki uch juft notanish odam borligini isbotlang.
Muammo 9.6. Yo'naltirilmagan grafik G=(V,E) har bir V= V 1 V 2 bo'lim uchun ↔ bo'sh bo'lmagan V 1 va V 2 bilan V 1 ni V 2 ga tutashtiruvchi chekka mavjudligini isbotlang.
Muammo 9.7. Yo'naltirilmagan grafikning to'g'ridan-to'g'ri ikkita toq darajali uchi bo'lsa, ular yo'l bilan bog'langanligini isbotlang.
Muammo 9.8. G=(V,E) |E| bilan yo‘naltirilmagan grafik bo‘lsin< |V|-1. Докажите, что тогда G несвязный граф.
Muammo 9.9. Bog'langan yo'naltirilmagan grafikda har qanday ikkita ekanligini isbotlang oddiy usullar maksimal uzunlikdagilar umumiy uchiga ega.
Muammo 9.10. G=(V,E) halqasiz yo‘naltirilmagan grafikda k ta bog‘langan komponent bo‘lsin. Keyin buni isbotlang
Muammo 9.11. Erish imkoniyati grafigi nima uchun ekanligini aniqlang
n ta uchli va boʻsh qirralar toʻplamiga ega grafik;
n ta uchli grafik: V= (v 1 ,… , v n ), uning qirralari sikl hosil qiladi:
Muammo 9.12. Grafik uchun erishish mumkinligi grafik matritsasi hisoblang
va mos keladigan erishish grafigini tuzing. G grafigining barcha asoslarini toping.
Muammo 9.13. Berilgan uchun qurish guruch. 9.7 yo'naltirilgan grafik G 1 =(V,E) uning qo'shnilik matritsasi A G1, insidans matritsasi B G1 va qo'shnilik ro'yxatlari. A G1* erishish imkoniyati matritsasi ni hisoblang va mos keladigan G1* erishish imkoniyati grafigini tuzing.
Guruch. 9.7.
Yo'naltirilmagan va yo'naltirilgan daraxtlar
Daraxtlar har xil turdagi ierarxik tuzilmalarni ifodalash uchun ishlatiladigan grafiklarning eng qiziqarli sinflaridan biridir.
Ta'rif 10.1. Yo'naltirilmagan grafik, agar u bog'langan va tsikllarga ega bo'lmasa, daraxt deyiladi.
Ta'rif 10.2. Yo‘naltirilgan grafik G=(V,E) agar (yo‘naltirilgan) daraxt deyiladi
Yoniq guruch. 10.1 yo'naltirilmagan daraxt G 1 va yo'naltirilgan daraxt G 2 misollari ko'rsatilgan. E'tibor bering, G 2 daraxti G 1 dan c uchini ildiz sifatida tanlash va barcha qirralarni ildizdan uzoqroq yo'nalishda yo'naltirish orqali olingan.
Guruch. 10.1. Yo'naltirilmagan va yo'naltirilgan daraxtlar
Bu tasodif emas. Yo'naltirilmagan va yo'naltirilgan daraxtlar o'rtasidagi bog'liqlik haqidagi quyidagi gapni o'zingiz isbotlang.
Lemma 10.1. Agar biron-bir yo'naltirilmagan daraxtda G=(V,E) ildiz sifatida ixtiyoriy v V cho'qqisini tanlaymiz va barcha qirralarni "ildizdan" yo'nalishiga yo'naltiramiz, ya'ni. v unga tushadigan barcha qirralarning boshi, v ga tutashgan cho'qqilar unga to'g'ri keladigan barcha yo'naltirilmagan qirralarning boshi va hokazo qilib belgilansa, natijada olingan yo'naltirilgan grafik G" yo'naltirilgan daraxt bo'ladi.
Yo'naltirilmagan va yo'naltirilgan daraxtlar ko'plab ekvivalent xususiyatlarga ega.
10.1 teorema. G=(V,E) yo‘naltirilmagan grafik bo‘lsin. Keyin quyidagi shartlar ekvivalent bo'ladi.
G - daraxt.
G dagi har qanday ikkita cho'qqi uchun ularni bog'laydigan yagona yo'l mavjud.
G ulangan, lekin E dan istalgan chekka olib tashlanganida u ulanishni to'xtatadi.
G ulanadi va |E| = |V| -1.
G asiklik va |E| = |V| -1.
G asiklikdir, lekin E ga istalgan chekka qo'shilishi tsikl hosil qiladi.
Isbot(1) (2): Agar G dagi ba'zi ikkita cho'qqi ikkita yo'l bilan bog'langan bo'lsa, u holda G ning tsikli bo'lishi aniq. Ammo bu (1)dagi daraxt ta'rifiga zid keladi.
(2) (3): Agar G ulangan bo'lsa, lekin ba'zi chekka (u,v) olib tashlanganda, E ulanishni yo'qotmaydi, u va v o'rtasida bu chetni o'z ichiga olmaydigan yo'l bor. Ammo keyin u va v ni bog'laydigan G da kamida ikkita yo'l bor, bu shart (2) ga ziddir.
(3) (4): O'quvchiga taqdim etilgan (9.4 muammoga qarang).
(4) (5): Agar G siklni o'z ichiga olgan bo'lsa va ulangan bo'lsa, u holda tsikldan biron bir chekka olib tashlanganda, ulanganlik buzilmasligi kerak, lekin qirralarning |E|= V -2 bo'lib qoladi va 9.4-masalaga muvofiq. (a) kamida V -1 qovurg'a bo'lishi kerak. Olingan qarama-qarshilik G da sikllar yo'qligini va (5) shart bajarilganligini ko'rsatadi.
(5) (6): Faraz qilaylik, E ga chekka (u,v) qo‘shilganda sikl paydo bo‘lmadi. U holda G dagi u va v uchlari turli bog'langan komponentlarda bo'ladi. |E|= V -1 bo'lganligi sababli, bu komponentlarning birida (V 1 ,E 1) bo'lsin, qirralarning soni va uchlari soni mos keladi: |E 1 |=|V 1 |. Ammo keyin uning tsikli bor (9.4 (b) masalaga qarang), bu G ning asiklikligiga zid keladi.
(6) (1): Agar G ulanmagan bo'lsa, u holda turli bog'langan komponentlardan ikkita u va v uchlari bo'lar edi. Keyin E ga chekka (u,v) qo'shilishi (6) ga zid bo'lgan tsiklning paydo bo'lishiga olib kelmaydi. Demak, G bog'langan va daraxtdir.
Yo'naltirilgan daraxtlar uchun ko'pincha quyidagi induktiv ta'rifdan foydalanish qulay.
Ta'rif 10.3. Keling, induksiya yo'li bilan daraxtlar deb ataladigan yo'naltirilgan grafiklar sinfini aniqlaylik. Shu bilan birga, ularning har biri uchun biz tanlangan cho'qqi - ildizni aniqlaymiz.
Guruch. 10.2 bu ta'rifni aks ettiradi.
Guruch. 10.2. Yo'naltirilgan daraxtlarni induktiv aniqlash
10.2 teorema. 10.2 va 10.3 yo'naltirilgan daraxtlarning ta'riflari ekvivalentdir.
Isbot Grafik G=(V,E) 10.2 ta’rif shartlarini qanoatlantirsin. Cho'qqilar soni bo'yicha |V| ekanligini induksiya orqali ko'rsatamiz.
Agar |V|=1 boʻlsa, u holda yagona v V choʻqqisi (1) xossasi boʻyicha daraxtning ildizi, yaʼni. Bu grafikda qirralar yo'q: E =. Keyin.
Faraz qilaylik, 10.2 ta’rifni qanoatlantiradigan n ta burchakli har bir grafik ga kiritilgan. (n+1)-chi cho'qqisi bo'lgan G=(V,E) grafik 10.2 ta'rif shartlarini qanoatlantirsin. (1) shartga ko'ra u r 0 cho'qqi-ildizga ega. r 0 dan k chekka chiqsin va ular r 1 , ... , r k (k 1) cho’qqilarga olib borsin. V i =( v V|v \textit( )r i dan yetib boradigan cho‘qqilari va ularni tutashtiruvchi E i E qirralarini o‘z ichiga olgan grafikni G i ,(i=1, …, k) bilan belgilaymiz.Tushunish oson. G i 10.2. ta'rifning shartlarini qondiradi. Haqiqatan ham, r i qirralarni o'z ichiga olmaydi, ya'ni. bu cho'qqi G i ning ildizidir. V i dan qolgan har bir cho’qqi G’dagi kabi bir chetni o’z ichiga oladi. Agar v V i bo'lsa, u holda G i grafigining ta'rifi bo'yicha r i ildizidan erishish mumkin. beri |V i | n, keyin induktiv gipoteza bilan. Keyin G grafigi G 1, ..., G k daraxtlardan 10.3 taʼrifning induktiv qoidasi (2) boʻyicha olinadi va shuning uchun sinfga kiradi.
⇐ Agar G=(V,E) grafik sinfga kiritilgan boʻlsa, 10.2 taʼrifning (1)-(3) shartlarining bajarilishini 10.2 taʼrif yordamida induksiya yoʻli bilan osongina aniqlash mumkin. Buni mashg‘ulot sifatida o‘quvchiga qoldiramiz.
Yo'naltirilgan daraxtlar bilan bog'liq juda ko'p terminologiya mavjud bo'lib, ular ikkita manbadan kelib chiqadi: botanika va oilaviy munosabatlar sohasi.
Ildiz - chekkalari bo'lmagan yagona cho'qqi, barglar - chekkalari bo'lmagan yagona cho'qqi. Ildizdan barggacha bo'lgan yo'l daraxt shoxlari deb ataladi. Daraxtning balandligi uning shoxlarining maksimal uzunligidir. Cho'qqining chuqurligi - bu ildizdan shu cho'qqigacha bo'lgan yo'lning uzunligi. v V cho'qqisi uchun daraxtning T=(V,E) pastki grafigi, shu jumladan v dan yetib boradigan barcha cho'qqilari va E dan ularni tutashtiruvchi qirralari v ildizi bilan T daraxtining T v pastki daraxtini hosil qiladi (10.3-masalaga qarang). V cho'qqisining balandligi T v daraxtining balandligi. Bir nechta ajratilgan daraxtlarning birlashmasi bo'lgan grafik o'rmon deb ataladi.
Agar chekka v cho'qqidan w cho'qqisiga olib borsa, u holda v deyiladi ota w, va w - o'g'lim v (so'nggi paytlarda ingliz tilidagi adabiyotlarda aseksual juft atamalar qo'llanilmoqda: ota-ona - bola). Daraxtning ta'rifidan darhol kelib chiqadiki, har bir tepada, ildizdan tashqari, bitta otasi bor. Agar yo'l v cho'qqidan w cho'qqisiga olib borsa, u holda v ning ajdodi, w esa v ning avlodi deyiladi. Umumiy otasi bo'lgan cho'qqilar deyiladi birodarlar yoki opa-singillar.
Keling, yo'naltirilgan daraxtlarni umumlashtiruvchi grafiklarning yana bir sinfini - yo'naltirilgan asikliklarni ajratib ko'rsatamiz. Keyinchalik mantiqiy funktsiyalarni ifodalash uchun bunday etiketli grafiklarning ikki turi qo'llaniladi. Bu grafiklar bir nechta ildizga ega bo'lishi mumkin - qirralari bo'lmagan cho'qqilar va har bir cho'qqi daraxtlar kabi bitta emas, balki bir nechta qirralarni o'z ichiga olishi mumkin.
kompyuter texnologiyalar, ayniqsa dastur ... 2009 yilning boshlang'ich maktab eksperimental sayt hisoblanadi tomonidan Federal joriy etish davlat ...
OAV MONITORING Kasb-hunar ta'limini modernizatsiyalash 2011 yil mart - avgust
XulosaBirlashgan davlat imtihonlar" tomonidan tanlov": axborot kompyutertexnologiyalar, biologiya va adabiyot. Aytgancha, bu erda yil Yagona davlat imtihoni... savol“Amalga kiritish natijalari haqida dasturlari milliy tadqiqot universitetlarini rivojlantirish 2009 -2010 yillar". ...
STRATEGIK RIVOJLANISH DASTURI Tver 2011
DasturIN 2009 yil. 2010 yilda kuzatilgan tarkibiy o'zgarishlar yiltomonidan tomon 2009 , ... Professional tarzda – yo'naltirilgan xorijiy til", "Zamonaviy ta'lim texnologiyalar". Har birida dastur malaka oshirish moduli joriy etilmoqda” Davlat ...
1. erishish mumkinligi va qarama-qarshilik
Erish qobiliyati tushunchasi qo'llaniladigan juda ko'p muammolar mavjud. Mana taxalluslardan biri. Grafik qandaydir tashkilotning modeli bo'lishi mumkin, unda odamlar cho'qqilar bilan ifodalanadi va yoylar aloqa kanallarini izohlaydi. Bunday modelni ko'rib chiqayotganda, bir odamdan x ma'lumotni boshqa shaxsga o'tkazish mumkinmi degan savol tug'ilishi mumkin x 7, ya'ni. X cho'qqisidan X cho'qqisiga boradigan yo'l bormi? Agar shunday yo'l mavjud bo'lsa, u holda x cho'qqisiga x cho'qqisidan chiqish mumkin deyiladi. Uzunliklari berilgan qiymatdan oshmaydigan yoki uzunligi grafikdagi eng koʻp choʻqqilar sonidan kichik boʻlgan yoʻllardagina x choʻqqisidan x choʻqqisiga erishish mumkinligi qiziqtirishi mumkin.
Grafikdagi erishish imkoniyati R = ||r,y||, erishish imkoniyati matritsasi bilan tavsiflanadi, i, j =1,2,... P, Qayerda P grafikning uchlari soni va har bir element quyidagicha aniqlanadi:
Gu- 1 agar cho'qqi X, x dan kirish mumkin,
Gu= 0 aks holda.
G grafigining berilgan x„ tepasidan chiqish mumkin boʻlgan R(x,) uchlari toʻplami quyidagi x elementlardan iborat; , buning uchun erishish mumkin bo'lgan matritsadagi (/, /)-chi element 1 ga teng. Shubhasiz, R matritsasidagi barcha diagonal elementlar 1 ga teng, chunki har bir cho'qqiga o'zidan 0 uzunlikdagi yo'l orqali erishish mumkin. Chunki 1-tartibni to'g'ridan-to'g'ri xaritalash G +1 (x,) bunday cho'qqilar to'plamidir Xj, x dan 1 uzunlikdagi yo'llar yordamida erishish mumkin bo'lsa, G(G(x,)) = G to'plami X,) 2 uzunlikdagi yo'llar yordamida x dan erishish mumkin bo'lgan cho'qqilardan iborat. G ga o'xshash p(x,) uzunlik yo'llari yordamida x dan erishish mumkin bo'lgan cho'qqilar to'plamidir R.
Grafikdagi x„ dan erishish mumkin bo'lgan har qanday cho'qqi uzunligi 0 yoki 1 yoki 2 bo'lgan yo'l (yoki yo'llar) yordamida erishish mumkin bo'lganligi sababli, ..., yoki R, u holda x„ choʻqqisiga erishish mumkin boʻlgan choʻqqilar toʻplami shaklda ifodalanishi mumkin
Ko'rib turganimizdek, erishish mumkin bo'lgan cho'qqilar to'plami R(x,) tepalikning to'g'ridan-to'g'ri o'tishli yopilishini ifodalaydi x„, ya'ni. R(x,) = T(x,). Shunday qilib, erishish mumkin bo'lgan matritsani qurish uchun barcha x, e X uchlari uchun erishish mumkin bo'lgan R(x,) to'plamlarni topamiz. g y - 1 agar x 7 e R(x,) va gu- 0 aks holda. Shaklda ko'rsatilgan grafik uchun. 59,4, A, erishish imkoniyati to'plamlari quyidagicha topiladi: 
Guruch. 59.4.
Qo'shnilik (A), erishish imkoniyati (R), qarama-qarshilik (Q) matritsalari quyidagi shaklga ega:
Qarama-qarshilik matritsasi Q = qij,i,j= 1,2,... P, Qayerda P- grafikning uchlari soni, quyidagicha aniqlanadi:
qij= 1, agar xy tepasidan cho'qqiga chiqish mumkin bo'lsa x h qtj = Aks holda.
Qarshi foydalanish mumkin bo'lgan to'plam Q(x,)- bu to'plamning istalgan cho'qqisidan X/ cho'qqisiga chiqish mumkin bo'lgan cho'qqilar to'plami. Rivojlanish mumkin bo'lgan R(x,) to'plamini qurishga o'xshab, biz uchun ifoda yozishimiz mumkin Q(x,):
Shunday qilib, Q(x,) x cho'qqisining teskari tranzitiv yopilishidan boshqa narsa emasligi aniq, ya'ni. Q(x() = T"(x,). Ta'riflardan ko'rinib turibdiki, X ustuni, Q matritsasi (qaysi q t j = 1, agar xyQ(x,) va s/u=0 aks holda) R matritsasining x qatoriga to'g'ri keladi, ya'ni. Q = R, bu erda R - erishish mumkin bo'lgan R matritsasiga ko'chirilgan matritsa.
Qarama-qarshi erishish matritsasi avvalroq ko'rsatilgan.
Shuni ta'kidlash kerakki, R va Q matritsalarining barcha elementlari 1 yoki 0 ga teng bo'lganligi sababli, har bir satr ikkilik shaklda saqlanishi mumkin, bu esa kompyuter xotirasi xarajatlarini tejaydi. R va Q matritsalari kompyuterda ishlov berish uchun qulaydir, chunki hisoblash nuqtai nazaridan asosiy operatsiyalar yuqori tezlikdagi mantiqiy operatsiyalardir.
2. Yo'lga kiritilgan cho'qqilar to'plamini topish Agar siz ushbu yo'llarga kiritilgan grafik uchlari haqida ma'lumot olishingiz kerak bo'lsa, unda siz to'g'ridan-to'g'ri va teskari o'tishli yopilishlarning ta'riflarini eslab qolishingiz kerak. T + (x,) cho'qqilar to'plami bo'lib, x„ cho'qqisidan yo'llar bor va T"(Y) - x / ga yo'llar mavjud bo'lgan cho'qqilar to'plami, keyin T (x,) n T. (xj)- har biri x dan xy gacha bo'lgan kamida bitta yo'lga tegishli bo'lgan cho'qqilar to'plami. Bu cho'qqilar asosiy yoki ikkita oxirgi uchga nisbatan integral deyiladi X, va hu. Grafikning barcha boshqa uchlari ahamiyatsiz yoki ortiqcha deb ataladi, chunki ularni olib tashlash x/dan xygacha bo'lgan yo'llarga ta'sir qilmaydi.
Shunday qilib, rasmdagi grafik uchun. 59.5, yo'lga kiritilgan cho'qqilarni topish, masalan, X2 cho'qqisidan X4 cho'qqigacha, T + (xg) = (xg, x3, X4, X5, Xb), T "(x4) = (xi) ni topishga to'g'ri keladi. , X2, X3 , X4, X5) va ularning kesishuvlari T + (xr) n T(x4) = = (X2, X3, X4, X 5).
