သင်္ချာဘာသာရပ်တွင် ဂရပ်သီအိုရီ

သင်္ချာဘာသာရပ်တွင် ဂရပ်သီအိုရီ

ဂရပ်သီအိုရီသည် အရာဝတ္ထုများအကြား ဆက်နွယ်မှုဖွဲ့စည်းပုံကို လေ့လာသည့် သီးခြားသင်္ချာ၏ ဌာနခွဲတစ်ခုဖြစ်သည်။ ဤအရာဝတ္ထုများကို ထိပ်ဖျားများ (နုတ်များ) အဖြစ် ကိုယ်စားပြုပြီး ၎င်းတို့အကြား ဆက်နွယ်မှုများကို အနားများ (စက်ဝိုင်းများ) အဖြစ် ကိုယ်စားပြုသည်။ ၎င်းသည် ရိုးရှင်းပုံရသော်လည်း ဂရပ်သီအိုရီသည် ကွန်ပျူတာသိပ္ပံနှင့် အင်ဂျင်နီယာပညာမှ ဇီဝဗေဒနှင့် စီးပွားရေးပညာအထိ၊ လူမှုရေးသိပ္ပံအထိ နယ်ပယ်အမျိုးမျိုးတွင် အရေးပါသော အခန်းကဏ္ဍမှ ပါဝင်သည်။ ရှုပ်ထွေးသော လက်တွေ့ကမ္ဘာပြဿနာများစွာကို ဂရပ်များကို အသုံးပြု၍ ပုံစံထုတ်နိုင်ပြီး သင်္ချာသဘောတရားများကို အသုံးပြု၍ ခွဲခြမ်းစိတ်ဖြာဖြေရှင်းရန် ပိုမိုလွယ်ကူစေသည်။

ဂရပ်များ၏ အဓိပ္ပာယ်ဖွင့်ဆိုချက်နှင့် အခြေခံအစိတ်အပိုင်းများ

တရားဝင်အားဖြင့် ဂရပ်တစ်ခုကို G = (V, E) အဖြစ် ရေးသားလေ့ရှိပြီး အောက်ပါအတိုင်းဖြစ်သည်-
– V (vertex set) သည် vertices များ၏ အစုံဖြစ်သည်။
– E (အနားအစုံ) သည် ထိပ်ဖျားအတွဲများကို ဆက်သွယ်ပေးသော အနားများ၏ အစုံဖြစ်သည်။

ဥပမာအားဖြင့် V = {A, B, C} နှင့် E = {(A,B), (B,C)} ဖြစ်ပါက၊ ဂရပ်က A သည် B နှင့် ချိတ်ဆက်ထားပြီး B သည် C နှင့် ချိတ်ဆက်ထားကြောင်း ပြသသည်။ ဤကိုယ်စားပြုမှုပုံစံသည် လမ်းကွန်ရက်များ၊ လူမှုမီဒီယာပေါ်ရှိ မိတ်ဆွေဆက်ဆံရေးများ၊ ကွန်ရက်များရှိ ကွန်ပျူတာချိတ်ဆက်မှုများနှင့် ဓာတုဗေဒတွင် မော်လီကျူးဖွဲ့စည်းပုံများကိုပင် ဖော်ပြရန်အတွက် အလွန်အသုံးဝင်ပါသည်။

နုတ်များသည် မြို့များ၊ အသုံးပြုသူများ၊ ကွန်ပျူတာများ သို့မဟုတ် မျိုးဗီဇများကဲ့သို့သော အရာအမျိုးမျိုးကို ကိုယ်စားပြုနိုင်သည်။ အနားသတ်များသည် မြို့များအကြား လမ်းများ၊ မိတ်ဆွေဖွဲ့မှုများ၊ ကွန်ရက်ကြိုးများ သို့မဟုတ် ဇီဝဗေဒဆိုင်ရာ အပြန်အလှန် ဆက်သွယ်မှုကဲ့သို့သော ဆက်ဆံရေးများကို ကိုယ်စားပြုသည်။

ဂရပ်အမျိုးအစားများ

