Graph Theory — အစက်များနှင့် ဆက်သွယ်မှုများကို လေ့လာခြင်း

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

ဒီနေရာက Graph ဟာ အရောင်းအတက်အကျကို ပြတဲ့ Line Chart၊ Bar Chart မျိုး မဟုတ်ပါဘူး။

Graph တစ်ခုမှာ အခြေခံအစိတ်အပိုင်း နှစ်မျိုးရှိပါတယ်။

• Vertex — အစက်တစ်ခု။ အများကိန်းကို Vertices လို့ ခေါ်ပြီး Node လို့လည်း သုံးပါတယ်။
• Edge — Vertex နှစ်ခုကို ဆက်ထားတဲ့ ဆက်သွယ်မှု။

သင်္ချာသင်္ကေတနဲ့—

G = (V, E)

လို့ ရေးပါတယ်။ V က Vertex များရဲ့ အစု၊ E က Edge များရဲ့ အစု ဖြစ်ပါတယ်။

Graph တစ်ခုကို ဥပမာနဲ့ ကြည့်ရအောင်

A၊ B၊ C၊ D ဆိုတဲ့ Vertex လေးခု ရှိမယ်။

ဆက်ထားတဲ့ Edge တွေက—

A–B၊ A–C၊ B–C၊ C–D

ဖြစ်မယ်ဆိုပါစို့။

ဒီ Graph မှာ Vertex ၄ ခု၊ Edge ၄ ခု ရှိပါတယ်။

A နဲ့ B က တိုက်ရိုက်ချိတ်ထားတယ်။ A နဲ့ D က တိုက်ရိုက်မချိတ်ထားပေမယ့် A → C → D ဆိုပြီး ဆက်သွားနိုင်ပါတယ်။

ဒီဥပမာကို အခြေခံပြီး Graph ရဲ့ သဘောတရားတွေကို ဆက်ကြည့်ပါမယ်။

၁။ Adjacent — တိုက်ရိုက်ချိတ်ဆက်နေခြင်း

Vertex နှစ်ခုကြားမှာ Edge တစ်ခုရှိရင် အဲဒီ Vertex နှစ်ခုကို Adjacent Vertices လို့ ခေါ်ပါတယ်။

ဥပမာမှာ—

• A နဲ့ B က Adjacent ဖြစ်တယ်။
• C နဲ့ D က Adjacent ဖြစ်တယ်။
• A နဲ့ D က Adjacent မဖြစ်ဘူး။

အခြား Vertex ကို ဖြတ်သွားပြီး ရောက်နိုင်တာနဲ့ တိုက်ရိုက်ချိတ်ဆက်နေတာကို ခွဲသိဖို့ လိုပါတယ်။

၂။ Degree — Vertex တစ်ခုမှာ ချိတ်ထားတဲ့ Edge အရေအတွက်

Vertex တစ်ခုနဲ့ ဆက်နေတဲ့ Edge အရေအတွက်ကို အဲဒီ Vertex ရဲ့ Degree လို့ ခေါ်ပါတယ်။

နမူနာ Graph မှာ—

Vertex	ချိတ်ဆက်ထားတဲ့ Vertex များ	Degree
A	B၊ C	၂
B	A၊ C	၂
C	A၊ B၊ D	၃
D	C	၁

Degree အားလုံးကို ပေါင်းရင်—

၂ + ၂ + ၃ + ၁ = ၈

ရပါတယ်။ Edge အရေအတွက် ၄ ရဲ့ နှစ်ဆပါ။

Undirected Graph မှာ Edge တစ်ခုချင်းစီက အစွန်းနှစ်ဖက်ရဲ့ Degree ကို ထည့်တွက်ပေးတာကြောင့်—

Degree အားလုံးပေါင်းလဒ် = Edge အရေအတွက် × ၂

ဖြစ်ပါတယ်။ ဒီဆက်နွယ်မှုကို Handshaking Lemma လို့ ခေါ်ပါတယ်။

