අධ්‍යක්ෂණය කළ ප්‍රස්ථාරය ලබා දී ඇත. දිශානුගත ප්‍රස්තාරය. ලූප් ප්‍රස්ථාර, මිශ්‍ර ප්‍රස්ථාර, හිස් ප්‍රස්ථාර, බහු ප්‍රස්ථාර, සාමාන්‍ය ප්‍රස්ථාර, සම්පූර්ණ ප්‍රස්ථාර

අධ්යක්ෂණය කළ ප්රස්තාරය(කෙටියෙන් digraph) යනු (බහු) ප්‍රස්ථාරයකි, එහි දාරවලට දිශාවක් පවරා ඇත. යොමු කරන ලද දාර ද හැඳින්වේ චාප, සහ සමහර මූලාශ්රවල සහ හුදෙක් දාරවල. කිසිදු දාරයක් දිශානතියක් ලබා නොදෙන ප්‍රස්ථාරයක් නොදියුණු ප්‍රස්ථාරයක් ලෙස හැඳින්වේ, හෝ digraph නොවන.

මූලික සංකල්ප

විධිමත් ලෙස, digraph D = (V , E) (\ displaystyle D=(V,E))බොහෝ සමන්විත වේ V (\ displaystyle V), එහි මූලද්රව්ය ලෙස හැඳින්වේ මුදුන්, සහ කට්ටල E (\ displaystyle E)ඇණවුම් කළ සිරස් යුගල u , v ∈ V (\ displaystyle u,v\ in V).

චාප (u , v) (\ displaystyle (u,v)) ආනුෂංගිකමුදුන් u (\ displaystyle u)හා v (\ displaystyle v). ඒත් එක්කම එහෙම කියනවා u (\ displaystyle u) - ආරම්භක උච්චයචාප, සහ v (\ displaystyle v) - පර්යන්ත උච්චය.

සම්බන්ධතාවය

මාර්ගය digraph එකක සිරස්වල ප්‍රත්‍යාවර්ත අනුක්‍රමයක් ලෙස හැඳින්වේ සහ චාප, කාරුණික v 0 ( v 0 , v 1 ) v 1 ( v 1 , v 2 ) v 2 . . . v n (\ displaystyle v_(0)\(v_(0),v_(1)\)v_(1)\(v_(1),v_(2)\)v_(2)...v_(n))(ශීර්ෂයන් නැවත නැවතත් කළ හැක). මාර්ගයේ දිග- එහි ඇති චාප ගණන.

මාර්ගයඅර තියෙන්නේ මාර්ගයපුනරාවර්තන චාපයකින් තොරව ඩිග්‍රැෆ් එකක, පහසු මාර්ගය- පුනරාවර්තන සිරස් නැත. එක් ශීර්ෂයක සිට තවත් ශීර්ෂයකට මාර්ගයක් තිබේ නම්, දෙවන ශීර්ෂය සාක්ෂාත් කරගත හැකියපළමු සිට.

පරිපථයවසා ඇත මාර්ගය.

සදහා අර්ධ මාර්ගයචාප වල දිශාවට ඇති සීමාව ඉවත් කර ඇත අතරමගහා අර්ධ සමෝච්ඡය.

digraph දැඩි ලෙස සම්බන්ධ වී ඇත, හෝ සරලව ශක්තිමත්, එහි සියලු සිරස් අන්යෝන්ය නම් සාක්ෂාත් කරගත හැකිය; එක් මාර්ගයක් සම්බන්ධ කර ඇත, හෝ සරලව ඒකපාර්ශ්විකකිසියම් සිරස් දෙකක් සඳහා අවම වශයෙන් එකක් අනෙකෙන් ළඟා විය හැකි නම්; ලිහිල්ව සම්බන්ධ වී ඇත, හෝ සරලව දුර්වල, චාප වල දිශාව නොසලකා හරින්නේ නම්, සම්බන්ධිත (බහු) ප්රස්ථාරයක් ලබා ගනී;

උපරිම ශක්තිමත්උපස්ථරය ලෙස හැඳින්වේ ශක්තිමත් සංරචකය; ඒකපාර්ශ්වික සංරචකයහා දුර්වල සංරචකයසමාන ආකාරයකින් අර්ථ දක්වා ඇත.

ඝනීභවනය digraph D (\ displaystyle D)සිරස් ශක්තිමත් සංරචක වන digraph ලෙස හැඳින්වේ D (\ displaystyle D), සහ චාපය ඇතුලට D ⋆ (\ displaystyle D^(\star ))අනුරූප සංරචකවල ඇතුළත් කර ඇති සිරස් අතර අවම වශයෙන් එක් චාපයක් පවතින බව පෙන්නුම් කරයි.

අතිරේක අර්ථ දැක්වීම්

අධ්‍යක්ෂණය කරන ලද ඇසික්ලික් ප්‍රස්ථාරයහෝ hammockයනු සමෝච්ඡ විවරණයකි.

දාරවල දිශාව ආපසු හරවා ලබා දී ඇති එකකින් ලබාගත් අධ්‍යක්‍ෂිත ප්‍රස්ථාරයක් ලෙස හැඳින්වේ ආපසු හැරවීම.

නෝඩ් තුනක් සහිත සියලුම ඩිග්‍රැෆ් වල රූපය සහ ගුණාංග

පුරාවෘත්තය: සිට- දුර්වල, OS- ඒකපාර්ශ්වික, එස්එස්- ශක්තිමත්, එච්- අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයකි, ජී- කඩුල්ලක් (ඇචක්ලික්), ටී- තරඟාවලියකි

0 චාප	1 චාප	චාප 2 ක්	චාප 3 ක්	චාප 4 ක්	චාප 5 ක්	චාප 6 ක්
හිස්, එන්, ජී	එන්, ජී		OS	CC	CC	සම්පූර්ණ, CC
		OS, N, G	CC, N, T	CC
		සී, එන්, ජී	OS, N, G, T	OS
		සී, එන්, ජී	OS

