Graph Theory ကို ဘယ်နေရာတွေမှာ အသုံးချနိုင်သလဲ?

Graph တစ်ခုမှာ Vertex တွေနဲ့ Edge တွေ ပါပါတယ်။

ဒါပေမယ့် အစက်တွေနဲ့ မျဉ်းတွေ ဆွဲထားတာကနေ ဘာအသုံးဝင်လာသလဲ?

အဓိကက လက်တွေ့ပြဿနာတစ်ခုကို Graph အဖြစ် ကိုယ်စားပြုလိုက်တဲ့အခါ ချိတ်ဆက်မှု၊ လမ်းကြောင်း၊ အတွဲချိတ်ဆက်ခြင်းနဲ့ ကန့်သတ်ချက်တွေကို စနစ်တကျ လေ့လာနိုင်လာတာ ပါ။

ရိုးရှင်းတဲ့ ဥပမာတွေကနေ ပိုရှုပ်ထွေးတဲ့ ပြဿနာတွေအထိ ကြည့်ရအောင်။

၁။ မိတ်ဆွေကွန်ရက် — Connectivity

လူတစ်ယောက်စီကို Vertex၊ မိတ်ဆွေဖြစ်တဲ့ လူနှစ်ယောက်ကြားကို Edge လို့ သတ်မှတ်ကြည့်ပါ။

ဒါဆို—

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

ဆိုတာတွေ လေ့လာနိုင်ပါတယ်။

ဒီနေရာမှာ မိတ်ဆွေဖြစ်မှုကို နှစ်ဖက်တူညီတယ်လို့ သတ်မှတ်ရင် Undirected Graph သုံးနိုင်ပါတယ်။ Follow လုပ်ထားမှုလို တစ်ဖက်သတ်ဆက်နွယ်မှုဆိုရင် Directed Graph နဲ့ ကိုယ်စားပြုရပါတယ်။

အသုံးချတဲ့သဘောတရား — Connectivity၊ Connected Components၊ Distance။

၂။ ဝင်္ကပါကနေ ထွက်ခြင်း — Path Finding

ဝင်္ကပါတစ်ခုမှာ လမ်းဆုံနဲ့ ဝင်ပေါက်၊ ထွက်ပေါက်တွေကို Vertex အဖြစ် ယူပါ။ အဲဒီနေရာတွေကြားက လမ်းတွေကို Edge အဖြစ် ယူပါ။

“ဝင်ပေါက်ကနေ ထွက်ပေါက်ကို ရောက်နိုင်သလား” ဆိုတာ Path ရှိမရှိ ရှာတဲ့ပြဿနာပါ။

လမ်းတစ်ခုချင်းစီကို ကုန်ကျစရိတ်တူတယ်လို့ ယူဆရင် Breadth-First Search — BFS နဲ့ Edge အရေအတွက် အနည်းဆုံးလမ်းကို ရှာနိုင်ပါတယ်။

ဒါပေမယ့် လမ်းအပိုင်းတချို့က ရှည်ပြီး တချို့က တိုနေရင် Edge အနည်းဆုံးလမ်းက အကွာအဝေးအနည်းဆုံးလမ်း ဖြစ်ချင်မှ ဖြစ်ပါမယ်။

အသုံးချတဲ့သဘောတရား — Reachability၊ Graph Traversal၊ Shortest Path။

၃။ မြို့တစ်မြို့ကနေ တစ်မြို့သွားခြင်း — Weighted Shortest Path

မြို့တွေကို Vertex၊ လမ်းတွေကို Edge အဖြစ် ယူပြီး လမ်းတစ်ခုချင်းစီမှာ ကြာချိန် သတ်မှတ်ပါ။

A ကနေ D ကို သွားဖို့—

Route	စုစုပေါင်းကြာချိန်
A → B → D	၂၅ မိနစ်
A → C → D	၁၈ မိနစ်
A → D တိုက်ရိုက်	၃၀ မိနစ်

ဆိုရင် အချိန်အနည်းဆုံး Route က A → C → D ပါ။

Weight တွေ အနုတ်မဖြစ်တဲ့အခြေအနေမှာ Dijkstra’s Algorithm ကို အသုံးပြုနိုင်ပါတယ်။

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

အသုံးချတဲ့သဘောတရား — Weighted Graph၊ Shortest Path။

၄။ စာမေးပွဲအချိန်ဇယား — Graph Coloring

ဘာသာရပ်တစ်ခုစီကို Vertex အဖြစ် ယူပါ။

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

ပြီးရင် Vertex တွေကို Color ခြယ်ပါ။ Edge နဲ့ ဆက်ထားတဲ့ Vertex နှစ်ခုက Color မတူရပါဘူး။

ဒီမှာ Color တစ်ခုက Exam time slot တစ်ခုကို ကိုယ်စားပြုပါတယ်။

A၊ B၊ C ဘာသာရပ်သုံးခုလုံးက တစ်ခုနဲ့တစ်ခု Conflict ရှိနေရင် Triangle ဖြစ်ပါတယ်။ အနည်းဆုံး Color သုံးခု၊ တစ်နည်းအားဖြင့် Time slot သုံးခု လိုပါတယ်။

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

