Königsberg မြို့၏ တံတားခုနစ်စင်းပြဿနာ

Königsberg မြို့၏ တံတားခုနစ်စင်းပြဿနာသည် သင်္ချာ၏သမိုင်းကြောင်းတွင် ထင်ရှားသည့် ပြဿနာပုစ္ဆာတစ်ခုပင် ဖြစ်သည်။ ပုစ္ဆာတွင် အဖြေမရှိကြောင်းကို လီယွန်ဟတ် အွိုင်လာ က ၁၇၃၆ ခုနှစ် တွင် သက်သေပြနိုင်ခဲ့သည်။ ယင်းဖြေရှင်းချက်မှ ဂရပ်သီအိုရီ နှင့် တိုပေါ်လော်ဂျီ တို့အတွက် အခြေခံ idea များဖြစ်ပေါ်လာခဲ့သည်။

Euler ၏ခေတ်အခါက Königsberg မြို့၏ မြေပုံ။ ပုံတွင် Pregel မြစ်နှင့် တံတားခုနစ်စင်းတို့ကို highlight ပြထားသည်။

Prussia ရှိ Königsberg မြို့သည် (ယခု ကာလင်နင်ဂရတ်မြို့၊ ရုရှားနိုင်ငံ ) မြစ်လယ်ကျွန်းများဖြစ်သော Kneiphof နှင့် Lomse ကျွန်းများအပါအဝင် Pregel မြစ် ကိုခွလျက်တည်ရှိသည်။ မြို့၏ကုန်းမြေများ (ကျွန်းများဟုသုံးမည်) ကို တံတားခုနစ်စင်းဖြင့်ဆက်သွယ်ထားသည်။ ပြဿနာပုစ္ဆာမှာ တံတားအားလုံးကို အတိအကျတစ်ကြိမ်စီဖြတ်၍ မြို့ကိုပတ်လျှောက်ရန်ဖြစ်သည်။

ဤတွင် မလိုလားအပ်သော ပြဿနာများမဖြစ်စေရန်အတွက်

1. သတ်မှတ်ထားသောတံတားများမှ မဖြတ်ဘဲ ကျွန်းတစ်ခုနှင့်တစ်ခု ကူးခြင်း၊
2. တံတားများကို အစအဆုံးမလျှောက်ခြင်း၊

စသည်တို့ကို ကန့်သတ်ထားသည်။

Euler က ဤပြဿနာတွင် အဖြေမရှိကြောင်း သက်သေပြနိုင်ခဲ့သည်။

Euler ၏ ဖြေရှင်းချက်

ပထမဦးစွာ Euler က မြေကြီးပေါ်တွင်သွားသည့် လမ်းကြောင်း၏ ပုံစံသည် အရေးမကြီးကြောင်း ထောက်ပြခဲ့သည်။ ဤပြဿနာအတွက် အမှန်တကယ်အရေးပါသည်မှာ တံတားများကို ဖြတ်ရမည့် အစီအစဉ်သာဖြစ်သည်။ ထိုအချက်ကြောင့် Euler သည် ပြဿနာပုစ္ဆာအား abstract term များသုံး၍ ပြန်လည်ဖော်ပြနိုင်ခဲ့သည်။ (ယင်းအသုံးပြုချက်ကပင် ဂရပ်သီအိုရီ ၏မျိုးစေ့ဖြစ်ခဲ့သည်။) တစ်နည်းအားဖြင့် ထိုအချက်ကြောင့် မည်သည့်တံတားများက မည်သည့်ကျွန်းများကို ဆက်သွယ်ထားကြောင်းကိုသာ အာရုံစိုက်ရန်လိုကြောင်း သိခဲ့သည်။ ယနေ့ခေတ်သုံး သင်္ချာဝေါဟာရများနှင့်ရေးသော် ကျွန်းတစ်ခုစီကို vertex သို့မဟုတ် node တစ်ခုနှင့် ဖော်ပြ၍ တံတားတစ်စင်းစီကိုမူ အစွန်း တစ်ခု (vertex စုံတွဲတစ်ခု) နှင့် ဖော်ပြသည်ဟု ရေးနိုင်သည်။ ရရှိလာသည့် သင်္ချာ structure ကို ဂရပ် ဟုခေါ်သည်။