පෙර පරිච්ඡේදවලදී, අපි යොමු නොකළ ප්‍රස්ථාර න්‍යායේ ප්‍රධාන ප්‍රතිඵල කිහිපයක් ඉදිරිපත් කළෙමු. කෙසේ වෙතත්, සමහර අවස්ථාවන් විස්තර කිරීමට යොමු නොකළ ප්‍රස්ථාර ප්‍රමාණවත් නොවේ. උදාහරණයක් ලෙස, වීථිවලට අනුරූප වන ප්‍රස්ථාරයක් සහිත ගමනාගමන සිතියමක් නිරූපණය කරන විට, චලනය වීමේ අවසර ලත් දිශාව දැක්වීමට දාරවලට දිශානතියක් පැවරිය යුතුය. තවත් උදාහරණයක් වන්නේ ප්‍රස්ථාරයකින් ආකෘතිගත කරන ලද පරිගණක වැඩසටහනක් වන අතර එහි දාර එක් උපදෙස් මාලාවක සිට තවත් එකකට පාලන ප්‍රවාහය නිරූපණය කරයි. වැඩසටහනේ මෙම නිරූපණයේදී, පාලන ප්‍රවාහයේ දිශාව දැක්වීමට දාරවලට දිශානතියක් ද ලබා දිය යුතුය. නිරූපණය කිරීම සඳහා යොමු කළ ප්‍රස්ථාරයක් අවශ්‍ය වන භෞතික පද්ධතියක තවත් උදාහරණයක් වන්නේ විද්‍යුත් පරිපථයකි. අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරවල යෙදුම් සහ අදාළ ඇල්ගොරිතම පරිච්ඡේදයේ සාකච්ඡා කෙරේ. 11-15.

මෙම පරිච්ඡේදය අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරවල න්‍යායේ ප්‍රධාන ප්‍රතිඵල ඉදිරිපත් කරයි. දිශානුගත ඉයුලර් දාම සහ හැමිල්ටෝනියානු චක්‍රවල පැවැත්ම සම්බන්ධ ප්‍රශ්න සාකච්ඡා කෙරේ. දිශානුගත ගස් සහ දිශානුගත ඉයුලර් දාම සමඟ ඇති සම්බන්ධය ද සලකා බලනු ලැබේ.

5.1 මූලික අර්ථ දැක්වීම් සහ සංකල්ප

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරවලට අදාළ මූලික නිර්වචන සහ සංකල්ප කිහිපයක් හඳුන්වා දීමෙන් ආරම්භ කරමු.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක් කට්ටල දෙකකින් සමන්විත වේ: සීමිත V කට්ටලයක්, එහි මූලද්‍රව්‍ය සිරස් ලෙස හැඳින්වේ, සහ සීමිත E කට්ටලයක්, එහි මූලද්‍රව්‍ය දාර හෝ චාප ලෙස හැඳින්වේ. සෑම චාපයක්ම ඇණවුම් කළ සිරස් යුගලයක් සමඟ සම්බන්ධ වේ.

සිරස් නම් කිරීමට සංකේත භාවිතා කරන අතර චාප නම් කිරීමට සංකේත භාවිතා කරයි. , එසේ නම්, අවසන් vertices ලෙස හැඳින්වේ, එහිදී - ආරම්භක ශීර්ෂය, - end vertex . එකම ආරම්භක සහ අවසාන සිරස් යුගල ඇති සියලුම චාප සමාන්තර ලෙස හැඳින්වේ. සිද්ධි ශීර්ෂය එහි ආරම්භය සහ අවසන් ශීර්ෂය යන දෙකම නම් චාපයක් ලූපයක් ලෙස හැඳින්වේ.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක චිත්‍රක නිරූපණයකදී, සිරස් තිත් හෝ කව මගින් නිරූපණය වන අතර දාර (චාප) කොටස් මගින් නිරූපණය කෙරේ.

ඒවායේ අන්ත ලක්ෂ්‍ය නියෝජනය කරන තිත් හෝ කව සම්බන්ධ කරන රේඛා. මීට අමතරව, චාප වලට දිශානතියක් පවරනු ලැබේ, එය ආරම්භක සිරස් සිට අවසන් ශීර්ෂය දක්වා යොමු කරන ලද ඊතලයකින් දැක්වේ.

උදාහරණයක් ලෙස, ඔවුන්ගේ ඒවා නම්, අධ්‍යක්ෂ ප්‍රස්ථාරයක් fig මගින් නිරූපණය කළ හැක. 5.1 මෙම ප්රස්ථාරයේ - සමාන්තර චාප, සහ - ලූප්.

සහල්. 5.1 දිශානුගත ප්‍රස්තාරය.

චාපයක් එහි අවසාන ශීර්ෂ දක්වා සිදුවීමක් යැයි කියනු ලැබේ. එක් චාපයක් සඳහා පර්යන්තය නම් සිරස් යාබද ලෙස හැඳින්වේ. චාප වලට පොදු පර්යන්ත ශීර්ෂයක් තිබේ නම්, ඒවා යාබද ලෙස හැඳින්වේ.

චාපයක් එහි ආරම්භක ශීර්ෂයෙන් පිටතට ගොස් එහි අවසාන ශීර්ෂයට ඇතුල් වීම ලෙස හැඳින්වේ. ශීර්ෂයකට සිද්ධි චාප නොමැති නම් හුදකලා යැයි කියනු ලැබේ.

ශීර්ෂයක උපාධිය යනු එයට ඇති චාප සංඛ්‍යාවයි. ශීර්ෂයක in-degree යනු V ට ඇතුළු වන චාප ගණන වන අතර පිටත-උපාධිය යනු පිටතට යන චාප ගණනයි. සංකේත සහ b" මගින් අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයේ අවම බාහිර-අංශක සහ අංශක විදහා දක්වයි. ඒ හා සමානව, සංකේත මඟින් පිළිවෙළින් උපරිම බාහිර-උපාධි සහ අංශක විදහා දක්වයි.

