ក្បួនដោះស្រាយ Kruskal របស់ - សំណង់នៃក្របខ័ណ្ឌល្អប្រសើរបំផុតនោះ

ក្នុង geometer ដើមសតវត្សទី 19 ពីក្រុងបែរឡាំង Jakob Steiner កំណត់ភារកិច្ចនៃរបៀបតភ្ជាប់ភូមិចំនួនបីដូច្នេះប្រវែងរបស់ពួកគេគឺខ្លីបំផុតបាន។ ក្រោយមកគាត់បានសង្ខេបបញ្ហានេះ: វាត្រូវបានទាមទារដើម្បីរកចំណុចក្នុងយន្តហោះមួយចម្ងាយពីវាទៅ n ចំណុចផ្សេងទៀតត្រូវបានគេទាបបំផុត។ នៅសតវត្សទី 20 នេះវានៅតែបន្តធ្វើការនៅលើប្រធានបទនេះ។ វាត្រូវបានគេសម្រេចចិត្តដើម្បីយកពិន្ទុមួយចំនួននិងភ្ជាប់ពួកវានៅក្នុងវិធីដូចថាចម្ងាយរវាងពួកគេគឺខ្លីបំផុតបាន។ ទាំងអស់នេះជាករណីពិសេសនៃបញ្ហានេះកំពុងត្រូវបានសិក្សា។

ក្បួនដោះស្រាយ "លោភ"

ក្បួនដោះស្រាយ Kruskal បានសំដៅទៅលើក្បួនដោះស្រាយ "លោភលន់" (ហៅផងដែរថាជម្រាល) ។ សារៈសំខាន់នៃការទាំងនោះ - ការទទួលជ័យជម្នះខ្ពស់បំផុតនៅលើជំហានគ្នា។ មិនមែនជានិច្ច, ក្បួនដោះស្រាយ "លោភលន់" ការផ្តល់នូវដំណោះស្រាយល្អបំផុតចំពោះបញ្ហានេះ។ មានទ្រឹស្តីមួយគឺបង្ហាញថានៅក្នុងកម្មវិធីរបស់ពួកគេដើម្បីភារកិច្ចជាក់លាក់ដែលពួកគេបានផ្តល់នូវដំណោះស្រាយដែលល្អបំផុតនោះ។ នេះជាទ្រឹស្តីនៃ matroids នេះ។ ក្បួនដោះស្រាយ Kruskal បានសំដៅទៅលើបញ្ហាបែបនេះ។

ការរកទម្ងន់ carcass អប្បបរមា

ក្បួនដោះស្រាយបានអានៈសង់រាប់ស៊ុមមួយល្អប្រសើរបំផុត។ បញ្ហារបស់វាគឺមានដូចខាងក្រោម។ លោក Dan undirected ក្រាហ្វិកដោយគ្មានគែមស្របនិងរង្វិលជុំនិងសំណុំនៃគែមត្រូវបានផ្ដល់មុខងារទម្ងន់ w ដែលកំណត់ចំនួនទៅគែមអ៊ីគ្នា - ឆ្អឹងជំនីទម្ងន់ - សរសេរ (អ៊ីមែល) ។ ទម្ងន់នៃសំណុំរងគ្នានៃការមានពហុភាពនៃឆ្អឹងជំនីនេះគឺជាការបូកនៃទម្ងន់របស់គែមរបស់វា។ ត្រូវការដើម្បីរកឱ្យឃើញគ្រោងឆ្អឹងនៃទម្ងន់តូចមួយ។

បរិយាយ

ក្បួនដោះស្រាយ Kruskal ធ្វើការ។ ដំបូងគែមទាំងអស់នៃក្រាហ្វដំបូងគឺត្រូវបានរៀបចំឡើងលំដាប់នៃទម្ងន់។ ដំបូងស៊ុមមិនមានឆ្អឹងជំនីរណាមួយនោះទេប៉ុន្តែរួមទាំងការកំពូលទាំងអស់។ បន្ទាប់ពីជំហានបន្ទាប់នៃក្បួនដោះស្រាយទៅជាផ្នែកមួយរួចទៅហើយនៃគ្រោងឆ្អឹងសាងសង់នេះដែលជាព្រៃសម្រាប់ព្រឹត្តិការណ៍, គែមមួយត្រូវបានបន្ថែម។ វាមិនត្រូវបានជ្រើសរើសដោយបំពាន។ គែមទាំងអស់នៃក្រាហ្វដែលមិនមែនជាកម្មសិទ្ធិរបស់ស៊ុម, អាចត្រូវបានគេហៅថាក្រហមនិងបៃតង។ កំពូលនៃគែមក្រហមគឺនៅក្នុងគ្នាសមាសភាគដូចគ្នានេះស្ថិតក្រោមការតភ្ជាប់ព្រៃសំណង់និងកំពូលបៃតង - ខុសគ្នា។ ដូច្នេះប្រសិនបើអ្នកបានបន្ថែមទៅគែមក្រហមនេះមានវដ្តមួយហើយបើបៃតង - ដូចជាបានទទួលបន្ទាប់ពីជំហាននេះសមាសភាគឈើភ្ជាប់នេះនឹងមានតិចជាងមួយ។ ដូច្នេះសំណង់លទ្ធផលមិនអាចបន្ថែមបានទេគែមក្រហមប៉ុន្តែគែមបៃតងណាមួយអាចត្រូវបានបន្ថែមដើម្បីទទួលបានព្រៃ។ ហើយបន្ថែមគែមបៃតងដែលមានទម្ងន់តិចបំផុត។ លទ្ធផលគឺក្របខ័ណ្ឌនៃទម្ងន់អប្បបរមា។