→ →

မည်သည့်တံတား (edge) များက မည်သည့်ကျွန်း (vertex) များကို ဆက်သွယ်သည်ဟူသော ဆက်သွယ်ချက်ကသာ အရေးပါသည့်အတွက်ကြောင့် graph ၏ပုံကိုဆွဲရာတွင် ပုံစံမျိုးစုံဖြင့်ဆွဲနိုင်လေသည်။ Vertex နှစ်ခုအကြားတွင် edge ဖြင့်ဆက်ထားခြင်း မထားခြင်းကသာ အရေးပါသည်။ ဆက်ထားသည့်ဆက်ကြောင်း၏ ကောက်ခြင်းဖြောင့်ခြင်း၊ vertex နှစ်ခုဘယ်ညာလွဲနေခြင်း စသည်တို့လျစ်လျူရှုထားနိုင်ပေသည်။

ထို့နောက် လမ်းကြောင်းတိုင်းသည် စလျှောက်သည့်ကျွန်းနှင့် လမ်းကြောင်းဆုံးသည့်ကျွန်းမှအပ ကျန်သောကျွန်းတိုင်းကို တံတားတစ်စင်းသုံး၍ဝင်ခဲ့ပါက ပြန်ထွက်ရန်အတွက် အခြားတံတားတစ်စင်းကို သုံးကိုသုံးရမည်ဖြစ်ကြောင်း Euler က သတိထားမိခဲ့သည်။ တစ်နည်းအားဖြင့်ဆိုသော် လမ်းကြောင်းတစ်ခုတွင် (စသည့် vertex နှင့် ဆုံးသည့် vertex မှအပ) vertex များအားလုံး၌ အဝင်အဖြစ်အသုံးပြုခဲ့သော တံတားအရေအတွက်နှင့် အထွက်အဖြစ်အသုံးပြုခဲ့သော တံတားအရေအတွက်သည် အတူတူပင်ဖြစ်ရမည်ဖြစ်သည်။ သို့အတွက်ကြောင့် တံတားအားလုံးကို အတိအကျတစ်ကြိမ်သာဖြတ်သွားသည် လမ်းကြောင်းရှိပါက ထိုလမ်းကြောင်း၏ အစနှင့် အဆုံးကျွန်းများမှအပ ကျန်ကျွန်းအားလုံးတွင်ရှိရမည့် တံတားအရေအတွက်သည် စုံကိန်းသာဖြစ်ရလိမ့်မည်။ (တံတားတိုင်းကို အဝင်တံတားနှင့် အထွက်တံတားဟူ၍ ညီညီမျှမျှအသုံးပြုခဲ့သောကြောင့်။) သို့ရာတွင် လက်တွေ့၌ မြေကျွန်းအသီးသီးရှိ တံတားအရေအတွက်သည် မကိန်းများ ဖြစ်နေလေသည်။ (အလယ်ခေါင်ရှိကျွန်းတွင် တံတား ၅ စင်းနှင့် ကျန်ကျွန်းများတွင် ၃ စင်းစီ။) ထို့ကြောင့် တံတားအားလုံးကို အတိအကျတစ်ကြိမ်စီဖြတ်သောလမ်းသာ ရှိနေခဲ့ပါက နှစ်ခုသောကျွန်းတို့၌ ရှိရမည့်တံတားအရေအတွက်သည် စုံကိန်းရော၊ မကိန်းပါ ဖြစ်ရတော့မည့်သဘော သက်ရောက်သွားသည်။ သို့ဖြစ်၍ တံတားအားလုံးကို အတိအကျတစ်ကြိမ်စီဖြတ်သောလမ်း ဆိုသည်မှာ မရှိနိုင်ဟူ၍ ကောက်ချက်ဆွဲနိုင်လေသည်။