ඕනෑම ශීර්ෂයක කට්ටල පහත පරිදි අර්ථ දක්වා ඇත: උදාහරණයක් ලෙස, රූපයේ ප්‍රස්ථාරයේ. 5.1

ලූපය මෙම ශීර්ෂයට ඇතුල් වීම සහ පිටවීම යන දෙකෙහිම අර්ධ-අංශක වැඩි කරන බව සලකන්න. පහත සඳහන් ප්‍රකාශය එක් එක් චාපයක් අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක ආදානය සහ ප්‍රතිදානය යන දෙකෙහිම අර්ධ අංශක එකතුවෙන් 1 කින් වැඩි වීමේ ප්‍රතිඵලයකි.

ප්රමේයය 5.1. චාප සහිත සෘජු ප්‍රස්ථාරයක

in-degrees එකතුව = out-degrees එකතුව = m.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක උප ප්‍රස්ථාර සහ ජනනය කරන ලද උප ප්‍රස්ථාර නිර්වචනය නොකළ ප්‍රස්ථාරවල (Sec. 1.2) ආකාරයටම අර්ථ දක්වා ඇත.

අධ්‍යක්ෂණය කරන ලද G ප්‍රස්ථාරයක චාප වලින් දිශානතිය ඉවත් කිරීමේ ප්‍රතිඵලයක් ලෙස ඇති වන අපරික්ෂාකාරී ප්‍රස්ථාරයක් යටින් දිවෙන නොපැහැදිලි ප්‍රස්ථාරය G ලෙස හඳුන්වනු ලබන අතර එය මගින් දක්වනු ලැබේ.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක දිශානුගත මාර්ගයක් යනු සිරස්වල සීමිත අනුපිළිවෙලකි

G ප්‍රස්ථාරයේ චාපයක් යනු කුමක්ද. එවැනි මාර්ගයක් සාමාන්‍යයෙන් අධ්‍යක්ෂණය කරන ලද -මාර්ගයක් ලෙස හඳුන්වනු ලබන අතර, ආරම්භක ශීර්ෂය මාර්ගයේ අවසාන ශීර්ෂය වන අතර අනෙකුත් සියලුම සිරස් අභ්‍යන්තර වේ. දිශානුගත මාර්ගයක ආරම්භක සහ අවසාන සිරස් එහි අවසාන සිරස් ලෙස හැඳින්වේ. චාප සහ එම නිසා සිරස්, එක් වරකට වඩා යොමු කළ මාර්ගයක දිස් විය හැකි බව සලකන්න.

දිශානුගත මාර්ගයක් එහි අවසාන සිරස් වෙනස් නම් විවෘත යැයි කියනු ලැබේ, එසේ නොමැති නම් එය සංවෘත ලෙස හැඳින්වේ.

දිශානුගත මාර්ගයක් එහි සියලු චාප එකිනෙකට වෙනස් නම් දිශානුගත මාර්ගයක් ලෙස හැඳින්වේ. දිශානුගත මාර්ගයක් එහි අවසාන ලක්ෂ්‍ය වෙනස් නම් විවෘත වේ, එසේ නොමැති නම් එය වසා ඇත.

විවෘත දිශානුගත මාර්ගයක් එහි සියලුම සිරස් වෙනස් නම් දිශානුගත මාර්ගයක් ලෙස හැඳින්වේ.

සංවෘත දිශානුගත දාමයක් පර්යන්තය හැර එහි සිරස් වෙනස් නම් දිශානුගත චක්‍රයක් හෝ සමෝච්ඡයක් ලෙස හැඳින්වේ.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක් එහි සමෝච්ඡ නොමැති නම් ඇචක්‍රීය හෝ සමෝච්ඡ නොවන යැයි කියනු ලැබේ. උදාහරණයක් ලෙස, Fig. 1 හි අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරය ආචක්‍රීය වේ. 5.2

සහල්. 5.2 Acyclic අධ්‍යක්ෂණය කළ ප්‍රස්ථාරය.

සහල්. 5.3 දැඩි ලෙස සම්බන්ධිත අධ්‍යක්‍ෂ ප්‍රස්ථාරයකි.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක සිරස් අනුපිළිවෙලක් G හි ඇති මාර්ගයක් ලෙස හැඳින්වේ, එය යටින් පවතින අපරික්ෂාකාරී ප්‍රස්ථාරයේ මාර්ගයක් නම්, උදාහරණයක් ලෙස, Fig. 5.2 යනු මාර්ගයකි, නමුත් නැඹුරු නොවේ.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක දාමය, මාර්ගය සහ චක්‍රය එලෙසම අර්ථ දක්වා ඇත.

යටින් ඇති යොමු නොකළ ප්‍රස්ථාරය සම්බන්ධ කර ඇත්නම් අධ්‍යක්ෂණය කළ ප්‍රස්ථාරයක් සම්බන්ධ වේ යැයි කියනු ලැබේ.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක G උප ප්‍රස්ථාරයක් ප්‍රස්ථාරයේ සංරචකයක් නම් එය G ප්‍රස්ථාරයේ සංරචකයක් ලෙස හැඳින්වේ

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක සිරස් G වෙතින් සහ ආපසු G වෙත යොමු කළ මාර්ග තිබේ නම් දැඩි ලෙස සම්බන්ධ වන බව කියනු ලැබේ. සමඟ දැඩි ලෙස සම්බන්ධ වී ඇත්නම්, පැහැදිලිවම, දැඩි ලෙස සම්බන්ධ වේ. සෑම ශීර්ෂයක්ම තමාටම තදින් සම්බන්ධ වේ.

