ຂັ້ນຕອນວິທີ Kruskal ຂອງ - ການກໍ່ສ້າງຂອງໂຄງຮ່າງການທີ່ດີທີ່ສຸດ

ໃນຕົ້ນ geometer ຕະວັດທີ 19 Jakob Steiner ຈາກເບີລິນກໍານົດຫນ້າວຽກຂອງວິທີການເຊື່ອມຕໍ່ສາມບ້ານດັ່ງນັ້ນຄວາມຍາວຂອງເຂົາເຈົ້າແມ່ນສັ້ນທີ່ສຸດ. ຫຼັງຈາກນັ້ນ, ເຂົາສະຫຼຸບບັນຫາ: ມັນຈໍາເປັນຕ້ອງມີເພື່ອຊອກຫາຈຸດໃນຍົນໄດ້, ໄລຍະຫ່າງຈາກມັນກັບ n ຈຸດອື່ນໆໄດ້ຕ່ໍາສຸດ. ໃນສະຕະວັດທີ 20 ໄດ້, ມັນຍັງຈະສືບຕໍ່ເຮັດວຽກກ່ຽວກັບຫົວຂໍ້ນີ້. ມັນໄດ້ຕັດສິນໃຈທີ່ຈະໃຊ້ເວລາຈຸດໃດຫນຶ່ງແລະການເຊື່ອມຕໍ່ໃຫ້ເຂົາເຈົ້າໃນລັກສະນະທີ່ໄລຍະຫ່າງລະຫວ່າງເຂົາເຈົ້ານີ້ແມ່ນ shortest ໄດ້. ທັງຫມົດນີ້ເປັນກໍລະນີພິເສດຂອງບັນຫາທີ່ທ່ານກໍາລັງສຶກສາ.

"Greedy" ຂັ້ນຕອນວິທີ

ຂັ້ນຕອນວິທີ Kruskal ຂອງຫມາຍເຖິງ "greedy" ຂັ້ນຕອນວິທີ (ເອີ້ນວ່າຍັງ gradient). ໂດຍເນື້ອແທ້ແລ້ວຂອງເຫຼົ່ານັ້ນ - ໄດ້ໄຊຊະນະທີ່ສູງທີ່ສຸດໃນແຕ່ລະຂັ້ນຕອນ. ບໍ່ສະເຫມີໄປ, "greedy" ຂັ້ນຕອນວິທີສະຫນອງການແກ້ໄຂທີ່ດີທີ່ສຸດກັບບັນຫາ. ມີທິດສະດີເປັນ, ສະແດງໃຫ້ເຫັນວ່າໃນຄໍາຮ້ອງສະຫມັກຂອງເຂົາເຈົ້າກັບວຽກງານສະເພາະໃດຫນຶ່ງທີ່ເຂົາເຈົ້າໃຫ້ການແກ້ໄຂທີ່ເຫມາະສົມ. ນີ້ແມ່ນທິດສະດີຂອງ matroids ໄດ້. ຂັ້ນຕອນວິທີ Kruskal ຂອງຫມາຍເຖິງບັນຫາດັ່ງກ່າວ.

ຊອກຫານ້ໍາ carcass ຕ່ໍາສຸດ

ຂັ້ນຕອນວິທີເບິ່ງສ້າງເປັນຈໍານວນກອບທີ່ດີທີ່ສຸດ. ບັນຫາຂອງມັນແມ່ນເປັນດັ່ງຕໍ່ໄປນີ້. Dan undirected ເສັ້ນສະແດງການໂດຍບໍ່ມີການຂອບຂະຫນານແລະ loops, ແລະທີ່ກໍານົດໄວ້ຂອງແຄມຂອງແມ່ນໄດ້ຮັບການທໍາງານຂອງນ້ໍາຫນັກ w, ເຊິ່ງມອບຫມາຍເລກທີ່ໃນແຕ່ລະຂອບ e - rib ນ້ໍາຫນັກ - w (e). ນ້ໍາຂອງປີກຍ່ອຍຂອງນາມຂອງ ribs ໃນແຕ່ລະແມ່ນລວມຍອດຂອງນ້ໍາຂອງຂອບດັ່ງກ່າວ. ຈໍາເປັນຕ້ອງໄດ້ຊອກຫາກະດູກຂອງນ້ໍາຂະຫນາດນ້ອຍໄດ້.