ဂရပ်သီအိုရီသည် မော်ဒယ်လ်ပြုလုပ်နေသော ဆက်နွယ်မှုများ၏ သဘောသဘာဝပေါ် မူတည်၍ ဂရပ်အမျိုးအစားများစွာကို အသိအမှတ်ပြုသည်-

၁။ လမ်းညွှန်မထားသော ဂရပ်
ဘေးနှစ်ဖက်မှာ ဦးတည်ရာမရှိပါဘူး။ A ဟာ B နဲ့ ချိတ်ဆက်ထားရင် B ဟာလည်း A နဲ့ ချိတ်ဆက်ထားပါတယ်။ ဥပမာ- နှစ်လမ်းသွား ချစ်ကြည်ရင်းနှီးမှု။

၂။ ညွှန်ကြားထားသော ဂရပ် (ညွှန်ကြားထားသော ဂရပ် / ဒိုင်ဂရပ်)
အနားသတ်များတွင် ဦးတည်ရာရှိပြီး အစီအစဉ်တကျအတွဲများ (A → B) အဖြစ်ဖော်ပြသည်။ ၎င်းသည် လူမှုမီဒီယာ သို့မဟုတ် လုပ်ငန်းစဉ်စီးဆင်းမှုများတွင် "လိုက်လံလုပ်ဆောင်သော" ဆက်ဆံရေးများကို ပုံစံထုတ်ရန်အတွက် သင့်လျော်ပါသည်။

၃။ အလေးချိန်ရှိသော ဂရပ်
အစွန်းတစ်ခုစီတွင် အကွာအဝေး၊ ကုန်ကျစရိတ် သို့မဟုတ် ခရီးသွားချိန်ကဲ့သို့သော အလေးချိန်ရှိသောတန်ဖိုးတစ်ခုရှိသည်။ အလေးချိန်ရှိသောဇယားများကို အမြန်ဆုံး သို့မဟုတ် အသက်သာဆုံးလမ်းကြောင်းများကိုရှာဖွေရန် မကြာခဏအသုံးပြုလေ့ရှိသည်။

၄။ ရိုးရှင်းသော ဂရပ်
၎င်းတွင် ကွင်းများ မရှိသလို တူညီသော ကြိုးချည်အတွဲများကို ချိတ်ဆက်ပေးသည့် နှစ်ထပ်အနားများလည်း မရှိပါ။

၅။ မာလ်တီဂရပ်
စနစ်တစ်ခုတွင် ဆက်နွယ်မှုများစွာကို မော်ဒယ်လ်လုပ်ရန်အတွက် အသုံးဝင်သော အနားတစ်ခုထက်ပို၍ node အစုံကို ချိတ်ဆက်ပေးပါသည်။

၆။ ပြီးပြည့်စုံသော ဂရပ် (ပြီးပြည့်စုံသော ဂရပ်)
ထိပ်ဖျားတစ်စုံစီကို အစွန်းတစ်ခုဖြင့် ချိတ်ဆက်ထားသည်။ ထိပ်ဖျား n ခုပါသော ပြီးပြည့်စုံသော ဂရပ်တစ်ခုကို Kₙ အဖြစ် ရေးသားလေ့ရှိသည်။ ၎င်းကို ချိတ်ဆက်မှု၏ အမြင့်ဆုံး ကန့်သတ်ချက်ကို ဆွေးနွေးရန် မကြာခဏ အသုံးပြုလေ့ရှိသည်။

၇။ နှစ်ပိုင်းဂရပ်
node အစုံတစ်ခုကို အုပ်စုနှစ်စုခွဲနိုင်ပြီး၊ အနားသတ်များကို မတူညီသောအုပ်စုများမှ node များကို ရိုးရှင်းစွာ ချိတ်ဆက်ပေးသည်။ ဥပမာ- အလုပ်သမားများနှင့် အလုပ်အကိုင်များ၊ ကျောင်းသားများနှင့် သင်တန်းများကို တွဲပေးခြင်း။