ការអនុវត្តន៍

បញ្ជាក់ព្រៃនាពេលបច្ចុប្បន្ននេះអេហ្វវាបែងចែកសំណុំនៃកំពូលនៅក្នុងវាលនៃការតភ្ជាប់ (ទម្រង់សហជីពរបស់ខ្លួនស្រី, ហើយពួកគេមាន disjointed) ។ នៅគែមទាំងពីរនៃកំពូលក្រហមដែលពួកគេបានកុហកនៅក្នុងមួយដុំ។ ជាផ្នែកមួយ (X) - មុខងារកំពូលគ្នា x ត្រឡប់ផ្នែកនៃឈ្មោះនេះ, វាជារបស់ X ។ Unite (x, y) - នីតិវិធីដែលកសាងភាគថាសថ្មីមួយដែលមានរួមបញ្ចូលគ្នារវាងផ្នែកខ្លះនៃ x និង y និងផ្នែកដទៃទៀតទាំងអស់។ សូមឱ្យ n - ចំនួននៃគែម។ គំនិតទាំងអស់នេះត្រូវបានរួមបញ្ចូលក្នុងក្បួនដោះស្រាយ Kruskal នេះ។ ការអនុវត្តន៍:

1. រៀបចំគែមទាំងអស់របស់ក្រាហ្វទី 1 ដល់ n-ឡើងទម្ងន់លើកទីនេះ។ (ក្រុងអៃទ្វេ - ខ្ញុំជាមួយនឹងចំនួនគែមចំណុចកំពូល) ។

2. សម្រាប់ខ្ញុំ = 1 ដល់ n ធ្វើ។

3. x: = ផ្នែក (AI) ។

4. y: = ផ្នែក (ពីរ) ។

5. ប្រសិនបើមាន x y ដែលមិនស្មើបន្ទាប់មក Unite (x, y) ដើម្បីរួមបញ្ចូលជាមួយចំនួនគែមស្រីខ្ញុំ។

ភាពត្រឹមត្រូវ

សូមឱ្យក្រុមហ៊ុន T - ស៊ុមរបស់ក្រាហ្វដើមសាងសង់ប្រើក្បួនដោះស្រាយ Kruskal និង S - ស៊ុមបំពានរបស់ខ្លួន។ យើងមានដើម្បីបញ្ជាក់ថា W (T) គឺមិនធំជាង W (S) ។

សូមអោយ M - ពហុភាពនៃមន្ទីរព្រុយ, P - ពហុភាពនៃព្រុយ T. ប្រសិនបើការរបស់ S គឺជាការមិនស្មើទៅនឹងក្រុមហ៊ុន T, បន្ទាប់មកមាននិងឆ្អឹងជំនីស៊ុម T មាន, មិនដែលជាកម្មសិទ្ធិរបស់អេសអេសនិង adjoining វដ្ត, វាត្រូវបានគេហៅថាគគបានយកចេញពី es គែមណាមួយដែលជាកម្មសិទ្ធិរបស់ អេសយើងទទួលបានស៊ុមថ្មីមួយ, ដោយសារតែគែមនិងកំពូលគឺដូចគ្នា។ ទំងន់របស់វាគឺមិនធំជាង W (S) ចាប់តាំងពីការសរសេរ (និង) មិនយូរទៀតទេ W (គឺ) នៅក្នុងអំណាចក្បួន Kruskal ។ ប្រតិបត្ដិការនេះ (ឆ្អឹងជំនីរក្រុមហ៊ុន T S បានជំនួសនៅលើឆ្អឹងជំនីរ) នឹងត្រូវបានធ្វើម្តងទៀតដរាបណាបានទទួលធីទម្ងន់នៃស៊ុមទទួលបានជាបន្តបន្ទាប់គ្នានេះគឺមិនធំជាងទម្ងន់មុនដែលបញ្ជាក់ថា W (T) គឺមិនធំជាង W (S) ។