ශීර්ෂයක් ශීර්ෂයකට තදින් සම්බන්ධ වී තිබේ නම්, පහසුවෙන් පෙනෙන පරිදි, එම සිරස් ශීර්ෂයට තදින් සම්බන්ධ වේ.එබැවින්, මෙම අවස්ථාවෙහිදී, ශීර්ෂයන් දැඩි ලෙස සම්බන්ධ වී ඇති බව යමෙක් සරලව කියයි.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක් එහි සියලුම සිරස් තදින් සම්බන්ධ වී ඇත්නම් එය දැඩි ලෙස සම්බන්ධ වන බව කියනු ලැබේ. උදාහරණයක් ලෙස, රූපයේ ඇති ප්‍රස්ථාරය. 5.3

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක උපරිම තදින් සම්බන්ධිත උප ප්‍රස්ථාරය G හි ප්‍රබල ලෙස සම්බන්ධිත සංරචකයක් ලෙස හැඳින්වේ. අධ්‍යක්ෂණය කළ ප්‍රස්ථාරයක් දැඩි ලෙස සම්බන්ධ වී ඇත්නම්, එයට තනි දැඩි ලෙස සම්බන්ධිත සංරචකයක් ඇත, එනම් එයම.

යොමු කළ ප්‍රස්ථාරයක් සලකා බලන්න. එහි සෑම සිරස්තලයක්ම G ප්‍රස්ථාරයේ හරියටම එක් ප්‍රබල ලෙස සම්බන්ධිත සංරචකයකට අයත් වන බව දැකීම පහසුය. එබැවින්, දැඩි ලෙස සම්බන්ධිත සංරචකවල සිරස් කුලක ප්‍රස්ථාරයේ Y ශීර්ෂයේ කොටසක් සාදයි.

සහල්. 5.4 ප්රස්තාරය සහ එහි ඝනීභවනය.

උදාහරණයක් ලෙස, රූපයේ දැක්වෙන ප්‍රස්ථාරය. 5.4, ​​a හි සිරස් කට්ටල සමඟ දැඩි ලෙස සම්බන්ධ වූ සංරචක තුනක් ඇති අතර අධ්‍යක්‍ෂිත ප්‍රස්ථාරයක සිරස් කට්ටලයේ කොටසක් සාදයි.

සිත්ගන්නා කරුණ නම්, අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක ප්‍රස්ථාරයේ ප්‍රබල ලෙස සම්බන්ධිත කිසිදු සංරචකයකට ඇතුළත් නොවන චාප අඩංගු විය හැකිය. උදාහරණයක් ලෙස, Fig. හි ප්‍රස්ථාරයෙහි ප්‍රබල ලෙස සම්බන්ධිත කිසිදු සංරචකයකට චාප ඇතුළත් නොවේ. 5.4, ​​ඒ.

මේ අනුව, "දැඩි ලෙස සම්බන්ධ වූ" ගුණාංගය ප්‍රස්ථාරයේ ශීර්ෂ කට්ටලය බෙදීමට හේතු වුවද, එය චාප කට්ටලය බෙදීම ජනනය නොකළ හැකිය.

යුනියන්, ඡේදනය, mod 2 එකතුව, සහ අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරවල අනෙකුත් ක්‍රියාවන් නොපැහැදිලි ප්‍රස්ථාරවල මෙන් හරියටම අර්ථ දක්වා ඇත (Sec. 1.5).

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක G හි දැඩි ලෙස සම්බන්ධිත සංරචකවල සියලුම චාප හැකිලීමේ ප්‍රතිඵලය වන ප්‍රස්ථාරය G හි ඝනීභවනය වූ ප්‍රස්ථාරය ලෙස හැඳින්වේ. රූපයේ දැක්වෙන ප්‍රස්ථාරයේ ඝනීභවනය. 5.4, ​​a, රූපයේ දැක්වේ. 5.4b.

ප්‍රස්ථාරයේ සිරස් ප්‍රස්ථාර G හි දැඩි ලෙස සම්බන්ධිත සංරචක වලට අනුරූප වන අතර සංරචකවල ඝනීභවනය කරන ලද රූප ලෙස හැඳින්වේ.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක ශ්‍රේණිගත කිරීම සහ චක්‍රීය සංඛ්‍යාව අනුරූප නොවන ප්‍රස්ථාරයේ ඒවාට සමාන වේ. මෙයින් අදහස් කරන්නේ G අධ්‍යක්ෂණය කළ ප්‍රස්ථාරයක චාප, සිරස් සහ සංරචක තිබේ නම්, G ප්‍රස්ථාරයේ ශ්‍රේණිය සහ චක්‍රීය අංකය ලබා දෙන්නේ

අපි දැන් අවම වශයෙන් සම්බන්ධිත ප්‍රස්ථාර නිර්වචනය කර ඒවායේ සමහර ගුණාංග අධ්‍යයනය කරමු.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාර G එකක් දැඩි ලෙස සම්බන්ධ වී ඇත්නම් එය අවම වශයෙන් සම්බන්ධ වන බව කියනු ලබන අතර, කිසියම් චාපයක් ඉවත් කිරීමෙන් එහි ප්‍රබල ලෙස සම්බන්ධිත දේපල අහිමි වේ.

සහල්. 5.5 අවම වශයෙන් සම්බන්ධිත අධ්‍යක්ෂ ප්‍රස්ථාරය.

අවම වශයෙන් සම්බන්ධ වන්නේ, උදාහරණයක් ලෙස, Fig. 5.5

පැහැදිලිවම, අවම වශයෙන් සම්බන්ධිත ප්‍රස්ථාරවලට සමාන්තර චාප සහ ලූප තිබිය නොහැක.

යොමු නොකළ ප්‍රස්ථාරයක් අවම වශයෙන් සම්බන්ධ වන්නේ එය ගසක් නම් සහ පමණක් බව අපි දනිමු (උදා. 2.13). ප්‍රමේයය 2.5 අනුව, ගසකට අවම වශයෙන් අංශක 1 හි ශීර්ෂ දෙකක්වත් ඇත. එබැවින්, අවම වශයෙන් සම්බන්ධිත අපරික්ෂාකාරී ප්‍රස්ථාරවලට අවම වශයෙන් අංශක 1 හි ශීර්ෂ දෙකක්වත් ඇත.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාර සඳහා සමාන ප්‍රතිඵලයක් අපි ස්ථාපිත කරමු. සෑම ශීර්ෂයකටම පිටතට යන සහ එන චාප තිබිය යුතු බැවින් දැඩි ලෙස සම්බන්ධිත ප්‍රස්ථාරයක ඕනෑම ශීර්ෂයක උපාධිය අවම වශයෙන් 2 විය යුතුය. පහත ප්‍රමේයය තුළ, අවම වශයෙන් සම්බන්ධිත අධ්‍යක්‍ෂ ප්‍රස්ථාරයකට අවම වශයෙන් අංශක 2 හි ශීර්ෂ දෙකක්වත් ඇති බව අපි ඔප්පු කරමු.