ຄໍາອະທິບາຍ

ຂັ້ນຕອນວິທີ Kruskal ຂອງເຮັດວຽກ. ຫນ້າທໍາອິດ, ແຄມທັງຫມົດຂອງເສັ້ນສະແດງຄັ້ງທໍາອິດແມ່ນຈັດຢູ່ໃນຕັ້ງຊັນຂຶ້ນທຽບຄໍາສັ່ງຂອງນ້ໍາ. ໃນເບື້ອງຕົ້ນ, ກອບບໍ່ປະກອບດ້ວຍກະດູກແຕ່ປະກອບດ້ວຍການຕັ້ງທັງຫມົດ. ຫຼັງຈາກຂັ້ນຕອນຕໍ່ໄປຂອງຂັ້ນຕອນວິທີໃນການສ່ວນການກໍ່ສ້າງແລ້ວຂອງ carcass, ເຊິ່ງເປັນປ່າຢຽດ, ຫນຶ່ງຂອບແມ່ນເພີ່ມ. ມັນບໍ່ໄດ້ຖືກເລືອກຕາມອໍາເພີໃຈ. ແຄມທັງຫມົດຂອງເສັ້ນສະແດງ, ບໍ່ເປັນຂອງກອບການ, ສາມາດເອີ້ນວ່າສີແດງແລະສີຂຽວ. ດ້ານເທິງຂອງແຕ່ລະຄົນ, ແຂບສີແດງຢູ່ໃນອົງປະກອບດຽວກັນພາຍໃຕ້ການເຊື່ອມຕໍ່ປ່າໄມ້ການກໍ່ສ້າງ, ແລະ tops ສີຂຽວ - ທີ່ແຕກຕ່າງກັນ. ດັ່ງນັ້ນ, ຖ້າຫາກວ່າທ່ານເພີ່ມກັບແຂບສີແດງ, ມີວົງຈອນການ, ແລະຖ້າຫາກວ່າສີຂຽວ -. ເປັນທີ່ໄດ້ຮັບຫຼັງຈາກຂັ້ນຕອນນີ້ໄມ້ເຊື່ອມຕໍ່ອົງປະກອບຈະຫນ້ອຍກ່ວາຫນຶ່ງ ດັ່ງນັ້ນ, ໃນການກໍ່ສ້າງສົ່ງຜົນໃຫ້ບໍ່ສາມາດເພີ່ມບໍ່ມີຂອບສີແດງ, ແຕ່ຂອບສີຂຽວສາມາດເພີ່ມເພື່ອໃຫ້ໄດ້ຮັບປ່າທໍາມະຊາດ. ແລະເພີ້ມເປັນຂອບສີຂຽວກັບນ້ໍາຫນັກຕ່ໍາສຸດ. ຜົນໄດ້ຮັບເປັນໂຄງຮ່າງຂອງນ້ໍາຫນັກຕ່ໍາສຸດໄດ້.

ການປະຕິບັດ

ຊີ້ປ່າໄມ້ໃນປະຈຸບັນແອັຟມັນໄດ້ແບ່ງທີ່ກໍານົດໄວ້ຂອງຈຸດໃນພາກສະຫນາມຂອງການເຊື່ອມຕໍ່ໄດ້ (ຮູບແບບສະຫະພາບຂອງເຂົາເຈົ້າ F, ແລະພວກເຂົາເຈົ້າແມ່ນຕິດປະຕໍ່). ໃນທັງສອງແຄມຂອງຈຸດສີແດງທີ່ເຂົາເຈົ້ານອນຢູ່ໃນສິ້ນ. ສ່ວນ (x) - ການທໍາງານຂອງທີ່ສໍາລັບແຕ່ລະຈຸດຍອດ x ຈະກັບຄືນມາບາງສ່ວນຂອງຊື່ໄດ້, ມັນເປັນ x. ກາ (x, y) - ລະບຽບການທີ່ຈະສ້າງການແບ່ງປັນໃຫມ່, ປະກອບມີການສົມທົບພາກສ່ວນຂອງ x ແລະ y ແລະທຸກພາກສ່ວນອື່ນໆໄດ້. ໃຫ້ n - ຈໍານວນຂອງແຄມ. ແນວຄວາມຄິດທັງຫມົດເຫຼົ່ານີ້ແມ່ນຮວມຢູ່ໃນຂັ້ນຕອນວິທີ Kruskal ຂອງ. ການປະຕິບັດ:

1. ຈັດແຄມທັງຫມົດຂອງເສັ້ນສະແດງຈາກ 1 ກັບ n-th ນ້ໍາຫນັກຕັ້ງຊັນຂຶ້ນ. (Ai, bi - ຂ້າພະເຈົ້າມີຈໍານວນຂອບປາຍ).

2. ສໍາລັບຂ້າພະເຈົ້າ = 1 ກັບ n ເຮັດ.

3. x: = ຊິ້ນສ່ວນ (ai).

4. y = ຊິ້ນສ່ວນ (bi).

5. ຖ້າ x ບໍ່ y ເທົ່າທຽມກັນຫຼັງຈາກນັ້ນກາ (x, y) ຈະປະກອບມີຈໍານວນຂອບ F i ໄດ້.

ການກວດແກ້

ໃຫ້ T - ກອບຂອງເສັ້ນສະແດງຕົ້ນສະບັບກໍ່ສ້າງການນໍາໃຊ້ຂັ້ນຕອນວິທີ Kruskal ແລະ S - ກອບທີ່ຕົນເອງມັກຂອງຕົນ. ພວກເຮົາຈໍາເປັນຕ້ອງພິສູດວ່າ w (T) ບໍ່ແມ່ນຫຼາຍກ່ວາ w (S).

ໃຫ້ M - ສຽງຂອງຄີ S, P - ສຽງຂອງຄີ T. ຖ້າ S ບໍ່ແມ່ນເທົ່າທຽມກັນກັບ T, ຫຼັງຈາກນັ້ນມີການກອບ rib ແລະ T ບໍ່ເປັນ to S. S. ແລະຢູ່ໃກ້ຊິດວົງຈອນການ, ມັນຖືກເອີ້ນວ່າ C. C ເອົາຈາກ es ຂອບໃດ, ເປັນ S. ພວກເຮົາໄດ້ຮັບເປັນກອບໃຫມ່, ເນື່ອງຈາກວ່າຂອບແລະຈຸດແມ່ນດຽວກັນ. ນ້ໍາຫນັກຂອງຕົນບໍ່ແມ່ນຫຼາຍກ່ວາ w (S), ນັບຕັ້ງແຕ່ w (et) ບໍ່ມີຕໍ່ໄປອີກແລ້ວ w (es) ໃນຂັ້ນຕອນວິທີອໍານາດ Kruskal ໄດ້. ດໍາເນີນການ (ການທົດແທນ ribs T S on ribs) ຈະໄດ້ຮັບການຊ້ໍາເປັນໄດ້ຮັບ T. ນ້ໍາຫນັກຂອງແຕ່ລະພາໄດ້ຮັບຕໍ່ມາຫຼັງຈາກໄດ້ບໍ່ແມ່ນຫຼາຍກ່ວານ້ໍາຫນັກທີ່ຜ່ານມາ, ຊຶ່ງກໍຫມາຍຄວາມວ່າ w (T) ບໍ່ແມ່ນຫຼາຍກ່ວາ w (S).

ທີ່ເຂັ້ມແຂງຂອງຂັ້ນຕອນວິທີ Kruskal ຂອງດັ່ງຕໍ່ໄປນີ້ຈາກທິດສະດີບົດຂອງ Rado-Edmonds ກ່ຽວກັບ matroids ໄດ້.

ຄໍາຮ້ອງສະຫມັກຕົວຢ່າງຂັ້ນຕອນວິທີ Kruskal