ភាពមាំមួននៃក្បួនដោះស្រាយ Kruskal នេះធ្វើឡើងបន្ទាប់ពីទ្រឹស្តីបទនៃ Rado-Edmonds នៅលើ matroids ។

ឧទាហរណ៍ការកម្មវិធីក្បួនដោះស្រាយ Kruskal

ក្រាហ្វដាន់ជាមួយនឹងការថ្នាំងមួយ, B, C, D, E និងឆ្អឹងជំនីរ (a, b), (A, E), (B, C), (ខ, អ៊ី), (C, D), (គ, ង) (D, e) ។ ទម្ងន់នៃគែមដែលត្រូវបានបង្ហាញនៅក្នុងតារាងហើយនៅក្នុងតួលេខនេះ។ ដំបូងព្រៃសំណង់ស្រីមានកំពូលទាំងអស់នៃក្រាហ្វនិងមិនមានឆ្អឹងជំនីរណាមួយឡើយ។ ក្បួនដោះស្រាយ Kruskal ដំបូងបន្ថែមឆ្អឹងជំនី (A, E), ចាប់តាំងពីមានទំងន់មានទាបបំផុតនិងកំពូលមួយនិងអ៊ីមាននៅក្នុងសមាសភាគផ្សេងគ្នាតភ្ជាប់ឈើស្រី (ឆ្អឹងជំនី (A, E) គឺបៃតង), បន្ទាប់មកឆ្អឹងជំនីរនេះ (គ, ឃ) ដោយសារតែ ថាយ៉ាងហោចណាស់នេះទម្ងន់គែមនៃគែមក្រាហ្វដែលមិនមែនជាកម្មសិទ្ធិរបស់ស្រី, ហើយវាគឺជាបៃតង, បន្ទាប់មកសម្រាប់ហេតុផលដូចគ្នាបន្ថេមគែម (a, b) ។ ប៉ុន្តែគែម (ខ, អ៊ី) ត្រូវបានអនុម័តទោះបីជាគាត់និងទំងន់អប្បបរមានៃគែមដែលនៅសល់, ព្រោះវាជាក្រហម: កំពូលខនិងអ៊ីមែលជាកម្មសិទ្ធិរបស់សមាសភាគដូចគ្នានៃការតភ្ជាប់ព្រៃស្រីគឺថាប្រសិនបើយើងបន្ថែមទៅស្រីគែម (ខ, អ៊ីមែល) នេះត្រូវបានបង្កើតឡើង វដ្ត។ បន្ទាប់មកបានបន្ថែមគែមបៃតង (ខ, គ) ត្រូវបានអនុម័តគែមក្រហម (គ, ង), ហើយបន្ទាប់មក D, E ។ បន្តគ្នាដូច្នេះគែមត្រូវបានបន្ថែម (A, E), (C, D), (a, b), (B, C) ។ ពី nihera ស៊ុមល្អប្រសើរបំផុតនិងមានក្រាហ្វដើម។ ដូច្នេះក្នុងករណីនេះវាប្រតិបត្តិការក្បួនដោះស្រាយមួយ Kruskal ។ ឧទាហរណ៍មួយត្រូវបានបង្ហាញ។

តួលេខនេះបានបង្ហាញក្រាហ្វិកមួយដែលមានសមាសភាគតភ្ជាប់ពីរ។ បន្ទាត់ដិតបង្ហាញពីឆ្អឹងជំនីរស៊ុមល្អប្រសើរបំផុត (បៃតង) បានសាងសង់ប្រើក្បួនដោះស្រាយ Kruskal ។

រូបភាពក្រាហ្វកំពូលបង្ហាញដើមនិងបាត - គ្រោងនៃទម្ងន់តិចតួចបំផុតមួយបានកសាងឡើងសម្រាប់គាត់ដោយប្រើក្បួនដោះស្រាយបាន។

លំដាប់នៃឆ្អឹងជំនីបន្ថែម (1,6); (0,3), (2,6) ឬ (2,6), (0,3) - គឺមិនសំខាន់ទេ! (3,4); (0,1), (1,6) ឬ (1,6), (0,1) ផងដែរខ្វល់ (5,6) ។

ក្បួនដោះស្រាយ Kruskal បានរកឃើញថាការអនុវត្ត, ឧទាហរណ៍, ដើម្បីបង្កើនប្រសិទ្ធភាពទំនាក់ទំនង gasket នេះផ្លូវនៅតំបន់សួនឧស្សាហកម្មការលំនៅដ្ឋានថ្មីនៅក្នុងប្រទេសនីមួយ, ដូចជានៅក្នុងករណីផ្សេងទៀត។