පළමු පාඩමේදී, ප්‍රස්ථාරයක් පිළිබඳ සංකල්පය හඳුන්වාදීම, අපි උදාහරණයක් ලෙස ක්‍රීඩා කණ්ඩායම්වල තරඟය සලකා බැලුවෙමු. අප. A සහ C කියන්න, කණ්ඩායම් දෙකක් සම්බන්ධ කර ඇත, මෙම කණ්ඩායම් දැනටමත් එකිනෙකා සමඟ ක්‍රීඩා කරන විට එජ් AC සමඟ. කෙසේ වෙතත්, එවැනි ප්‍රස්ථාරයක් ඉතා වැදගත් ප්‍රශ්නයකට පිළිතුරු නොදේ: ක්‍රීඩාව හරියටම ජයග්‍රහණය කළේ කවුද?
මෙම අඩුපාඩුව පහසුවෙන් ඉවත් කළ හැකිය. A කණ්ඩායම Cට එරෙහිව ජයග්‍රහණය කර ඇත්නම්, A සිට C දක්වා යොමු කරන ලද ඊතලයක් AC මත තැබීමට අපි එකඟ වෙමු. දැනටමත් ක්‍රීඩා කර ඇති සියලුම ක්‍රීඩා වල ප්‍රතිඵල අප දන්නා බව සිතමු, සහ ප්‍රස්තාරයට එකතු කරන්න. 1 අනුරූප ඊතල; රූපයේ පෙන්වා ඇති ප්‍රස්ථාරයේ මෙම ප්‍රතිඵලයට ඉඩ දෙන්න. 58.

රූපය 58.

මෙම ප්‍රස්ථාරයෙන් පෙන්නුම් කරන්නේ A කණ්ඩායම C පරාජය කළ බවත්, F කණ්ඩායම A කණ්ඩායමට පරාජය වූ බවත්, B කණ්ඩායම C, E, F යනාදියට එරෙහිව සියලුම තරඟ ජයගත් බවත්ය.

දාරයප්රස්ථාරය ලෙස හැඳින්වේ දිශානුගත, එක් ශීර්ෂයක් සැලකේ නම් ඉළ ඇටයේ ආරම්භය, සහ අනෙකුත් - අවසානය.
සියලුම දාර දිශානත වූ ප්‍රස්ථාරයක් ලෙස හැඳින්වේ දිශානතියගණන් කරන්න.
අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක එකම ශීර්ෂය සමහර දාරවල ආරම්භය ලෙසත් අනෙක් ඒවා සඳහා අවසානය ලෙසත් සේවය කළ හැක. ඒ අනුව, මුදුනේ අංශක දෙකක් වෙන්කර හඳුනාගත හැකිය: පිටවීමේ උපාධිය සහ ඇතුල්වීමේ උපාධිය.
උපාධියෙන් පිටවීමඅධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක ශීර්ෂය A යනු A වලින් පිටවන දාර ගණනයි (සටහන්: d+(A)).
අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක A ශීර්ෂයක ඇතුල් වීමේ උපාධිය යනු ඇතුළත් කිරීම් ගණනයි නමුත්දාර (සංකේතය: d-(A)).
තරගයක් ජය පරාජයෙන් තොරව අවසන් වුවහොත් කුමක් කළ යුතුද? අනුරූප දාර නොයොදා තැබීමෙන් අපට ප්‍රස්ථාරයේ ටයි ප්‍රතිඵල පරාවර්තනය කළ හැක. එසේ කිරීමෙන්, අපි ඊනියා ලබා ගනිමු smshanny ගණන්, අධ්‍යක්ෂණය සහ නොයොමු දාර දෙකම ඇති.
යොමු කළ ප්‍රස්ථාරයක මාර්ගයක් A1 සිට An දක්වා G යනු දිශානුගත දාරවල අනුපිළිවෙලකි<А1; А2>, <А2; А3>, ..., <Аn-1; Аn>, එක් එක් පෙර දාරයේ අවසානය ඊළඟ එකේ ආරම්භය සමග සමපාත වන අතර කිසිඳු දාරයක් එක් වරකට වඩා සිදු නොවේ.