အသုံးချတဲ့သဘောတရား — Graph Coloring၊ Chromatic Number။

၅။ လူနဲ့အလုပ် အတွဲချိတ်ခြင်း — Bipartite Matching

လူတွေကို တစ်ဖက်၊ အလုပ်တွေကို တစ်ဖက် ခွဲထားပါ။

လူတစ်ယောက်က အလုပ်တစ်ခုကို လုပ်နိုင်ရင် အဲဒီနှစ်ခုကြား Edge ဆက်ပါ။

ဥပမာ—

• မောင် A က အလုပ် ၁ နဲ့ အလုပ် ၂ နှစ်ခုလုံး လုပ်နိုင်တယ်။
• မောင် B က အလုပ် ၁ ပဲ လုပ်နိုင်တယ်။

မောင် A ကို အလုပ် ၁ အရင်ပေးလိုက်ရင် မောင် B အတွက် အလုပ်မကျန်တော့ပါဘူး။

မောင် A ကို အလုပ် ၂၊ မောင် B ကို အလုပ် ၁ ပေးလိုက်ရင် နှစ်ယောက်လုံး အလုပ်ရပါတယ်။

ဒီဥပမာမှာ လူတစ်ယောက်ကို အလုပ်တစ်ခု၊ အလုပ်တစ်ခုကို လူတစ်ယောက်သာ ပေးမယ်လို့ သတ်မှတ်ထားပါတယ်။ ဒီလို Vertex မထပ်တဲ့ Edge တွေကို ရွေးယူထားတဲ့အစုကို Matching လို့ ခေါ်ပါတယ်။

အတွဲအရေအတွက် အများဆုံးရအောင် ရှာတာက Maximum Matching ပါ။ အရည်အချင်းအမှတ် ဒါမှမဟုတ် ကုန်ကျစရိတ်တွေပါ ထည့်တွက်ရင် Weighted Matching ပုံစံတွေကို ဆက်စဉ်းစားနိုင်ပါတယ်။

အသုံးချတဲ့သဘောတရား — Bipartite Graph၊ Matching။

၆။ နေရာအားလုံးကို ကုန်ကျစရိတ်အနည်းဆုံးနဲ့ ချိတ်ခြင်း — Minimum Spanning Tree

ရွာလေးရွာကို ဆက်သွယ်ဖို့ Cable ဆွဲချင်တယ်ဆိုပါစို့။

ရွာတစ်ရွာစီက Vertex၊ ဆွဲလို့ရတဲ့ Cable လမ်းကြောင်းက Edge၊ ကုန်ကျစရိတ်က Weight ပါ။

ဒီမှာ မေးခွန်းက—

ရွာအားလုံး ဆက်သွယ်နိုင်အောင် Cable စုစုပေါင်းကုန်ကျစရိတ် အနည်းဆုံးနဲ့ ဘယ်လိုဆွဲမလဲ?

ဖြစ်ပါတယ်။

ဒီလို ပြဿနာအတွက် Minimum Spanning Tree — MST ကို စဉ်းစားနိုင်ပါတယ်။ Connected Undirected Graph မှာ Vertex အားလုံးပါဝင်ပြီး Cycle မရှိတဲ့ ချိတ်ဆက်မှုတွေထဲက Weight စုစုပေါင်း အနည်းဆုံးကို ရွေးတာပါ။

MST က နေရာအားလုံးကို ချိတ်ပေးပါတယ်။ ဒါပေမယ့် နေရာနှစ်ခုကြား Shortest Path ကို အမြဲပေးတာ မဟုတ်ပါဘူး။

နောက်တစ်ချက်က Tree မှာ အစားထိုးလမ်းကြောင်း မရှိပါဘူး။ Cable တစ်ကြောင်း ပြတ်ရင် ကွန်ရက်က ကွဲသွားနိုင်ပါတယ်။ ပြတ်တောက်မှုခံနိုင်ရည် လိုအပ်ရင် MST ထက်ပိုတဲ့ ချိတ်ဆက်မှုတွေ လိုလာနိုင်ပါတယ်။

အသုံးချတဲ့သဘောတရား — Spanning Tree၊ Minimum Spanning Tree။

၇။ ပိုက်ကွန်ရက်ထဲ ရေဘယ်လောက် ဖြတ်စီးနိုင်သလဲ — Maximum Flow

ရေပိုက်ကွန်ရက်တစ်ခုမှာ ပိုက်ဆုံတွေကို Vertex၊ ပိုက်တွေကို Edge အဖြစ် ယူပါ။

ပိုက်တစ်ခုချင်းစီမှာ တစ်မိနစ်အတွင်း ဖြတ်စီးနိုင်တဲ့ ပမာဏ — Capacity — ရှိမယ်။

ရေစတင်ထွက်တဲ့နေရာကို Source၊ ရေရောက်စေချင်တဲ့နေရာကို Sink လို့ ခေါ်ပါတယ်။

ဒီမှာ မေးခွန်းက—

