រទេះរុញ ឡានសម្អាតផ្លូវ និងអ្នករត់សំបុត្រ គឺជាឧទាហរណ៍សម្រាប់រថយន្ត និងមនុស្សដែលត្រូវឆ្លងកាត់ផ្លូវនីមួយៗ ប៉ុន្តែចង់ជៀសវាងការឆ្លងកាត់ផ្លូវពីរដង។

ទ្រឹស្ដីក្រាហ្វបានចាប់ផ្តើមនៅពេលដែលគណិតវិទូ Leonhard Euler កំពុងធ្វើការលើផ្លូវប្រភេទនេះ។

អឺលែរបានសរសេរក្រដាសនៅលើស្ពានទាំងប្រាំពីរនៃ Königsberg ដែលបង្ហាញថាវាមិនអាចទៅរួចទេក្នុងការដើរឆ្លងកាត់ទីក្រុងឆ្លងកាត់ស្ពាននីមួយៗពិតប្រាកដតែម្តង។

ចុចលើផែនទីនៃបញ្ហាខាងក្រោមដើម្បីអានបន្ថែមអំពីវា។

បង្ហាញ៖

ការរាប់ចុងបញ្ចប់នៃគែមទាំងអស់ផ្តល់លេខដូចគ្នានឹងការបន្ថែមដឺក្រេទាំងអស់នៃថ្នាំង ទាំងអស់ យល់ព្រម?

ដោយសារគែមនីមួយៗមានចុង 2 ចំនួនសរុបនៃគែមទាំងអស់ត្រូវតែស្មើគ្នា។ (ការបន្ថែមលេខគូផ្តល់លេខគូ។ )

ដើម្បីបន្ថែមដឺក្រេនៃថ្នាំងទាំងអស់ មួយនឹងបន្ថែមដឺក្រេគូដែលផ្តល់លេខគូ និងបន្ថែមដឺក្រេសេស។

ប្រសិនបើមានចំនួនសេសនៃថ្នាំងដឺក្រេសេស នោះផលបូកនោះនឹងជាសេស ហើយបន្ទាប់មក គូ + សេស = សេស ដូច្នេះចំនួនសរុបនៃដឺក្រេនឹងជាសេស។ ប៉ុន្តែវាស្មើនឹងចំនួនសរុបនៃចុងទាំងអស់នៃគែមទាំងអស់ ហើយនោះគឺស្មើ។ ដូច្នេះ ចំនួនថ្នាំងដឺក្រេសេសមិនអាចសេសបានទេ វា ត្រូវតែ ស្មើគ្នា។

ឧទាហរណ៍ 1 គឺជាលេខសេស ដូច្នេះមិនមានក្រាហ្វដែលមានតែ 1 ថ្នាំងសេសទេ។

ប្រសិនបើថ្នាំងមានដឺក្រេស្មើ ពោលគឺ 2, 4, 6, ... គែមត្រូវបានភ្ជាប់ទៅថ្នាំង បន្ទាប់មកនៅពេលមកដល់ថ្នាំងនោះ ចំនួនសេសនៃគែមដែលមិនប្រើគឺនៅសល់ដែលធំជាងសូន្យ ដូច្នេះមួយនឹងត្រូវបាន អាចចាកចេញពីថ្នាំងនោះ ហើយបន្តទៅមុខទៀត។ ប្រសិនបើដឺក្រេគឺសេស ពោលគឺ 1, 3, 5,.. គែមត្រូវបានភ្ជាប់ បន្ទាប់មកមួយត្រូវតែចាប់ផ្តើមផ្លូវនៅថ្នាំងនេះ ឬផ្លូវនឹងបញ្ចប់នៅថ្នាំងនេះ។ ដោយសារតែផ្លូវមួយមានត្រឹមតែ 2 ចុង វាអាចមានត្រឹមតែ 2 ថ្នាំងដែលមានកម្រិតសេស។ ដូច្នេះ៖

ដើម្បីឱ្យមានវដ្តអឺលែរ ក្រាហ្វត្រូវតែមានថ្នាំងតែមួយដឺក្រេ ហើយដើម្បីមានគន្លងអឺលែរ វាត្រូវតែមាន 2 ថ្នាំងកម្រិតសេស ថ្នាំងមួយនឹងជាការចាប់ផ្តើម ហើយមួយទៀតជាចុងបញ្ចប់នៃផ្លូវ .