၈။ သစ်ပင်
စက်ဝန်းများမပါဝင်သော ချိတ်ဆက်ထားသော ဂရပ်။ သစ်ပင်များသည် ဒေတာဖွဲ့စည်းပုံများ၊ အဖွဲ့အစည်းဆိုင်ရာ အဆင့်ဆင့်အုပ်ချုပ်မှုများနှင့် ဆုံးဖြတ်ချက်ကိုယ်စားပြုမှုတို့တွင် မရှိမဖြစ်လိုအပ်သည်။

ဂရပ်ဖ်သီအိုရီတွင် အရေးကြီးသော အယူအဆများ

ဂရပ်သီအိုရီတွင် အဓိကသဘောတရားအချို့မှာ အောက်ပါအတိုင်းဖြစ်သည်။

၁။ နုတ်ဒ်ဒီဂရီ
node တစ်ခု၏ဒီဂရီဆိုသည်မှာ ထို node နှင့် ချိတ်ဆက်ထားသော အနားများ၏ အရေအတွက်ဖြစ်သည်။ directed graph တွင် in-degree (ဝင်လာသော အနားများ၏ အရေအတွက်) နှင့် out-degree (ထွက်သွားသော အနားများ၏ အရေအတွက်) ရှိသည်။ ဒီဂရီသည် ကွန်ရက်တစ်ခုရှိ node တစ်ခု၏ "ချိတ်ဆက်မှု" ကို တိုင်းတာရာတွင် အသုံးဝင်သည်။

၂။ လမ်းကြောင်းများ၊ လမ်းကြောင်းများနှင့် စက်ဘီးများ
- လမ်းကြောင်းဆိုသည်မှာ အနားများဖြင့် ဆက်သွယ်ထားသော ထိပ်ဖျားများ၏ အစီအစဉ်ကို ဆိုလိုသည်။
- လမ်းကြောင်းဆိုသည်မှာ အနားသတ်များကို ထပ်မထပ်သော လမ်းကြောင်းတစ်ခုဖြစ်သည်။
– သံသရာဆိုသည်မှာ အနားများကို ထပ်ခါတလဲလဲ မပြုလုပ်ဘဲ (နှင့် များသောအားဖြင့် စတင်/အဆုံးမှလွဲ၍ နုတ်များကို ထပ်ခါတလဲလဲ မပြုလုပ်ဘဲ) စတင်သည့် နုတ်သို့ ပြန်သွားသည့် လမ်းကြောင်းတစ်ခုဖြစ်သည်။

ဤသဘောတရားသည် ကွန်ရက်များရှိ လမ်းကြောင်းရှာဖွေခြင်း၊ ဖြစ်နိုင်ချေရှိသော လမ်းကြောင်းများနှင့် စနစ်များရှိ ကွင်းဆက်ထောက်လှမ်းခြင်းကို နားလည်ရန်အတွက် အရေးကြီးပါသည်။

၃။ ချိတ်ဆက်မှု
ထိပ်ဖျားအစုံတိုင်းတွင် ၎င်းတို့ကို ဆက်သွယ်ထားသော လမ်းကြောင်းတစ်ခုရှိပါက ဂရပ်တစ်ခုသည် ချိတ်ဆက်ထားသည်ဟုဆိုသည်။ ညွှန်ကြားထားသော ဂရပ်များတွင်၊ အားကောင်းစွာ ချိတ်ဆက်ထားခြင်း (ထိပ်ဖျားတစ်ခုစီသည် အစွန်းတစ်ခုမှတစ်ဆင့် အခြားထိပ်ဖျားတိုင်းကို ရောက်ရှိနိုင်သည်) ကဲ့သို့သော ချိတ်ဆက်မှုဆိုင်ရာ ပိုမိုတိကျသော သဘောတရားများ ရှိပါသည်။

ချိတ်ဆက်မှုသည် ဆက်သွယ်ရေးကွန်ရက်များကို ခွဲခြမ်းစိတ်ဖြာရာတွင် အလွန်အရေးကြီးပါသည် - ဥပမာအားဖြင့် ချိတ်ဆက်မှုတစ်ခု ပြတ်တောက်သွားသော်လည်း ကွန်ရက်ရှိ ကွန်ပျူတာအားလုံးသည် အချင်းချင်း ဆက်သွယ်နိုင်သေးခြင်း ရှိ၊ မရှိ ဖြစ်သည်။