၃။ Directed နဲ့ Undirected Graph

Undirected Graph မှာ Edge ရဲ့ ဦးတည်ချက် မရှိပါဘူး။ A–B ဆိုတာ A နဲ့ B ချိတ်ထားတယ်လို့ပဲ ဆိုလိုပါတယ်။

Directed Graph မှာတော့ Edge ရဲ့ ဦးတည်ချက် ရှိပါတယ်။

A → B ဆိုတာ A ကနေ B ကို ဦးတည်နေခြင်းပါ။ B → A ရှိတယ်လို့ အလိုအလျောက် မဆိုလိုပါဘူး။

Directed Graph မှာ Degree ကို ထပ်ခွဲနိုင်ပါတယ်။

• In-degree — Vertex ထဲကို ဝင်လာတဲ့ Edge အရေအတွက်။
• Out-degree — Vertex ကနေ ထွက်သွားတဲ့ Edge အရေအတွက်။

A → B နဲ့ C → B ရှိရင် B ရဲ့ In-degree က ၂ ဖြစ်ပါတယ်။ B ကနေ ထွက်တဲ့ Edge မရှိရင် Out-degree က သုညပါ။

၄။ Walk၊ Trail နဲ့ Path

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

ဒီစာမှာ အောက်ပါသတ်မှတ်ချက်တွေကို သုံးပါမယ်။

အမျိုးအစား	သတ်မှတ်ချက်
Walk	Vertex နဲ့ Edge နှစ်မျိုးစလုံးကို ထပ်ဖြတ်နိုင်တယ်
Trail	Edge တစ်ခုကို ထပ်မဖြတ်ရဘူး။ Vertex ကိုတော့ ထပ်ဖြတ်နိုင်တယ်
Path	Vertex တစ်ခုကို ထပ်မဖြတ်ရဘူး

ဥပမာ—

A → B → A → C

က Walk ဖြစ်ပါတယ်။ A ကို ထပ်ဖြတ်ထားပြီး A–B Edge ကိုလည်း အသွားအပြန် ထပ်သုံးထားပါတယ်။

A → B → C → A

က Trail ဖြစ်ပါတယ်။ Edge မထပ်ပေမယ့် A ကို ပြန်ရောက်လာပါတယ်။

A → C → D

က Path ဖြစ်ပါတယ်။ Vertex မထပ်ပါဘူး။

Path ရဲ့ Length ဆိုတာ ဖြတ်သွားတဲ့ Edge အရေအတွက်ပါ။ A → C → D ရဲ့ Length က ၂ ဖြစ်ပါတယ်။

၅။ Cycle — မူလနေရာကို ပြန်ရောက်လာတဲ့ ပတ်လမ်း

စတင်တဲ့ Vertex ကို ပြန်ရောက်လာပြီး အစနဲ့အဆုံး Vertex မှလွဲလို့ အခြား Vertex တွေ မထပ်တဲ့ ပတ်လမ်းကို Cycle လို့ ခေါ်ပါတယ်။

နမူနာမှာ—

A → B → C → A

က Cycle ဖြစ်ပါတယ်။

A → B → A ကတော့ ဒီနမူနာလို Simple Undirected Graph မှာ Cycle မဟုတ်ပါဘူး။ Edge တစ်ခုတည်းကို အသွားအပြန် ထပ်သုံးထားလို့ပါ။

၆။ Connected Graph — Vertex အားလုံးကြား ရောက်နိုင်ခြင်း

Undirected Graph တစ်ခုမှာ ဘယ် Vertex နှစ်ခုကို ရွေးရွေး အဲဒီနှစ်ခုကြား Path ရှိရင် Connected Graph လို့ ခေါ်ပါတယ်။

နမူနာ Graph က Connected ဖြစ်ပါတယ်။ D ကိုရောက်ဖို့ C ကို ဖြတ်ရပေမယ့် အခြား Vertex အားလုံးနဲ့ ဆက်သွယ်ရောက်ရှိနိုင်ပါတယ်။