සහල්. 59
අධ්‍යක්ෂණය කළ ප්‍රස්ථාරයක G නම් මාර්ගයක් ඇත නමුත් B වෙත, පසුව ආපසු හිදීවෙත නමුත්නොවිය හැක (රූපය 59).
A සිට B දක්වා සෘජු මාර්ගයක් තිබේ නම්, B ලෙස හැඳින්වේ ළඟා වේma A වෙතින්
රූපය 38 B හි G තීරුවේ සාක්ෂාත් කරගත හැකිය
A සිට A, B වෙතින් A වෙත ළඟා විය නොහැක.
පහසු මාර්ගයඅධ්‍යක්ෂ ප්‍රස්ථාරයක් යනු එක් වරකට වඩා ශීර්ෂයක් අඩංගු නොවන මාර්ගයකි. වසා දැමූ මාර්ගයඅධ්‍යක්ෂිත ප්‍රස්ථාරයක අධ්‍යක්‍ෂ චක්‍රයක් ලෙස හැඳින්වේ.
දිගු මගමෙම මාර්ගයේ දාර ගණන වේ.
දුරඅධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරයක A සිට B දක්වා යනු A සිට B දක්වා ඇති කෙටිම මාර්ගයේ දිග වේ. A සිට B දක්වා මාර්ගයක් නොමැති නම්, A සිට B දක්වා ඇති දුර අනන්ත ලෙස හඳුන්වනු ලබන අතර එය දක්වනු ලැබේ. A සිට B දක්වා ඇති දුර S (AB) මගින් දක්වනු ලැබේ. රූප සටහන 38 හි ප්රස්ථාරය සඳහා
S (AB) \u003d 1, S (CB) - 2, S (BC) \u003d ?.
ගැටළුව 9.1.
මුහුදු වෙරළේ නිවාඩු නිකේතනයක, එක්-මාර්ග ගමනාගමනය ස්ථාපිත කිරීමෙන් පසු, ඔබට එක් එක් මංසන්ධියකට ඇතුළු විය හැකි වීදි ගණන ඔබට එයින් පිටවිය හැකි වීදි ගණනට සමාන බව පෙනී ගියේය. එකම ස්ථානයකින් ආරම්භ වී අවසන් වන සහ සෑම වීදි කොටසක් හරහාම හරියටම එක් වරක් ගමන් කරන මුර සංචාර මාර්ගයක් යෝජනා කළ හැකි බව ඔප්පු කරන්න.
විසඳුමක්.
නගරයේ චලනය නිර්වචනය කරන ඩිග්‍රැෆ් ජී ගොඩනඟමු.
digraph ලෙස හැඳින්වේ සම්බන්ධ,ඒවායේ දිශානතිය සැලකිල්ලට නොගෙන චාප දිගේ එහි ඕනෑම ශීර්ෂයක සිට වෙනත් ඕනෑම ස්ථානයකට යා හැකි නම්. සම්බන්ධිත digraph ලෙස හැඳින්වේ ඉයුලර්,එය Euler චක්රයක් තිබේ නම්.
ප්‍රමේයය 12. සම්බන්ධිත ඩිග්‍රැෆ් එකක් යනු එහි එක් එක් ශීර්ෂයන් සඳහා නම් සහ පමණක් නම් යුලර් වේvසමානාත්මතාවයඈ- (v) = ඈ+ (v) .
ප්‍රමේයය 4.2 ගැටලුවේ ඇති ප්‍රමේයය හා සමානව ඔප්පු කර ඇත.
තනන ලද G ප්‍රස්ථාරයේ සිරස් සඳහා, d-(v) = d+(v) සමානාත්මතාවය තෘප්තිමත් වන බව ගැටලුවේ කොන්දේසි වලින් එය අනුගමනය කරයි. එබැවින්, Euler ප්‍රස්තාරය G, සහ Euler චක්‍රය අපේක්ෂිත මුර සංචාර මාර්ගය තීරණය කරනු ඇත.
ගැටළුව 9.2.
තලයේ සීමිත ලකුණු සංඛ්‍යාවක් සලකුණු කර ඇත. සමහර ලක්ෂ්‍ය යුගල දෛශිකවල ආරම්භය සහ අවසානය වන අතර ඕනෑම ලක්ෂ්‍යයකට ඇතුළු වන දෛශික සංඛ්‍යාව එයින් පිටවන දෛශික සංඛ්‍යාවට සමාන වේ. දෛශික එකතුව සොයන්න.
විසඳුමක්.
තලයේ ලක්ෂ්‍ය දෛශික සමඟ එක්ව ඩිග්‍රැෆ් ජී සාදයි. ඩයිග්‍රැෆ් එකක චක්‍රය, එහි සියලුම සිරස් වෙනස් වේ, එය හැඳින්වේ. සමෝච්ඡය.
ප්‍රමේයය 13. සම්බන්ධිත ඩිග්‍රාෆ්ජීEuler if and only ifජීයුගල වශයෙන් පොදු දාර නොමැති සමෝච්ඡයන්ගේ එකමුතුවයි.
සාක්ෂි. අවශ්‍යතාවය. G Euler digraph එකක් වීමට ඉඩ දෙන්න. එහි ඕනෑම ශීර්ෂයක් u1 සලකන්න. අපි u1 ශීර්ෂය යම් චාපයක් දිගේ තබමු (u1, u2) digraph G සම්බන්ධ කර ඇති බැවින් මෙය කළ හැක. d-(u2) = d+(u2), චාපය දිගේ u2 ශීර්ෂය අත්හැරිය හැක (u2, u3) . ඩිග්‍රැෆ් G හි සීමිත සිරස් සංඛ්‍යාවක් ඇත, එබැවින් අපි කලින් සිටි යම් ශීර්ෂයකින් අවසන් වෙමු. w වලින් ආරම්භ වන සහ අවසන් වන දාමයේ කොටස C1 මාර්ගයයි. Digraph G වෙතින් සමෝච්ඡ C1 හි චාප ඉවත් කරන්න . ප්‍රතිඵලයක් ලෙස ලැබෙන ඩිග්‍රාෆ් G1 (සමහර විට විසන්ධි වී ඇත), C ට අයත් සිරස් වල ඇතුල් වීමේ සහ පිටවීමේ අංශක එකකින් අඩු වී ඇත, ඉතිරි සිරස් වල ඇතුල් වීමේ සහ පිටවීමේ අංශක වෙනස් වී නොමැත. එබැවින්, C1 digraph හි ඕනෑම ශීර්ෂයක් සඳහා, d-(v) = d+(v) සමානාත්මතාවය රඳවා ගනු ඇත. එබැවින්, ඩිග්‍රාෆ් G1 හි, අපට C සමෝච්ඡය හුදකලා කළ හැකිය 2 ආදිය
ඉයුලර් චක්‍රයක් බවට සමෝච්ඡයන් ඒකාබද්ධ කිරීමෙන් ප්‍රමාණවත් බව ඔප්පු වේ (ගැටලු 4.2 හි ප්‍රමේයය සනාථ කිරීම බලන්න).
ප්රමේයය ඔප්පු කර ඇත. සමහර විට අපගේ ගැටලුවේ දෛශික නිර්වචනය කරන digraph G සම්බන්ධ නොවේ. digraph හි එක් එක් සම්බන්ධිත කොටස සඳහා ඔප්පු කරන ලද ප්‍රමේයය යෙදීමෙන්, අපි දෛශික කොටස් සමෝච්ඡ ලෙස ලබා ගනිමු. එක් සමෝච්ඡයකට අයත් දෛශික එකතුව ශුන්‍යයට සමාන වේ. එබැවින් සියලුම දෛශිකවල එකතුව ශුන්‍යයට සමාන වේ.