Dan ເສັ້ນສະແດງການທີ່ມີຂໍ້ a, b, c, d, e ແລະ ribs (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). ນ້ໍາຫນັກຂອງແຄມແມ່ນສະແດງໃຫ້ເຫັນໃນຕາຕະລາງແລະໃນຮູບ. ໃນເບື້ອງຕົ້ນ, ປ່າໄມ້ກໍ່ສ້າງ F ປະກອບດ້ວຍການຕັ້ງທັງຫມົດຂອງເສັ້ນສະແດງແລະບໍ່ມີ ribs ໃດ. ສູດການຄິດໄລ່ Kruskal ທໍາອິດເພີ່ມ rib (a, e), ນັບຕັ້ງແຕ່ນ້ໍາຫນັກທີ່ມີການຕ່ໍາສຸດ, ແລະຕັ້ງແລະ e ຢູ່ໃນອົງປະກອບທີ່ແຕກຕ່າງກັນການເຊື່ອມຕໍ່ໄມ້ F (rib (a, e) ແມ່ນສີຂຽວ), ຫຼັງຈາກນັ້ນ rib ໄດ້ (c, d), ເນື່ອງຈາກວ່າ ວ່າຢ່າງຫນ້ອຍນີ້ນ້ໍາຫນັກຂອບຂອງແຄມເສັ້ນສະແດງການ, ບໍ່ເປັນ F, ແລະມັນເປັນສີຂຽວ, ຫຼັງຈາກນັ້ນສໍາລັບເຫດຜົນດຽວກັນເພີ້ມພູນຂອບ (a, b). ແຕ່ຂອບ (b, e) ແມ່ນຜ່ານການ, ເຖິງແມ່ນວ່າເຂົາແລະນ້ໍາຫນັກຕ່ໍາສຸດຂອງແຄມຍັງເຫຼືອ, ເນື່ອງຈາກວ່າມັນເປັນສີແດງ: ການຕັ້ງ b ແລະ e ຂຶ້ນກັບອົງປະກອບດຽວກັນຂອງການເຊື່ອມຕໍ່ປ່າ F, ວ່າແມ່ນ, ຖ້າຫາກວ່າພວກເຮົາໄດ້ເພີ່ມ F ແຂບໄດ້ (b, e), ຖືກສ້າງຕັ້ງຂຶ້ນ ວົງຈອນ. ຫຼັງຈາກນັ້ນ, ເພີ່ມຂອບສີຂຽວ (b, c), ແມ່ນຜ່ານການແຂບສີແດງ (c, e), ແລະຫຼັງຈາກນັ້ນ d, e. ດັ່ງນັ້ນ, ແຄມມີການເພີ່ມ sequentially (a, e), (c, d), (a, b), (b, c). From nihera ກອບທີ່ດີທີ່ສຸດແລະປະກອບດ້ວຍເສັ້ນສະແດງຕົ້ນສະບັບ. ດັ່ງນັ້ນໃນກໍລະນີນີ້ມັນດໍາເນີນຂັ້ນຕອນວິທີການ Kruskal. ຕົວຢ່າງສະແດງໃຫ້ເຫັນ.

ຕົວເລກດັ່ງກ່າວສະແດງໃຫ້ເຫັນເປັນເສັ້ນສະແດງການ, ຊຶ່ງປະກອບດ້ວຍສອງອົງປະກອບຕໍ່. ການສາຍກ້າຫານບຸ ribs ກອບທີ່ດີທີ່ສຸດ (ສີຂຽວ) ການກໍ່ສ້າງການນໍາໃຊ້ຂັ້ນຕອນວິທີ Kruskal.

ຮູບເທິງສະແດງໃຫ້ເຫັນໃນເສັ້ນສະແດງຕົ້ນສະບັບ, ແລະທາງລຸ່ມ - ໂຄງກະດູກຂອງນ້ໍາຫນັກຫນ້ອຍ, ສ້າງສໍາລັບພຣະອົງໂດຍການນໍາໃຊ້ສູດການ.

ລໍາດັບຂອງ ribs ເພີ່ມ (16); (03), (2,6) ຫຼື (2,6), (0,3) - ບໍ່ແມ່ນສິ່ງສໍາຄັນ; (3,4); (0,1), (1,6) ຫຼື (1,6), (0,1), ຍັງບົວລະບັດໃນ (5,6).

ຂັ້ນຕອນວິທີ Kruskal ຂອງເຫັນວ່າຄໍາຮ້ອງສະຫມັກພາກປະຕິບັດ, ສໍາລັບການຍົກຕົວຢ່າງ, ເພື່ອເພີ່ມປະສິດທິການສື່ສານ gasket, ຖະຫນົນຫົນທາງໃນໃຫມ່ທ້ອງຖິ່ນຊທີ່ຢູ່ອາໄສໃນແຕ່ລະປະເທດ, ເຊັ່ນດຽວກັນກັບໃນກໍລະນີອື່ນໆ.