၄။ ဆပ်ဂရပ်များနှင့် အစိတ်အပိုင်းများ
အောက်ဂရပ်ဆိုသည်မှာ ထိပ်ဖျားများနှင့် အနားများ၏ အစုအဝေးတစ်ခုမှ ဖွဲ့စည်းထားသော ဂရပ်၏ အစုအဝေးတစ်ခုဖြစ်သည်။ ချိတ်ဆက်ထားသော အစိတ်အပိုင်းဆိုသည်မှာ ချိတ်ဆက်ထားဆဲ အမြင့်ဆုံး အောက်ဂရပ်ဖြစ်သည်။ လူမှုကွန်ရက် ခွဲခြမ်းစိတ်ဖြာမှုတွင် အစိတ်အပိုင်းများသည် ချိတ်ဆက်ထားသော်လည်း တစ်ခုနှင့်တစ်ခု ကွဲပြားနေသော အုပ်စုများကို ကိုယ်စားပြုနိုင်သည်။

ဂန္ထဝင်သီအိုရမ်များနှင့်ပြဿနာများ

ဂရပ်ဖ်သီအိုရီသည် ၁၈ ရာစုတွင် Leonhard Euler ဖြေရှင်းခဲ့သော ကျော်ကြားသော Königsberg Bridges ပြဿနာမှ စတင်၍ ရှည်လျားသောသမိုင်းကြောင်းရှိသည်။ Euler သည် တံတားခုနစ်စင်းလုံးကို တစ်ကြိမ်တည်းဖြတ်ကူးပြီး စတင်ရာနေရာသို့ ပြန်ရောက်ရန် မဖြစ်နိုင်ကြောင်း သက်သေပြခဲ့ပြီး ခေတ်သစ်ဂရပ်ဖ်သီအိုရီ၏ အုတ်မြစ်ကို ထူထောင်ခဲ့သည်။

ဂရပ်သီအိုရီတွင် ဂန္ထဝင်ခေါင်းစဉ်အချို့မှာ-

၁။ အွိုင်လာနှင့် ဟယ်မီလ်တန် လမ်းကြောင်းများ
– Eulerian လမ်းကြောင်းတစ်ခုသည် အစွန်းတစ်ခုစီကို တစ်ကြိမ်သာ ဖြတ်သန်းသွားသည်။ ညွှန်ပြမထားသော ဂရပ်တွင် Eulerian လမ်းကြောင်းတစ်ခု ရှိနေခြင်းအတွက် အခြေအနေသည် မဒီဂရီရှိသော ထိပ်ဖျားများ အရေအတွက်နှင့် ဆက်စပ်နေသည်။
– Hamiltonian လမ်းကြောင်းသည် vertex တစ်ခုစီသို့ တစ်ကြိမ်သာ ရောက်ရှိသည်။ Euler ၏ပြဿနာနှင့်မတူဘဲ Hamilton ၏ပြဿနာသည် ပိုမိုခက်ခဲပြီး ၎င်း၏ variants အများစုသည် တွက်ချက်မှုအရ NP-hard ဖြစ်သည်။

၂။ ဂရပ်အရောင်ခြယ်ခြင်း
ဂရပ်အရောင်ခြယ်ခြင်းဆိုသည်မှာ ထိပ်စွန်းများ (သို့မဟုတ် အနားများ) ကို အရောင်များ သတ်မှတ်ပေးခြင်းဖြင့် အနီးနားရှိ ထိပ်စွန်းများတွင် အရောင်တူညီမှု မရှိစေပါ။ လူသိများသော အသုံးချမှုတစ်ခုမှာ မြေပုံအရောင်ခြယ်ခြင်းပြဿနာဖြစ်ပြီး ၎င်းသည် မျက်နှာပြင်မြေပုံတိုင်းကို အများဆုံး အရောင်လေးမျိုးဖြင့် အရောင်ခြယ်နိုင်သည် (အရောင်လေးမျိုးသီအိုရမ်) ဟူသော သီအိုရမ်ကို ဦးတည်စေသည်။