ඔබ ඇල්ගොරිතම කෙලින්ම අධ්‍යයනය කිරීමට පෙර, පරිගණකයක ඒවා නිරූපණය කරන්නේ කෙසේද යන්න තේරුම් ගැනීමට ඔබට ප්‍රස්ථාර පිළිබඳ මූලික දැනුමක් තිබිය යුතුය. මෙහිදී, ප්‍රස්ථාර න්‍යායේ සියලුම අංග විස්තරාත්මකව විස්තර නොකෙරේ (මෙය අවශ්‍ය නොවේ), නමුත් ඒවා පමණක් නොදැනුවත්කම මෙම ක්‍රමලේඛන ක්ෂේත්‍රය උකහා ගැනීම සැලකිය යුතු ලෙස සංකීර්ණ කරයි.

උදාහරණ කිහිපයක් ප්‍රස්ථාරය පිළිබඳ මතුපිට අදහසක් ලබා දෙනු ඇත. එබැවින් සාමාන්ය ප්රස්ථාරයක් යනු උමං මාර්ග සිතියමක් හෝ වෙනත් මාර්ගයකි. විශේෂයෙන්, ක්‍රමලේඛකයෙකු පරිගණක ජාලයක් සමඟ හුරුපුරුදු වන අතර එය ප්‍රස්ථාරයක් ද වේ. මෙහි ඇති පොදු දෙය නම් රේඛා මගින් සම්බන්ධ කර ඇති තිත් තිබීමයි. එබැවින් පරිගණක ජාලයක, ලක්ෂ්යයන් වෙනම සේවාදායකයන් වන අතර, රේඛා යනු විවිධ ආකාරයේ විද්යුත් සංඥා වේ. උමං මාර්ගයේ, පළමු දුම්රිය ස්ථාන, දෙවැන්න ඔවුන් අතර තැබූ උමං වේ. ප්‍රස්ථාර න්‍යායේ දී ලක්ෂ්‍ය ලෙස හැඳින්වේ මුදුන් (ගැට), සහ රේඛා ඉළ ඇට (චාප) මේ ක්රමයෙන්, ප්රස්ථාරයදාර මගින් සම්බන්ධ කර ඇති සිරස් එකතුවකි.

ගණිතය ක්‍රියාත්මක වන්නේ දේවල අන්තර්ගතය සමඟ නොව, ඒවායේ ව්‍යුහය සමඟ, එය සමස්තයක් ලෙස ලබා දී ඇති සියල්ලෙන් වියුක්ත කරමිනි. මෙම තාක්ෂණය භාවිතා කිරීමෙන්, අපට සමහර වස්තු ගැන ප්රස්තාර ගැන නිගමනය කළ හැක. ප්‍රස්තාර න්‍යාය ගණිතයේ කොටසක් වන බැවින්, ප්‍රතිපත්තිමය වශයෙන්, වස්තුවක් යනු කුමක්ද යන්න එයට කිසිසේත්ම වැදගත් නොවේ; එකම වැදගත් දෙය නම් එය ප්‍රස්ථාරයක්ද, එනම් ප්‍රස්ථාර සඳහා අවශ්‍ය ගුණාංග එහි තිබේද යන්නයි. එමනිසා, උදාහරණ දීමට පෙර, අපි සලකා බලනු ලබන වස්තුව හුදකලා කරන්නේ, අපගේ මතය අනුව, ප්‍රතිසමයක් පෙන්වීමට අපට ඉඩ සලසන දේ පමණි, අපි පොදු දෙයක් සොයමු.

අපි නැවතත් පරිගණක ජාලයට යමු. එයට නිශ්චිත ස්ථලකයක් ඇති අතර, ඒවා සම්බන්ධ කරන පරිගණක සහ මාර්ග ගණනාවක් සම්ප්‍රදායිකව නිරූපණය කළ හැක. පහත රූපයේ දැක්වෙන්නේ උදාහරණයක් ලෙස සම්පුර්ණයෙන්ම සවි කර ඇති ස්ථලකයයි.

එය මූලික වශයෙන් ප්‍රස්ථාරයකි. පරිගණක පහ යනු සිරස් වන අතර ඒවා අතර සම්බන්ධතා (සංඥා මාර්ග) දාර වේ. පරිගණක සිරස් සමඟ ප්‍රතිස්ථාපනය කිරීමෙන් අපට ගණිතමය වස්තුවක් ලැබේ - දාර 10 ක් සහ සිරස් 5 ක් ඇති ප්‍රස්ථාරයක්. ඔබට අත්තනෝමතික ලෙස සිරස් අංක කළ හැකි අතර, රූපයේ එය සිදු කර ඇති ආකාරය අවශ්ය නොවේ. මෙම උදාහරණයේ කිසිදු ලූපයක් භාවිතා නොකරන බව සඳහන් කිරීම වටී, එනම්, එවැනි දාරයක් ශීර්ෂයෙන් ඉවත් වී වහාම එයට ඇතුළු වන නමුත් ගැටළු වලදී ලූප ඇතිවිය හැකිය.

ප්‍රස්තාර න්‍යායේ භාවිතා වන වැදගත් අංක කිහිපයක් මෙන්න:

• G=(V, E), මෙහි G යනු ප්‍රස්ථාරයක්, V යනු එහි සිරස් සහ E දාර වේ;
• |V| - අනුපිළිවෙල (ශීර්ෂ ගණන);
• |ඊ| - ප්රස්ථාර ප්රමාණය (දාර ගණන).