ដើម្បីពិនិត្យមើលថាតើគែមមួយគឺជាស្ពាន ឬអត់នោះ វានឹងចាប់ផ្តើមនៅចុងម្ខាងនៃគែម ហើយចូលមើលថ្នាំងអ្នកជិតខាងទាំងអស់ និងអ្នកជិតខាងទាំងអស់របស់ពួកគេជាដើម។ បើ​គេ​មិន​ចូល​ទៅ​ម្ខាង​ទៀត​នៃ​គែម​ទេ នោះ​គែម​នោះ​ជា​ស្ពាន។ ការស្វែងរកទាំងស្រុងបែបនេះរបស់អ្នកជិតខាងទាំងអស់មិនថ្លៃខ្លាំងទេ។ ប៉ុន្តែប្រសិនបើនរណាម្នាក់ត្រូវធ្វើវាមុនពេលឆ្លងកាត់គែមនីមួយៗ នោះការខិតខំប្រឹងប្រែងសរុបគឺធំ ក្បួនដោះស្រាយពេញលេញត្រូវបានគេហៅថា Fleury's algorithm ដែលមានអាយុកាលតាំងពីឆ្នាំ 1883 ។

ក្បួនដោះស្រាយដែលមានប្រសិទ្ធភាពជាងគឺ Hierholzer (1873) ។

ប្រសិនបើក្រាហ្វមាន 2 ថ្នាំងដឺក្រេសេស នោះគេរកឃើញផ្លូវមួយបើមិនដូច្នេះទេវដ្ដ ក្នុងករណីទាំងពីរនេះលឿនណាស់ដោយមិនពិនិត្យមើលស្ពាន។

1) បន្ទាប់ពីការដកគែមដែលបានប្រើទាំងអស់ កម្រិតនៃគែមដែលមិនប្រើដែលនៅសល់គឺសូម្បីតែសម្រាប់ថ្នាំងទាំងអស់។

ហេតុអ្វី?

2) ត្រូវតែមានយ៉ាងហោចណាស់ថ្នាំងមួយដែលមានគែមជាប់គ្នាដែលប្រើហើយមិនប្រើ។

ហេតុអ្វី?

ដោយសារតែ 1) មនុស្សម្នាក់អាចរកឃើញវដ្តនៃគែមដែលមិនប្រើ ដោយចាប់ផ្តើម និងបញ្ចប់នៅថ្នាំងនេះ។ ដោយសារតែ 2) វដ្តនេះអាចត្រូវបានរួមបញ្ចូលនៅក្នុងផ្លូវ / វដ្តដំបូងនៅពេលដែលវាឈានដល់ថ្នាំងនេះ។ ការបង្កប់នៃវដ្តនៃគែមដែលមិនប្រើរហូតមកដល់ពេលនេះ ត្រូវបានធ្វើម្តងទៀតរហូតដល់គែមទាំងអស់ត្រូវបានប្រើប្រាស់ ហើយដូច្នេះមួយមានគន្លងអឺលែរ ឬ វដ្តអឺលែរ ដែលប្រើគែមទាំងអស់។

តើ​កំណែ​លឿន​ជាង​នេះ​តម្លៃ​ប៉ុន្មាន?

ឧទាហរណ៍៖

     2   4  
    / \ / \ 
   1---3---5

សូមឱ្យវដ្តទីមួយគឺ 1-3-2-1 ។ ថ្នាំង 3 កើតឡើងនៅក្នុងវដ្តនេះ និងនៅក្នុងវដ្តដែលមិនប្រើ 3-4-5-3 ។ យើងបញ្ចូលវាទៅក្នុងវដ្តទីមួយ ហើយទទួលបានវដ្ត 1-3-4-5-3-2-1។ មិនមានគែមដែលមិនប្រើទៀតទេ ដូច្នេះក្បួនដោះស្រាយបញ្ចប់នៅទីនេះ យើងបានរកឃើញវដ្តអឺលែរ ។

តើ​វដ្ដ​អាច​បញ្ចូល​ដោយ​របៀប​ណា​ដោយ​ប្រើ​ចំណុច​ប្រទាក់​របស់​យើង?

រាល់ពេលដែលគេទៅដល់ថ្នាំង មនុស្សម្នាក់ក៏ចាកចេញពីថ្នាំងដែរ ដូច្នេះចំនួនគែមគូត្រូវបានប្រើប្រាស់។ ឥឡូវនេះ មួយមកដល់ ហើយប្រើគែមមួយនៅលើថ្នាំងដឺក្រេគូ។ ដូច្នេះមួយបានប្រើសរុបចំនួនសេសនៃគែមនៅលើថ្នាំងដឺក្រេគូ។