၃။ ပြားချပ်ဂရပ်
ပြားချပ်ချပ်မျက်နှာပြင်ပေါ်တွင် အနားများမဖြတ်ဘဲ ရေးဆွဲနိုင်ပါသည်။ ပြားချပ်ချပ်ဇယားများကို အီလက်ထရွန်းနစ်ဆားကစ်ဒီဇိုင်းနှင့် ကွန်ရက်အပြင်အဆင်တွင် ကျယ်ကျယ်ပြန့်ပြန့်အသုံးပြုကြသည်။

ဂရပ်ဖ်သီအိုရီတွင် အရေးကြီးသော အယ်လဂိုရီသမ်များ

ကွန်ပျူတာသိပ္ပံတွင် ဂရပ်သီအိုရီသည် အရေးကြီးသော အယ်လဂိုရီသမ်များစွာ၏ အခြေခံဖြစ်သည်။

– ဂရပ်ဖြတ်သန်းခြင်း၊ အစိတ်အပိုင်းရှာဖွေခြင်း၊ စက်ဝန်းရှာဖွေခြင်းနှင့် topology အတွက် BFS (Breadth-First Search) နှင့် DFS (Depth-First Search)။
– အနုတ်လက္ခဏာမပါသော အလေးချိန်များပါသည့် အလေးချိန်ပါ ဂရပ်တွင် အတိုဆုံးလမ်းကြောင်းကို ရှာဖွေရန် Dijkstra။
– အနုတ်လက္ခဏာအလေးချိန်များကို ကိုင်တွယ်နိုင်သည့် အတိုဆုံးလမ်းကြောင်းအတွက် Bellman–Ford။
– Kruskal နှင့် Prim တို့သည် အနည်းဆုံးကုန်ကျစရိတ်ဖြင့် network ဒီဇိုင်းအတွက် အသုံးဝင်သော minimum spanning tree ကို ရှာဖွေရန်။

ဤအယ်လဂိုရစ်သမ်များသည် ဂရပ်များ၏ သင်္ချာသဘောတရားများသည် လက်တွေ့ပြဿနာများကို ဖြေရှင်းရာတွင် မည်သို့တိုက်ရိုက်အခန်းကဏ္ဍမှ ပါဝင်သည်ကို သရုပ်ပြပါသည်။

ဂရပ်သီအိုရီကို လက်တွေ့ဘဝတွင် အသုံးချမှုများ

ဂရပ်သီအိုရီသည် အမျိုးမျိုးသော အခြေအနေများတွင် “ဆက်ဆံရေးများ” ကို ပုံစံပြုနိုင်သောကြောင့် အစွမ်းထက်ပါသည်။

၁။ သယ်ယူပို့ဆောင်ရေးနှင့် ရေကြောင်းသွားလာရေး
နုတ်များသည် လမ်းဆုံများကို ကိုယ်စားပြုပြီး အနားသတ်များသည် လမ်းများကို ကိုယ်စားပြုကာ အလေးချိန်များသည် အကွာအဝေး သို့မဟုတ် ခရီးသွားချိန်ကို ကိုယ်စားပြုသည်။ လမ်းကြောင်းပြစနစ်များသည် အကောင်းဆုံးလမ်းကြောင်းကို ဆုံးဖြတ်ရန် ဂရပ်အယ်လဂိုရစ်သမ်များကို အသုံးပြုသည်။

၂။ ကွန်ပျူတာကွန်ရက်များနှင့် အင်တာနက်
ရောက်တာများနှင့် ဆာဗာများသည် နုတ်များအဖြစ် ဆောင်ရွက်ပြီး ကေဘယ်လ်များ သို့မဟုတ် ချိတ်ဆက်မှုများသည် အနားသတ်များအဖြစ် ဆောင်ရွက်သည်။ ဂရပ်ခွဲခြမ်းစိတ်ဖြာမှုကို ဒေတာအသွားအလာကို အကောင်းဆုံးဖြစ်အောင်ပြုလုပ်ရန်နှင့် ကွန်ရက်ခံနိုင်ရည်ကို မြှင့်တင်ရန်အတွက် အသုံးပြုသည်။