අපගේ නඩුවේදී (රූපය 1) |V|=5, |E|=10;

ඕනෑම ශීර්ෂයකින් වෙනත් ඕනෑම ශීර්ෂයකට ප්‍රවේශ විය හැකි විට, එවැනි ප්‍රස්ථාරයක් හැඳින්වේ දිශානුගත නොවනසම්බන්ධිත ප්රස්ථාරය (රූපය 1). ප්රස්ථාරය සම්බන්ධ කර ඇත්නම්, නමුත් මෙම කොන්දේසිය සෑහීමකට පත් නොවේ නම්, එවැනි ප්රස්ථාරයක් හැඳින්වේ දිශානුගතහෝ digraph (රූපය 2).

අධ්‍යක්ෂණය කරන ලද සහ යොමු නොකළ ප්‍රස්ථාරවල ශීර්ෂයක උපාධිය පිළිබඳ සංකල්පය ඇත. Vertex උපාධියඑය වෙනත් සිරස් වලට සම්බන්ධ කරන දාර ගණනයි. ප්‍රස්ථාරයක සියලුම අංශකවල එකතුව එහි සියලුම දාරවල සංඛ්‍යාව මෙන් දෙගුණයකට සමාන වේ. රූප සටහන 2 සඳහා, සියලු බලවල එකතුව 20 වේ.

ඩිග්‍රැෆ් එකක, දික්කසාද නොවූ ප්‍රස්ථාරයක් මෙන් නොව, අතරමැදි ශීර්ෂ නොමැතිව ශීර්ෂය h සිට ශීර්ෂය s දක්වා ගමන් කළ හැක්කේ, දාරයක් h වලින් ඉවත් වී s වෙත ඇතුළු වූ විට පමණි, නමුත් අනෙක් අතට නොවේ.

අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාරවලට පහත අංකනය ඇත:

G=(V, A), මෙහි V යනු සිරස් වේ, A යනු දාර වේ.

තුන්වන වර්ගයේ ප්‍රස්ථාර - මිශ්රප්රස්තාර (රූපය 3). ඒවාට යොමු කළ දාර සහ දිශානුගත නොවන ඒවා දෙකම ඇත. විධිමත් ලෙස, මිශ්‍ර ප්‍රස්ථාරයක් පහත පරිදි ලියා ඇත: G=(V, E, A), වරහන් තුළ ඇති එක් එක් අක්ෂරය ඊට පෙර ආරෝපණය කළ දේ ද දක්වයි.

රූප සටහන 3 හි ප්‍රස්ථාරයේ, සමහර චාප යොමු කර ඇත [(e, a), (e, c), (a, b), (c, a), (d, b)], අනෙක් ඒවා අධ්‍යක්ෂණය නොවේ [( e, d), (e, b), (d, c)...].

මුලින්ම බැලූ බැල්මට ප්‍රස්ථාර දෙකක් හෝ වැඩි ගණනක් ඒවායේ ව්‍යුහයේ වෙනස් ලෙස පෙනෙන අතර, ඒවායේ විවිධ නිරූපණය හේතුවෙන් පැන නගී. නමුත් එය සැමවිටම එසේ නොවේ. අපි ප්රස්තාර දෙකක් ගනිමු (රූපය 4).

ඒවා එකිනෙකට සමාන වේ, මන්ද එක් ප්‍රස්ථාරයක ව්‍යුහය වෙනස් නොකර ඔබට තවත් එකක් ගොඩනගා ගත හැකිය. එවැනි ප්රස්තාර ලෙස හැඳින්වේ සමාවයවික, එනම්, එක් ප්‍රස්ථාරයක නිශ්චිත දාර සංඛ්‍යාවක් ඇති ඕනෑම ශීර්ෂයකට තවත් ප්‍රස්ථාරයක සමාන ශීර්ෂයක් ඇති ගුණාංගය තිබීම. රූප සටහන 4 හි සමරූපී ප්‍රස්ථාර දෙකක් පෙන්වයි.

ප්‍රස්ථාරයක එක් එක් දාරයට යම් අගයක් පවරන විට, දාරයේ බර ලෙස හැඳින්වේ, එවිට එවැනි ප්‍රස්ථාරයක් අත්හිටුවා ඇත. විවිධ කාර්යයන් වලදී, විවිධ වර්ගයේ මිනුම් බර ලෙස ක්‍රියා කළ හැකිය, උදාහරණයක් ලෙස, දිග, මාර්ග මිල යනාදිය. ප්‍රස්ථාරයක චිත්‍රක නිරූපණයක, සාමාන්‍යයෙන් බර අගයන් දාර අසල දක්වා ඇත.

අප සලකා බැලූ ඕනෑම ප්‍රස්ථාරයක, මාර්ගයක් තෝරා ගත හැකි අතර, එපමනක් නොව, එකකට වඩා වැඩි ගණනක් තෝරා ගත හැකිය. මාර්ගයයනු සිරස් අනුපිළිවෙලක් වන අතර, ඒ සෑම එකක්ම දාරයක් මගින් ඊළඟට සම්බන්ධ වේ. පළමු සහ අවසාන සිරස් සමපාත වන්නේ නම්, එවැනි මාර්ගයක් චක්රයක් ලෙස හැඳින්වේ. මාර්ගයක දිග තීරණය වන්නේ එය සෑදෙන දාර ගණන අනුව ය. උදාහරණයක් ලෙස, රූප සටහන 4.a හි, මාර්ගය [(e), (a), (b), (c)] අනුපිළිවෙල වේ. මෙම මාර්ගය උප ප්‍රස්ථාරයකි, මන්ද එයට දෙවැන්නෙහි අර්ථ දැක්වීම අදාළ වේ, එනම්: G'=(V', E') ප්‍රස්ථාරය G=(V, E) ප්‍රස්ථාරයේ උප ප්‍රස්ථාරයක් වන්නේ V' සහ E' නම් පමණි. V, E ට අයත් වේ.