အခု E ဆိုတဲ့ Vertex တစ်ခု ထပ်ထည့်ပြီး ဘယ် Vertex နဲ့မှ မဆက်ထားဘူးဆိုပါစို့။

အဲဒီ Graph က Disconnected ဖြစ်သွားပါတယ်။ E ကို Isolated Vertex လို့ ခေါ်ပြီး Degree က သုည ဖြစ်ပါတယ်။

Disconnected Graph ထဲက အချင်းချင်းဆက်သွယ်ရောက်ရှိနိုင်တဲ့ အစုတစ်ခုချင်းစီကို Connected Component လို့ ခေါ်ပါတယ်။

ဒီဥပမာမှာ Component နှစ်ခု ရှိပါတယ်။

• A၊ B၊ C၊ D ပါဝင်တဲ့ အစု။
• E တစ်ခုတည်း ပါဝင်တဲ့ အစု။

၇။ Weighted Graph — Edge တွေမှာ တန်ဖိုးပါခြင်း

Edge တွေမှာ အကွာအဝေး၊ ကြာချိန်၊ ကုန်ကျစရိတ်လို တန်ဖိုးတွေ သတ်မှတ်ထားရင် Weighted Graph လို့ ခေါ်ပါတယ်။

ဥပမာ—

Edge	Weight
A–B	၄
B–D	၃
A–C	၂
C–D	၈

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

• A → B → D ရဲ့ စုစုပေါင်း Weight က ၇။
• A → C → D ရဲ့ စုစုပေါင်း Weight က ၁၀။

နှစ်လမ်းစလုံး Edge နှစ်ခုစီ ဖြတ်ရပေမယ့် Weight စုစုပေါင်း မတူပါဘူး။

Unweighted Graph ရဲ့ Shortest Path က Edge အရေအတွက် အနည်းဆုံးလမ်းကို ဆိုလိုပါတယ်။

Weighted Graph ရဲ့ Shortest Path ကတော့ သတ်မှတ်ထားတဲ့ Weight စုစုပေါင်း အနည်းဆုံးလမ်းကို ဆိုလိုပါတယ်။

၈။ Tree — Cycle မရှိတဲ့ Connected Graph

Tree ဆိုတာ Cycle မရှိတဲ့ Connected Undirected Graph ဖြစ်ပါတယ်။

မူလနမူနာက A–B၊ A–C၊ B–C၊ C–D ဆိုတဲ့ Edge လေးခုထဲက A–B ကို ဖယ်ကြည့်ပါ။

A–C၊ B–C၊ C–D ပဲ ကျန်ပါမယ်။

Vertex အားလုံး ဆက်သွယ်ရောက်ရှိနိုင်သေးတယ်။ Cycle လည်း မရှိတော့ဘူး။ ဒါကြောင့် Tree ဖြစ်ပါတယ်။

Vertex အရေအတွက် n ရှိတဲ့ Tree မှာ—

Edge အရေအတွက် = n − ၁

ဖြစ်ပါတယ်။

ဒါ့အပြင် Tree ထဲက Vertex နှစ်ခုကြားမှာ Path တစ်လမ်းတည်းသာ ရှိပါတယ်။

Graph ပုံဆွဲတဲ့နေရာမှာ သတိထားရမယ့်အချက်

Graph ရဲ့ အဓိကက အစက်တွေ ဘယ်နေရာမှာရှိသလဲဆိုတာထက် ဘယ်အစက်နဲ့ ဘယ်အစက် ဆက်ထားသလဲ ဆိုတာပါ။

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

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

Graph Theory ကို စလေ့လာတဲ့အခါ Vertex၊ Edge၊ Degree၊ Path၊ Cycle နဲ့ Connectivity တို့ကို နားလည်ထားရင် ပိုရှုပ်ထွေးတဲ့ Graph တွေကို ဆက်လေ့လာဖို့ အခြေခံရပါပြီ။