၃။ လူမှုကွန်ရက်များ
အသုံးပြုသူများသည် node များအဖြစ်၊ ဆက်ဆံရေးများသည် အနားသတ်များအဖြစ်။ ဂရပ်သီအိုရီကို အသိုက်အဝန်းများကို ထောက်လှမ်းရန်၊ လွှမ်းမိုးမှု (ဗဟိုချက်) ကို တိုင်းတာရန်နှင့် သတင်းအချက်အလက် ဖြန့်ဝေမှုကို ခွဲခြမ်းစိတ်ဖြာရန် အသုံးပြုသည်။

၄။ ဇီဝဗေဒနှင့် ဓာတုဗေဒ
ဂရပ်များကို မျိုးဗီဇကွန်ရက်များ၊ ပရိုတင်း အပြန်အလှန် ဆက်သွယ်မှု သို့မဟုတ် မော်လီကျူးဖွဲ့စည်းပုံများကို ပုံစံထုတ်ရန် အသုံးပြုသည်။ ဇီဝသတင်းအချက်အလက်ဆိုင်ရာ သုတေသနအများစုသည် ကြီးမားသော ဂရပ်ခွဲခြမ်းစိတ်ဖြာမှုအပေါ် မှီခိုအားထားရသည်။

၅။ စီမံကိန်းနှင့် စက်မှုလုပ်ငန်းစီမံခန့်ခွဲမှု
ထိရောက်သော အလုပ်အစီအစဉ်များနှင့် အရေးကြီးသော လမ်းကြောင်းများကို ရှာဖွေရန်အတွက် လုပ်ငန်းတာဝန်အချိန်ဇယားဆွဲခြင်း (ဥပမာ PERT/CPM) တွင် ဦးတည်ထားသော ဂရပ်များကို အသုံးပြုသည်။

ပိတ်

သင်္ချာဘာသာရပ်တွင် ဂရပ်သီအိုရီသည် နုတ်များနှင့် အစွန်းများမှတစ်ဆင့် ဆက်နွယ်မှုများ၏ဖွဲ့စည်းပုံကို လေ့လာခြင်းဖြစ်သည်။ ၎င်း၏ ကွဲပြားသော ဂရပ်အမျိုးအစားများ၊ ဒီဂရီ၊ လမ်းကြောင်းနှင့် စက်ဝန်းကဲ့သို့သော သဘောတရားများနှင့် ရှာဖွေမှုနှင့် အကောင်းဆုံးဖြစ်အောင်ပြုလုပ်ခြင်း အယ်လဂိုရီသမ်များဖြင့် ဂရပ်သီအိုရီသည် အလွန်ပြောင်းလွယ်ပြင်လွယ်ရှိပြီး အစွမ်းထက်သောကိရိယာတစ်ခုဖြစ်သည်။ ၎င်း၏အားသာချက်မှာ ဖွဲ့စည်းတည်ဆောက်ပုံရှိပြီး ခွဲခြမ်းစိတ်ဖြာနိုင်သော မော်ဒယ်များတွင် ရှုပ်ထွေးသောပြဿနာများကို ကိုယ်စားပြုနိုင်စွမ်းတွင် တည်ရှိသည်။ ဂရပ်သီအိုရီသည် သီးခြားသင်္ချာ၊ ကွန်ပျူတာသိပ္ပံနှင့် နေ့စဉ်ဘဝကို သက်ရောက်မှုရှိသော ခေတ်မီအသုံးချမှုများစွာ ဖွံ့ဖြိုးတိုးတက်မှုအတွက် အရေးကြီးသော အခြေခံအုတ်မြစ်ဖြစ်လာခြင်းမှာ အံ့သြစရာမဟုတ်ပါ။

သင်အလိုရှိပါက၊ ဤဆောင်းပါးကို ပိုမိုသက်ဆိုင်မှုရှိစေရန်အတွက် ဆွေးနွေးမှုများ (ဥပမာ Euler ၏လမ်းကြောင်း၊ Dijkstra ၏ သို့မဟုတ် ဂရပ်အရောင်ခြယ်ခြင်းအကြောင်း) နှင့်အတူ ဥပမာပြဿနာများကိုလည်း ထည့်သွင်းနိုင်ပါသည်။