ပိုက်တစ်ချောင်းချင်းစီရဲ့ Capacity ကို မကျော်ဘဲ Source ကနေ Sink ကို ရေစုစုပေါင်း အများဆုံး ဘယ်လောက်ပို့နိုင်မလဲ?

ဖြစ်ပါတယ်။

ရေဝင်ပိုက်ကြီးတယ်ဆိုတာနဲ့ နောက်ဆုံးရောက်တဲ့ရေပမာဏ များမယ်လို့ မဆိုနိုင်ပါဘူး။ အလယ်ပိုင်းမှာ Capacity နည်းတဲ့ပိုက်တွေက Bottleneck ဖြစ်နေနိုင်ပါတယ်။

Maximum Flow–Minimum Cut Theorem က ဒီကွန်ရက်မှာ ရနိုင်တဲ့ Maximum Flow နဲ့ Source၊ Sink ကို ခွဲပစ်နိုင်တဲ့ Cut တွေထဲက Capacity အနည်းဆုံးတန်ဖိုး တူကြောင်း ဖော်ပြပါတယ်။

ရေပိုက်နမူနာက Capacity ကို ရှင်းပြဖို့ ရိုးရှင်းအောင် ယူထားတဲ့ Model ပါ။ တကယ့်ရေပိုက်ဒီဇိုင်းမှာ ရေဖိအားနဲ့ ပိုက်ပွတ်တိုက်မှုလို ရူပဗေဒအချက်တွေလည်း ထည့်တွက်ရပါတယ်။

အသုံးချတဲ့သဘောတရား — Flow Network၊ Capacity၊ Maximum Flow၊ Minimum Cut။

၈။ မြို့အများကြီးကို လှည့်ပြီး မူလနေရာ ပြန်လာခြင်း — Traveling Salesman Problem

မြို့တစ်မြို့ကနေ တစ်မြို့ကို အတိုဆုံးသွားချင်တာက Shortest Path ပြဿနာပါ။

ဒါပေမယ့်—

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

ဆိုရင် Traveling Salesman Problem — TSP ဖြစ်သွားပါတယ်။

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

မြို့အရေအတွက် တိုးလာတာနဲ့ ဖြစ်နိုင်တဲ့အစီအစဉ် အရေအတွက်က အလွန်မြန်မြန် တိုးလာပါတယ်။

TSP ရဲ့ အထွေထွေ Optimization ပြဿနာဟာ NP-hard ဖြစ်ပါတယ်။ ဒါက အဖြေရှာလို့ မရဘူးဆိုတဲ့ အဓိပ္ပာယ် မဟုတ်ပါဘူး။ ပြဿနာအရွယ်အစားနဲ့ သတ်မှတ်ချက်အပေါ် မူတည်ပြီး Exact Methods၊ Approximation Algorithms နဲ့ Heuristics တွေကို ရွေးသုံးကြပါတယ်။

ကားအများကြီး၊ တင်နိုင်တဲ့ပမာဏနဲ့ ပို့ရမယ့်အချိန်တွေပါ ထည့်လိုက်ရင်တော့ Vehicle Routing Problem — VRP လို ပိုကျယ်တဲ့ပြဿနာတွေဆီ ရောက်လာပါတယ်။

အသုံးချတဲ့သဘောတရား — Hamiltonian Cycle၊ TSP၊ Combinatorial Optimization။

မေးခွန်းမတူရင် Graph ပြဿနာလည်း မတူပါဘူး

သိချင်တဲ့အရာ	သက်ဆိုင်ရာပြဿနာ
ရောက်နိုင်သလား	Reachability
ဘယ်လမ်းက အတိုဆုံးလဲ	Shortest Path
မတိုက်မိအောင် ဘယ်လိုခွဲမလဲ	Graph Coloring
အတွဲအများဆုံး ဘယ်လိုချိတ်မလဲ	Maximum Matching
အားလုံးကို ကုန်ကျစရိတ်အနည်းဆုံးနဲ့ ဘယ်လိုချိတ်မလဲ	Minimum Spanning Tree
ကွန်ရက်တစ်ခုက အများဆုံး ဘယ်လောက်သယ်နိုင်သလဲ	Maximum Flow
နေရာအားလုံးကို လှည့်ပြီး အနည်းဆုံးခရီးနဲ့ ဘယ်လိုပြန်လာမလဲ	Traveling Salesman Problem

Graph တစ်ခုတည်းကို ကြည့်နေရင်တောင် မေးတဲ့မေးခွန်း မတူတာနဲ့ ဖြေရှင်းနည်း မတူနိုင်ပါဘူး။

Graph Theory ကို အသုံးချဖို့ ပထမဆုံးလုပ်ရတာက Algorithm ရွေးခြင်းမဟုတ်ဘဲ Vertex က ဘာလဲ၊ Edge က ဘာလဲ၊ ဘာကို အကောင်းဆုံးဖြစ်စေချင်တာလဲဆိုတာ တိတိကျကျ သတ်မှတ်ခြင်းပါ။

ဆက်ဖတ်ရန် — Graph Theory အခြေခံ။

ကိုးကားချက်များ — MIT: Graph Coloring၊ Princeton: Graph Algorithms၊ Princeton: Maximum Flow။