ගණිතයේ ප්රස්ථාර න්යාය
ප්රස්ථාර න්යාය යනු වස්තූන් අතර සම්බන්ධතාවල ව්යුහය අධ්යයනය කරන විවික්ත ගණිතයේ ශාඛාවකි. මෙම වස්තූන් සිරස් (නෝඩ්) ලෙස නිරූපණය වන අතර ඒවා අතර සම්බන්ධතා දාර (චාප) ලෙස නිරූපණය වේ. එය සරල ලෙස පෙනුනද, පරිගණක විද්යාව සහ ඉංජිනේරු විද්යාවේ සිට ජීව විද්යාව සහ ආර්ථික විද්යාව දක්වා සහ සමාජ විද්යාවන් දක්වා විවිධ ක්ෂේත්රවල ප්රස්ථාර න්යාය සැලකිය යුතු කාර්යභාරයක් ඉටු කරයි. බොහෝ සංකීර්ණ සැබෑ ලෝකයේ ගැටළු ප්රස්ථාර භාවිතයෙන් ආකෘතිගත කළ හැකි අතර, ගණිතමය සංකල්ප භාවිතයෙන් විශ්ලේෂණය කිරීමට සහ විසඳීමට පහසු කරයි.
ප්රස්ථාරවල අර්ථ දැක්වීම සහ මූලික සංරචක
විධිමත් ලෙස, ප්රස්ථාරයක් සාමාන්යයෙන් G = (V, E) ලෙස ලියා ඇති අතර, එහිදී:
– V (ශීර්ෂ කට්ටලය) යනු ශීර්ෂ කට්ටලයකි.
– E (දාර කට්ටලය) යනු සිරස් යුගල සම්බන්ධ කරන දාර කට්ටලයයි.
උදාහරණයක් ලෙස, V = {A, B, C} සහ E = {(A,B), (B,C)} නම්, A B හා සම්බන්ධ වී ඇති බවත් B C හා සම්බන්ධ වී ඇති බවත් ප්රස්ථාරයෙන් දැක්වේ. මෙම නිරූපණයේ ආකාරය මාර්ග ජාල, සමාජ මාධ්යවල මිත්රත්ව සබඳතා, ජාලවල පරිගණක සම්බන්ධතා සහ රසායන විද්යාවේ අණුක ව්යුහයන් පවා විස්තර කිරීමට ඉතා ප්රයෝජනවත් වේ.
නෝඩ් වලට නගර, පරිශීලකයින්, පරිගණක හෝ ජාන වැනි විවිධ දේවල් නියෝජනය කළ හැකිය. දාර මගින් නගර අතර මාර්ග, මිත්රත්වයන්, ජාල කේබල් හෝ ජීව විද්යාත්මක අන්තර්ක්රියා වැනි සම්බන්ධතා නියෝජනය වේ.
ප්රස්ථාර වර්ග
ප්රස්ථාර න්යාය මඟින් ප්රස්ථාර වර්ග බොහොමයක් හඳුනා ගනී, ඒවා ආකෘතිගත කරනු ලබන සම්බන්ධතාවල ස්වභාවය අනුව වෙනස් වේ:
1. යොමු නොකළ ප්රස්තාරය
පැතිවලට දිශාවක් නැත. A B හා සම්බන්ධ වී ඇත්නම්, B ද A හා සම්බන්ධ වේ. උදාහරණය: ද්වි-මාර්ග මිත්රත්වයක්.
2. යොමු කරන ලද ප්රස්ථාරය (අධ්යක්ෂණය කරන ලද ප්රස්ථාරය / ඩිග්රැෆ්)
දාරවලට දිශාවක් ඇති අතර, ඒවා අනුපිළිවෙලින් යුගල (A → B) ලෙස ප්රකාශ වේ. සමාජ මාධ්ය හෝ ක්රියාවලි ප්රවාහයන්හි "පහත දැක්වෙන" සම්බන්ධතා ආකෘතිකරණය සඳහා මෙය සුදුසු වේ.
3. බර තැබූ ප්රස්ථාරය
සෑම දාරයකටම දුර, පිරිවැය හෝ ගමන් කාලය වැනි බරිත අගයක් ඇත. බරිත ප්රස්ථාර බොහෝ විට වේගවත්ම හෝ ලාභම මාර්ග සොයා ගැනීමට භාවිතා කරයි.
4. සරල ප්රස්ථාරය
එයට සමාන ගැට යුගල සම්බන්ධ කරන ලූප සහ ද්විත්ව දාර නොමැත.
5. බහු ග්රැෆ්
පද්ධතියක බහු සම්බන්ධතා ආකෘතිකරණය සඳහා ප්රයෝජනවත් වන, එකම නෝඩ් යුගලය සම්බන්ධ කිරීමට එක් දාරයකට වඩා ඉඩ දෙයි.
6. සම්පූර්ණ ප්රස්ථාරය (සම්පූර්ණ ප්රස්ථාරය)
සෑම ශීර්ෂ යුගලයක්ම එක් දාරයකින් සම්බන්ධ කර ඇත. n ශීර්ෂ සහිත සම්පූර්ණ ප්රස්ථාරයක් සාමාන්යයෙන් Kₙ ලෙස ලියා ඇත. සම්බන්ධතාවල උපරිම සීමාව සාකච්ඡා කිරීමට මෙය බොහෝ විට භාවිතා වේ.
7. ද්විපාර්ශ්වික ප්රස්තාරය
නෝඩ් කට්ටලයක් කණ්ඩායම් දෙකකට බෙදිය හැකි අතර, දාර සරලව විවිධ කණ්ඩායම් වලින් නෝඩ් සම්බන්ධ කරයි. උදාහරණ: සේවකයින් සහ රැකියා, සිසුන් සහ පාඨමාලා ගැලපීම.
8. ගස
චක්ර නොමැතිව සම්බන්ධිත ප්රස්ථාරයක්. දත්ත ව්යුහයන්, ආයතනික ධූරාවලියන් සහ තීරණ නිරූපණය සඳහා ගස් අත්යවශ්ය වේ.
ප්රස්ථාර සිද්ධාන්තයේ වැදගත් සංකල්ප
ග්රැෆ් න්යායේ සමහර ප්රධාන සංකල්ප පහත පරිදි වේ:
1. නෝඩ් උපාධිය
නෝඩයක උපාධිය යනු එම නෝඩයට සම්බන්ධ කර ඇති දාර ගණනයි. සෘජු ප්රස්ථාරයක, අංශක (එන දාර ගණන) සහ පිටත අංශක (පිටතට යන දාර ගණන) ඇත. ජාලයක නෝඩයක "සම්බන්ධතාවය" මැනීම සඳහා උපාධිය ප්රයෝජනවත් වේ.
2. ධාවන පථ, මංපෙත් සහ බයිසිකල්
- මාර්ගයක් යනු දාර මගින් සම්බන්ධ කර ඇති සිරස් අනුපිළිවෙලකි.
- මංපෙතක් යනු දාර නැවත සිදු නොවන මාර්ගයකි.
– චක්රයක් යනු දාර පුනරාවර්තනය නොවී (සහ සාමාන්යයෙන් ආරම්භය/අවසානය හැර පුනරාවර්තන නෝඩ් නොමැතිව) ආරම්භක නෝඩයට නැවත පැමිණෙන මාර්ගයකි.
ජාල වල සංචාලනය, විය හැකි මාර්ග සහ පද්ධතිවල ලූප් හඳුනාගැනීම අවබෝධ කර ගැනීම සඳහා මෙම සංකල්පය වැදගත් වේ.
3. සම්බන්ධතාවය
සෑම ශීර්ෂ යුගලයකටම ඒවා සම්බන්ධ කරන මාර්ගයක් තිබේ නම් ප්රස්ථාරයක් සම්බන්ධ යැයි කියනු ලැබේ. සෘජු ප්රස්ථාරවල, දැඩි ලෙස සම්බන්ධ වීම වැනි සම්බන්ධතාවය පිළිබඳ වඩාත් නිශ්චිත සංකල්ප ඇත (සෑම ශීර්ෂයකටම දාරයක් හරහා අනෙක් සෑම ශීර්ෂයකටම ළඟා විය හැකිය).
සන්නිවේදන ජාල විශ්ලේෂණයේදී සම්බන්ධතාවය ඉතා වැදගත් වේ - උදාහරණයක් ලෙස, එක් සම්බන්ධතාවයක් නැති වුවහොත් ජාලයේ ඇති සියලුම පරිගණකවලට තවමත් එකිනෙකා සමඟ සන්නිවේදනය කළ හැකිද යන්න.
4. උප වගන්ති සහ සංරචක
උප ග්රන්ථයක් යනු සිරස් සහ දාරවල උප ග්රන්ථයකින් සාදන ලද ප්රස්ථාරයක උප ග්රන්ථයකි. සම්බන්ධිත සංරචකයක් යනු සම්බන්ධතාවයේ පවතින උපරිම උප ග්රන්ථයයි. සමාජ ජාල විශ්ලේෂණයේදී, සංරචකවලට සම්බන්ධ වී ඇති නමුත් එකිනෙකින් වෙන් වූ කණ්ඩායම් නිරූපණය කළ හැකිය.
සම්භාව්ය ප්රමේයයන් සහ ගැටළු
18 වන සියවසේදී ලියොන්හාර්ඩ් ඉයුලර් විසින් විසඳන ලද ප්රසිද්ධ කොනිග්ස්බර්ග් පාලම් ගැටළුවෙන් ආරම්භ වන ප්රස්ථාර න්යායට දිගු ඉතිහාසයක් ඇත. පාලම් හතම හරියටම එක් වරක් තරණය කර ආරම්භක ස්ථානයට ආපසු යා නොහැකි බව ඉයුලර් ඔප්පු කළ අතර එමඟින් නූතන ප්රස්ථාර න්යායේ පදනම ස්ථාපිත විය.
ප්රස්ථාර න්යායේ සමහර සම්භාව්ය මාතෘකා අතරට:
1. ඉයුලර් සහ හැමිල්ටන් ගමන් පථ
– යුලේරියානු මාර්ගයක් එක් එක් දාරය හරහා හරියටම එක් වරක් ගමන් කරයි. යොමු නොකළ ප්රස්ථාරයක යුලේරියානු මාර්ගයක් පැවතීම සඳහා වන කොන්දේසිය ඔත්තේ අංශකවල සිරස් ගණනට සම්බන්ධ වේ.
– හැමිල්ටෝනියානු මාර්ගයක් සෑම ශීර්ෂයකටම හරියටම එක් වරක් පිවිසෙයි. ඉයුලර්ගේ ගැටලුව මෙන් නොව, හැමිල්ටන්ගේ ගැටළුව බොහෝ දුෂ්කර වන අතර, එහි බොහෝ ප්රභේද පරිගණකමය වශයෙන් NP-දෘඪ වේ.
2. ප්රස්ථාර වර්ණ ගැන්වීම
ප්රස්ථාර වර්ණ ගැන්වීම යනු යාබද ශීර්ෂවලට එකම වර්ණයක් නොමැති වන පරිදි ශීර්ෂවලට (හෝ දාරවලට) වර්ණ පැවරීමයි. ප්රසිද්ධ යෙදුමක් වන්නේ සිතියම් වර්ණ ගැන්වීමේ ගැටළුවයි, එමඟින් සෑම තල සිතියමක්ම උපරිම වර්ණ හතරකින් (සිව් වර්ණ ප්රමේයය) වර්ණ ගැන්විය හැකි බවට ප්රමේයයට මග පාදයි.
3. තල ප්රස්තාරය
දාර ඡේදනය නොකර පැතලි මතුපිටක් මත තල ප්රස්ථාර ඇඳිය හැකිය. ඉලෙක්ට්රොනික පරිපථ නිර්මාණය සහ ජාල සැකැස්ම තුළ තල ප්රස්ථාර බහුලව භාවිතා වේ.
ප්රස්ථාර සිද්ධාන්තයේ වැදගත් ඇල්ගොරිතම
පරිගණක විද්යාවේදී, ප්රස්ථාර න්යාය බොහෝ වැදගත් ඇල්ගොරිතමවල පදනම වේ:
– ප්රස්ථාර සංක්රමණය, සංරචක සෙවීම, චක්ර හඳුනාගැනීම සහ ස්ථලකය සඳහා BFS (පළල-පළමු සෙවීම) සහ DFS (ගැඹුර-පළමු සෙවීම).
– සෘණ නොවන බර සහිත බරිත ප්රස්ථාරයක කෙටිම මාර්ගය සොයා ගැනීමට Dijkstra.
– ඍණ බර හැසිරවිය හැකි කෙටිම මාර්ගය සඳහා බෙල්මන්–ෆෝඩ්.
– අවම පිරිවැයක් සහිත ජාල නිර්මාණය සඳහා ප්රයෝජනවත් වන අවම ස්පේනින් ගස සොයා ගැනීමට කෘස්කල් සහ ප්රිම්.
ප්රස්ථාරවල ගණිතමය සංකල්ප ප්රායෝගික ගැටළු විසඳීමේදී සෘජු කාර්යභාරයක් ඉටු කරන ආකාරය මෙම ඇල්ගොරිතම මගින් පෙන්නුම් කෙරේ.
සැබෑ ජීවිතයේ ප්රස්ථාර න්යායේ යෙදීම්
ප්රස්ථාර න්යාය බලවත් වන්නේ එයට විවිධ සන්දර්භයන් තුළ “සම්බන්ධතා” ආකෘතිගත කිරීමට හැකි බැවිනි:
1. ප්රවාහනය සහ සංචලනය
නෝඩ් මගින් මංසන්ධි නියෝජනය කරන අතර, දාර මගින් මාර්ග නියෝජනය කරන අතර, බර මගින් දුර හෝ ගමන් කාලය නියෝජනය කරයි. හොඳම මාර්ගය තීරණය කිරීම සඳහා සංචාලන පද්ධති ග්රැෆ් ඇල්ගොරිතම භාවිතා කරයි.
2. පරිගණක ජාල සහ අන්තර්ජාලය
රවුටර සහ සේවාදායකයන් නෝඩ් ලෙස ක්රියා කරන අතර කේබල් හෝ සම්බන්ධතා දාර ලෙස ක්රියා කරයි. දත්ත ගමනාගමනය ප්රශස්ත කිරීමට සහ ජාල ඔරොත්තු දීමේ හැකියාව වැඩි දියුණු කිරීමට ප්රස්ථාර විශ්ලේෂණය භාවිතා කරයි.
3. සමාජ ජාල
පරිශීලකයන් නෝඩ් ලෙසත්, සම්බන්ධතා දාර ලෙසත්. ප්රස්ථාර න්යාය භාවිතා කරනුයේ ප්රජාවන් හඳුනා ගැනීමට, බලපෑම (මධ්යගතභාවය) මැනීමට සහ තොරතුරු ව්යාප්තිය විශ්ලේෂණය කිරීමට ය.
4. ජීව විද්යාව සහ රසායන විද්යාව
ජාන ජාල, ප්රෝටීන් අන්තර්ක්රියා හෝ අණුක ව්යුහයන් ආකෘතිකරණය කිරීමට ප්රස්ථාර භාවිතා කරයි. බොහෝ ජෛව තොරතුරු විද්යා පර්යේෂණ විශාල පරිමාණ ප්රස්ථාර විශ්ලේෂණය මත රඳා පවතී.
5. ව්යාපෘති සහ කාර්මික කළමනාකරණය
කාර්යක්ෂම වැඩ අනුපිළිවෙල සහ තීරණාත්මක මාර්ග සොයා ගැනීම සඳහා කාර්ය කාලසටහන්ගත කිරීමේදී (උදා: PERT/CPM) සෘජු ප්රස්ථාර භාවිතා වේ.
වසා දැමීම
ගණිතයේ ප්රස්ථාර න්යාය යනු නෝඩ් සහ දාර හරහා සම්බන්ධතා ව්යුහය අධ්යයනය කිරීමයි. එහි විවිධ පරාසයක ප්රස්ථාර වර්ග, උපාධිය, මාර්ගය සහ චක්රය වැනි සංකල්ප සහ සෙවුම් සහ ප්රශස්තිකරණ ඇල්ගොරිතම සමඟින්, ප්රස්ථාර න්යාය ඉතා නම්යශීලී සහ බලවත් මෙවලමකි. එහි ශක්තිය පවතින්නේ ව්යුහගත, විශ්ලේෂණය කළ හැකි ආකෘතිවල සංකීර්ණ ගැටළු නිරූපණය කිරීමේ හැකියාව තුළ ය. ප්රස්ථාර න්යාය විවික්ත ගණිතය, පරිගණක විද්යාව සහ එදිනෙදා ජීවිතයට බලපාන බොහෝ නවීන යෙදුම් සංවර්ධනය සඳහා තීරණාත්මක පදනමක් බවට පත්වීම පුදුමයක් නොවේ.
ඔබට අවශ්ය නම්, මෙම ලිපිය වඩාත් අදාළ කර ගැනීම සඳහා සාකච්ඡා සමඟ උදාහරණ ගැටළු (උදාහරණයක් ලෙස ඉයුලර්ගේ මාර්ගය, ඩිජ්ක්ස්ට්රා හෝ ප්රස්ථාර වර්ණ ගැන්වීම පිළිබඳ) එකතු කළ හැකිය.
