Graph Theory Basic - PDF

ບ ົດທີ 6 ທິດສະດີກຣາຟພື້ນຖານ (Basic Graph Theory) 6.1 ບ ົດນ ໍາ (Introductions) ກຣາຟ ( Graph ) ເປັນເຄື່ ອງມທາງຄະນິດສາດອີກແບບໜື່ ງທີື່ ໃຊຈ ື້ າລອງ...

ບ ົດທີ 6 ທິດສະດີກຣາຟພື້ນຖານ (Basic Graph Theory) 6.1 ບ ົດນ ໍາ (Introductions) ກຣາຟ ( Graph ) ເປັນເຄື່ ອງມທາງຄະນິດສາດອີກແບບໜື່ ງທີື່ ໃຊຈ ື້ າລອງບ ໍ ນ ັ ຫາບາງຢາ ື່ ງດວ ື້ ຍ ຮູບພາບແລວ ື້ ິດສະດີທາງຄະນິດສາດໜື່ ງໃນນນແມ ື້ ນ ໍາໃຊທ ັື້ ນທິ ື່ ດສະດີຂອງຄອມບີນາຕໍ ຣກ ິ ແກບ ື້ ນ ັ ຫາໂດຍ ື່ ດສະດີກຣາຟ (Graph theory)ນນເອງ. ສະເພາະແມນທິ ັື້ ແ ນ ວ ຄ ວ າມ ຄິ ດ ກ ື່ຽ ວ ກ ບ ັ ທິ ດສ ະດີ ກ ຣາຟ ໄດ ື້ ກ ໍາເນີດມາແຕດ ື່ ົນນານແລວ ື່ ີຄ.ສ1736 ຊື່ ງທື່ານເລ ື້ ເລີື່ ມແຕປ ອອນຮາດ ອອຍເລີ (Leonhard Euler ຄ.ສ. 1707-1783) ນ ັກຄະນິດສາດ ປະເທດສະວິດ ໄດພ ື້ ະຍາຍາມທີື່ ຈະແກໄື້ ຂ ບນ ົ ໂກນິ ກ ເບີ ກ (Konigsberg Bridge)”ທີື່ ຕ ງັ ື້ ຢູື່ ັ ຫາ “ຂ ວ ໃນຣາຊະອານາຈ ັກ Prussia ໂດຍມີແ ມ ນ ໍື້ ື່ Pregel ໄຫຼ ື່ າຊ ຜາື່ ນເມອງນີື້ ແລະ ກາງແມນ ໍື້ ເກາະ 2 ເກາະ, ຊື່ ງເເປັນ ື່ າມີ ການແບງື່ ແຜນ ົ ເມອງອອກເປັນ 4 ສວ ື່ ດິນຕວ ື່ ນ, ໂດຍມີຂ ົວ 7 ຂ ົວເຊື່ ອມລະຫວາື່ ງເກາະ ແລະ ຝັື່ ງ ແມນ ື່ າໍື້ ດື່ງັ ທີື່ ສະ ແດງ ໃນຮູບທີ1 ຮູບທີ 6.1: ຂ ົວທັງ 7 ແຫງ ື່ ເມອງໂກນິກເບີກ ື້ ດຕ ປະຊາຊ ົນໃນເມອງນີໄ ັ ື້ ນ ື້ ງບ ັ ຫາວາື່ ເປັນໄປໄດ ື້ ຫຼ ບໍື່ ທີື່ ຈະຂາື້ ມຜາື່ ນຂ ົວໃຫື້ຄ ົບທຸກຂ ົວ,ໂດຍແຕ ື່ ລະຂ ົວຂາື້ ມໄດພ ັ ື້ ື້ ຽງຄງດຽວແລ ື້ວ ກ ັບມາສູຈ ື່ ດ ົື້ , ເລອອນຮາດ ອອຍເລີ ໄດວ ຸ ເລີື່ ມຕນ ັ ຫານີື້ ແລະ ື້ ິເຄາະບນ ພິສດ ື້ ື່ ີຈະຫາທາງເດີນດງ ູ ວາື່ ເປັນໄປບໍື່ ໄດທ ື່ ັ ກາື່ ວ, ສຸດທາ ື້ ຍບນ ື່ ັ ກາື່ ວແມນຍ ັ ຫາຂ ົວດງ ື່ ັງບໍື່ ສາມາດແກໄື້ ຂໄດ.ື້ ຕໍື່ ມາປີ ຄ.ສ 1847 ທື່ານ ກຽກຊ ັອບ (Kichhoft) ນ ໍາເອົ າທິ ດສະດີກຣາຟໄປໃຊກ ື້ ັບການສກສາເຄື່ ອຂາື່ ຍ ວ ົງຈອນໄຟຟື້າ, ໃນປີ ຄ.ສ 1857 ທື່ານ ໄກເລ (Cayley) ໄດນ ື້ ໍາເອົ າທິ ດສະດີກຣາຟໄປປະກອບໃຊກ ື້ ັບ ັ (Hamiton) ໄດໃື້ ຊກ ວິຊາເຄມີ ແລະ ທື່ານ ຮາມິນຕນ ື້ ັງ ື້ ຣາຟສກສາເກມປິ ດສະໜາຕາື່ ງໆ. ນອກຈາກນີຍ ື້ ື່ ີບໍື່ ແມນນ ມີນ ັກຄະນິດສາດ ແລະ ຜູທ ື່ ັກຄະນິດສາດໂດຍກ ົງອີກຫຼ າຍໆທາ ື່ ນໄດນ ື້ ໍາເອົ າວິຊາທິດສະດີກຣາຟ ໄປປະກອບໃຊໃື້ ນການສ ກສາແຜນທີື່ ແລະ ການລະບາຍສີ ແ ຜນທີື່ ຈ ົນເຖິງ ສ ດ ັ ຕະວ ດ ັ ທີື່ 20 ຄ ຄ.ສ. 1936 ທື່ າ ນ ເດເນສ ໂກນິກ ໄດ ຂ ື້ ຽນປື້ ມ ວິ ຊ າທິ ດ ສະດີກ ຣາຟຂື້ນ ເປັ ນ ເຫຼັື້ ມ ທ ໍາອິ ດ ແລະ ນ ັບແຕ ື່ນ ນ ັ ື້ ົື້ ມາການສ ກສາທິ ດ ສະດີ ກ ຣາຟໄດ ື້ເ ພີື່ ມຂື້ ນ ແລະ ຖ ກນ ໍາໄປໃຊ ື້ຢື່ າ ງກວ ື້າ ງຂວາງໃນສາຂາ ເປັ ນ ຕ ນ ວິທະຍາສາດຄອມພິວ ເຕີ, ເຄມີສາດ, ວິສະວະກ ໍາ, ພູມສາດ, ເສດຖະສາດ, ນິເວດວິທະຍາ, ວ ດ ັ ສະດຸ ສາດ ແລະ ການຂ ົນສື່ງົ ເປັນຕນ. ື້ົ ເວົື້ າລວມແລື້ວກຣາຟເປັນໂຄງສາື້ ງທີື່ ປະກອບດວ ື້ ຍຈອມ ແລະ ເສັ ື້ ນເຊື່ ອມລະຫວ າື່ ງຈອມ ສອງ ຈອມ ຫຼ ຫຼ າຍຈອມ, ຊື່ ງເກອບທຸກສາຂາວິຊາສາມາດຈາລອງແບບໄດ ໍ ດ ື້ ວ ື້ ຍກຣາຟເຊັື່ ນ: ແບບຈ ໍາລອງ ເສັື້ນທາງເຊື່ ອມຕໍື່ ລະຫວາື່ ງເມອງຕາື່ ງໆ, ແບບຈາລອງເສັ ໍ ື້ນທາງການບິນ ແລະ ອື່ ນໆ. 133 6.2 ນິຍາມ ແລະ ຕ ົວຢາື່ ງ ❖ນິຍ າມ 6.1: ກຣາຟ (Graph) ປະກອບດ ວ ື້ ຍ 2 ກຸມ ື່ ຈອມ V(Vertex Set) ແລະ ກຸມ ື່ ຄ : ກຸມ ື່ ຂາື້ ງ E (Edge Set) ເຊິື່ ງກຸມ ື່ V ເປັນກຸມ ໍ ັດ ແລະ V   ກຸມ ື່ ຈາກ ື່ ຂາື້ ງ E ເປັນກຸມ ື່ ຂອງອະນຸກມ ຸື່ ທີື່ ມີສອງ ື່ V ເຊິື່ ງສ ັນຍາລັກດວ ອ ົງປະກອບຂອງກຸມ ື້ ຍ G = (V, E ). ໂດຍທົື່ ວໄປເພິື່ ນນິຍ ົມແບງື່ ກຣາຟອອກເປັນ 2 ຊະນິດຄ: ກຣາຟລະບຸທິດທາງ (Directed Graph) ແລະ ກຣາຟບໍື່ ລະບຸທິດທາງ (Undirected Graph) ດງ ື່ ັ ລາຍລະອຍດລຸມ ື່ ນີ:ື້ ກຣາຟ (Graph) ກຣາຟບໍື່ ລະບຸທິດທາງ ກຣາຟລະບຸທິດທາງ (Undirected Graph) (Directed Graph) ກຣາຟງາຍດາຍ ື່ (Simple Graph) ກຣາຟລະບຸທິດທາງ ງາຍດາຍ ື່ (DAG : ມ ັນຕີກຣາຟ (Multi Graph) Directed Acyclic Graph) ກຣາຟສ ົມບູນ (Complete Graph) ົື້ ກຣາຟຕນໄມ ລະບຸ ື້ ທິດ ື່ ນ (Path Graph) ກຣາຟພາກສວ ທາ (Directed Tree Graph) ົື້ ກຣາຟຕນໄມ ື້ (Tree Graph) ກຣາຟລະບຸທິດທາງ ກຣາຟຕໍື່ ເນື່ ອງ (Connected Graph) ອື່ ນໆ (Other wish Directed Graph) ກຣາຟອອຍເລີ (Euler Graph) ກຣາຟຮາມິນຕ ັນ (Hamiltonian Graph) ກຣາຟໜາື້ ພຽງ (Plane Graph) ກຣາຟຕໍື່ ເນື່ ອງຄ ົບ (Biconnected Graph) ຮູບທີ 6.2: ສະແດງຊະນິດຂອງກຣາຟ 134 ❖ ນິຍາມ 6.2: ກຣາຟງາຍດາຍ ື່ (Simple Graph) ແມນກຣາຟທີື່ ື່ ື້ ງ ( Loop ) ແລະ 2 ຈອມໃດໜື່ ງ ບໍື່ ບວ ໃນກຣາຟຈະມີເສັື້ນເຊື່ ອມບໍື່ ເກີນ 1 ເສັ ື້ນ ຕ ົວຢາື່ ງ 6.1: ກຣາຟ G1 ,G 2 ,G 3 , G 4 , G 5 ແລະ G 6 ຕໍື່ ໄປນີແ ື້ ມນກຣາຟງ ື່ າຍດາຍ ື່ ຮູບທີ 6.3: ສະແດງເຖິງກຣາຟງາຍດາຍ ື່ ❖ ນິຍາມ 6.3: ມ ັນຕີກຣາຟ (Multi Graph)ແມນກຣາຟທີື່ ື່ ມີເສັ ື້ນເຊື່ ອມຕໍື່ ລະຫວາື່ ງສອງຈອມໃດໜື່ ງຫຼ າຍ ື້ ງ (Loop) ກໍື່ ໄດ.ື້ ກວາື່ ໜື່ ງຂາື້ ງ ຫຼ ຈອມໜື່ ງມີໜື່ ງບວ ຕ ົວຢາື່ ງ 6.2: ກຣາຟ G 1 ; G 2 ; G 3 ແລະ G 4 ໄດດ ື່ ັ ນີ:ື້ ື້ ງ ຮູບທີ 6.4: ສະແດງເຖິງມ ັນຕີກຣາຟ ❖ ນິຍ າມ 6.4 : ກຣາຟສ ມ ົ ບູນ (Complete Graph) ທີື່ ມີ n ຈອມ ສ ນ ັ ຍາລັກ ດ ວ ື້ ຍ K n ແມ ນ ື່ ກຣາຟ ງາຍດາຍ, ື່ ຊື່ ງທຸກໆສອງຈອມຕາມໃຈຈະມີເສັ ື້ນເຊື່ ອມດຽວ. ຕ ົວຢາື່ ງ 6.3: ກຣາຟ K 2 ,K 3 ,K 4 ,K 5 ຕໍື່ ໄປນີແ ື້ ມນກຣາຟສ ື່ ົມບູນ: 135  ຮູບທີ 6.5: ສະແດງເຖິງກຣາຟສ ົມບູນ ❖ ນິຍາມ 6.5: ກຣາຟພາກສວ ື່ ນ (Path Graph) ແມນກຣາຟທີື່ ື່ ສາມາດແບງື່ ຈອມອອກເປັນ 2 ຫຼ ຫຼ າຍ ກຸມ ື່ ດຽວກ ັນບໍື່ມີເສັ ື້ນເຊື່ ອມຕໍື່ ກ ັນ. ື່ ທີື່ ມີອ ົງປະກອບຕາື່ ງກ ັນ ແລະ ອ ົງປະກອບໃນກຸມ ❖ ນິຍ າມ 6.6 : ກຣາຟ G(V,E) ໄດຖ ື່ ນ (Bipertite Graph) ກໍື່ ຕໍື່ ເມື່ ອ ື້ ກເອີື້ນວ າື່ : ກຣາຟ ສອງພາກສວ ື່ ະເສັ ື້ນເຊື່ ອມ e  E ແມນ ວາື່ : P1  P2 = P ແລະ P1  P2 =  ຊື່ ງແຕລ ື່ ຕິດຈອດຈອມໜື່ ງຂອງ P1 ແລະ ອີກຈອມໜື່ ງຂອງ P2 , ແລວ ື້ ວາື່ ກຸມ ື້ P1 ແລະ P2 ໄດເື້ ອີນ ື່ ພາກສວ ື່ ນ. ື່ ົ ແຕມ ຕ ົວຢາື່ ງ 6.4: ຈງ ື່ ນທີື່ ມີ P1 = {a, b, c} ແລະ P1 = {e, f, g, h} ື້ ກຣາຟສອງຟາກສວ ວິທີແກ:ື້ ສາມາດແຕມ ື້ ກຣາຟຫຼາຍໆກຣາຟໄດດ ື່ ັ ນີ:ື້ ື້ ງ c ຫຼ ຮູບທີ 6.6: ກຣາຟສອງພາກສວ ື່ ນ ົ ບູ ນ (Complete Bipartite Graph) ທີື່ ມີ P1 = r ແລະ ❖ ນິຍ າມ 6.7: ກຣາຟສອງພາກສ ື່ວ ນສ ມ P2 = s ສ ັນຍາລັກດວ ື້ ຍ K r,s ແມນກຣາຟທີື່ ື່ ື່ ະຈອມຂອງ P1 ເຊື່ ອມກ ັບແຕລ ມີແຕລ ື່ ະຈອມຂອງ P2. ຕ ົວຢາື່ ງ 6.5: ຈງ ື່ ົ ແຕມ ື້ ກຣາຟສອງພາກສວ ື່ ນສ ົມບູນ K 2,3 ແລະ K 3,3 ວິທີແກ:ື້ ສາມາດແຕມ ື້ ກຣາຟສອງພາກສວ ື່ ນສ ົມບູນ K 2,3 ແລະ K 3,3 ໄດດ ື່ ັ ນີ:ື້ ື້ ງ ຮູບທີ 6.7: ກຣາຟສອງພາກສວ ື່ ນສ ົມບູນ 136 ❖ ນິ ຍ າມ 6.8: ກຣາຟວ ກ ັ (Cycle Graph) ທີື່ ມີ n ຈອມສ ນ ັ ຖະຈ ກ ັ ຍາລັກ ດ ື້ ວ ຍ Cn ແມ ນ ື່ ກຣາຟ ງາຍດາຍທີື່ ື່ ເປັນເສັື້ນອອ ື່ ະຈອມມີເສັ ື້ນເຊື່ ອມຈອດພຽງແຕ ື່ 2 ເສັ ື້ນເທົື່ ານນ. ື້ ມຈອດ ແລະ ແຕລ ັ ື້ ຕ ົວຢາື່ ງ 6.6: ກຣາຟ C1 , C 2 , C 3 , C 4 ແລະ C 5 ຕໍື່ ໄປນີເື້ ປັນກຣາຟວ ັກຖະຈ ັກ ຮູບທີ 6.8: ສະແດງເຖິງກຣາຟວ ັກຖະຈ ັກ ❖ ນິຍ າມ 6.9: ກຣາຟຕ ນ ົື້ ໄມ ື້ (Tree graph) ທີື່ ມີ n ຈອມສ ນ ື້ ຍ Tn , n  2 ແມ ນ ັ ຍາລັກ ດ ວ ື່ ກຣາຟ ງາຍດາຍເຊ ື່ ື່ ອມຕໍື່ ແລະ ຫຼາຍໆກຣາຟຕນໄມ ົື້ ຢູ ື້ ລ ື່ ວມກ ັນ ເອີນ ື່ ໄມ ື້ (Forest graph). ື້ ວາື່ ກຣາຟປາ ຕ ົວຢາື່ ງ 6.7: ຕໍື່ ໄປນີສ ື້ ະແດງເຖິງກຣາຟຕນໄມ ົື້ ື້ ົື້ ໄມ ື້ ຮູບທີ 6.9: ສະແດງເຖິງກຣາຟຕນ ❖ ໝາຍເຫດ: ກຣາຟຕນໄມ ົື້ ທີື່ື້ ມີ n ຈອມ ຈະມີ n − 1 ເສັ ື້ນເຊື່ ອມ. ❖ ນິຍາມ 6.10: ວ ົງຈອນ (Circuit) C ໃນກຣາຟເຊື່ ອມຕໍື່ G ຈະເອີື້ນວາື່ ວ ົງຈອນອອຍເລີ ຖາື້ ວາື່ C ບ ັນຈຸເອົ າທຸກເສັ ື້ນຂອງ G. ກຣາຟເຊື່ ອມຕໍື່ ບ ັນຈຸເອົາວ ົງຈອນອອຍເລີ ຈະເອີນ ື້ ວາື່ ກຣາຟອອຍເລີ. ຕ ົວຢາື່ ງ 6.8: ຈງ ື່ ົ ພິຈາລະນາເບິື່ ງວາື່ ກຣາຟເຊື່ ອມຕໍື່ G ແລະ H ຕໍື່ ໄປນີເື້ ປັນກຣາຟອອຍເລີ ຫຼ ບໍື່ ? ວິທີແກ:ື້ ສ ໍາລັບກຣາຟ G ມີວ ົງຈອນ C : abcdeca ເປັນວ ົງຈອນທີື່ບ ັນຈຸເອົ າທຸກໆເສັ ື້ນເຊື່ ອມຂອງ G ື່ ັ ນນ, ດງ ັື້ G ເປັນກຣາຟອອຍເລີ 137  ສ ໍາລັບກຣາຟ H ມີວ ົງຈອນ C : caecbdfc ເປັນວ ົງຈອນທີື່ບໍື່ ບ ັນຈຸເອົ າທຸກໆເສັ ື້ນເຊື່ ອມຂອງ H ື່ ັ ນນ, ດງ ັື້ H ບໍື່ ເປັນກຣາຟອອຍເລີ ໝາຍເຫດ: 1). ກຣາຟເຊື່ ອມຕໍື່ G ເປັນກຣາຟອອຍເລີ, ແລວ ື້ ຈະໄດວ ື້ າື່ G ຕອ ື້ ງມີຢາື່ ງໜອ ື້ ຍ 3 ຈອມ 2). ກຣາຟ G ຈະເປັນກຣາຟອອຍເລີກື່ ຕ ໍ ື່ ໍເມື່ ອຈານວນຂອງກຣາຟ ໍ G ເປັນຈານວນຄູ ໍ.ື່ ❖ ນິຍາມ 6.11: ວ ກ ັ ຖະຈ ັກ C ໃນກຣາຟເຊື່ ອມຕໍື່ G ຈະເອີື້ນວາື່ ວ ກ ັ (Hamiltonian ັ ຖະຈ ັກຮາມິນຕນ Cycle) ຖາື້ ວາື່ C ບນ ັ ຈຸຈອມທຸກຈອມຂອງ G. ກຣາຟເຊື່ ອມຕໍື່ ບນ ັ ຈະເອີື້ນ ັ ຈຸເອົ າວ ັກຖະຈ ັກຮາມິນຕນ ວາື່ ກຣາຟຮາມິນຕ ັນ (Hamiltonian Graph). ພິຈາລະນາເກມໄອໂຄຊຽນ (Icosian game) ຂອງທື່ານ ວິລລຽມ ໂຣແວນຮາມິນຕນ ັ (William Rowan Hamiton, ຄສ.1805-1865) ຊື່ ງເປັນເກມປິ ດສະໜາການທື່ອງທື່ຽວຮອບໂລກ, ເກມນີປ ື້ ະກອບ ດວ ື້ ນ 12 ໜື້ າ, 5 ຫຼ ື່ຽ ມ, 30 ຂອບ, 20 ມູມ ໂດຍກ ໍານ ົດຊື່ ແຕ ື່ລ ະມູມດ ວ ື້ ຍຮູບ ກ ອ ື້ ຍຊື່ ເມ ອງທີື່ ມີຊື່ ສຽງ ລະດ ັບໂລກຈານວນ ໍ 20 ເມອງ ແລະ ນ ໍາເຂັມມຸດປັກໄວຕ ື່ ັ ສະແດງໃນຮູບລຸມ ື້ າມມູມຕາື່ ງໆດງ ື່ ນີ:ື້ ື້ ນ 12 ໜາື້ ຂອງເກມໄອໂຄຊຽນ ຮູບທີ 6.10: ສະແດງເຖິງຮູບກອ ື້ : ການຫາທາງເດີນຂອງຮູບກອ ຈຸດປະສ ົງຂອງເກມນີຄ ື້ ນນີໃື້ ຫຜ ື້ າື່ ນເມອງທຸກເມອງໂດຍເດີນຜາື່ ນແຕ ື່ ັ ື້ ລະເມອງພຽງຄງດຽວ ື້ ສຸດການເດີນທີື່ ເມອງເລີື່ ມຕນ ແລະ ສິນ ົື້ ເພື່ ອໃຫຈ ື້ ື່ ໄດວ ື້ າື່ ເມອງໃດໄດເື້ ດີນຜາື່ ນໄປ ແລວ ື້ ຼິື້ນຈະໃຊເື້ ຊອກພັນອອ ື້ ຜູຫ ື້ ມຮອບເຂັມມຸດທີື່ ປັກໄວຕ ື້ າມມູມທີື່ ເດີນຜາື່ ນ. ເນື່ ອງຈາກການຫຼ ິື້ນເກມໃຊຮ ື້ ບ ື້ ນສິບສອງໜາື້ ຊື່ ງຂອ ູ ກອ ື້ ນຂາື້ ງຍາກ, ທາື່ ນ ຮາມິນຕ ັນ ຈິື່ ງໄດອ ື້ ອກ ື້ ໃືູ່ ນຮູບແຜນ ແບບເກມນີຢ ື່ ັ ຮູບທີ 6.11a ແລະ ຄ ໍາຕອບຂອງເກມນີສ ື່ ພຽງດງ ື້ ະແດງດງ ື່ ັ ຮູບ 6.11b ລຸມ ື່ ນີ:ື້ ຮູບທີ 6.11: ສະແດງເຖິງແຜນ ື່ ພຽງຂອງເກມໄອໂຄຊຽນ 138 ຕ ົວຢາື່ ງ 6.9 : ຈງ ື່ ົ ພິຈາລະນາເບິື່ ງວາື່ ກຣາຟເຊື່ ອມຕໍື່ G ແລະ H ຕໍື່ ໄປນີເື້ ປັນກຣາຟຮາມິນຕ ັນ ຫຼ ບໍື່ ? ວິທີແກ:ື້ ສ ໍາລັບກຣາຟ G ເຫັ ນວາື່ ມີຫຼາຍວ ັກຖະຈ ັກທີື່ບໍື່ ສາມາດບ ັນຈຸເອົ າຈອມທຸກຈອມຂອງກຣາຟ G ໄດ ື້ ເຊັື່ ນ: ວ ັກຖະຈ ັກ C : abcehgda ບໍື່ ສາມາດບ ັນຈຸເອົ າຈອມ f ຂອງກຣາຟ G ໄດ ື້ ື່ ັ ນນ, ດງ ັື້ C ບໍື່ ເປັນວ ັກຖະຈ ັກຮາມິນ. ັື້ ກຣາຟເຊື່ ອມຕໍື່ G ບໍື່ ເປັນກຣາຟຮາມິນ. ສະນນ, ສ ໍາລັບກຣາຟ H ເຫັ ນວາື່ ມາດຊອກໄດວ ື້ ັກຖະຈ ັກ C : aceghifdba ທີື່ ບ ັນຈຸເອົາຈອມທຸກຈອມຂອງ ກຣາຟ H ື່ ັ ນນ, ດງ ັື້ C ເປັນວ ັກຖະຈ ັກຮາມິນຕ ັນ ັື້ ກຣາຟເຊື່ ອມຕໍື່ H ເປັນກຣາຟຮາມິນຕ ັນ ສະນນ, ໝາຍເຫດ: ກຣາຟເຊື່ ອມຕໍື່ G ເປັນກຣາຟຮາມິນຕ ັນ, ແລວ ື້ ຈະໄດວ ື້ າື່ G ຕອ ື້ ງມີຢາື່ ງໜອ ື້ ຍ 3 ຈອມ ❖ ນິຍາມ 6.12: ກຣາຟລະບຸທິດທາງ D (Directed Graph) ແມນກຣາຟທີື່ ື່ ມີລກ ື້ ອກທິດ, ຊື່ ງ ູ ສອນຊີບ ປະກອບດວ ື້ ຍກຸມ ື່ ເສັ ື້ນເຊື່ ອມ E(D) ເປັນຄູອ ື່ ຈອມ V(D) ແລະ ກຸມ ື່ ັນດ ັບທີື່ສາມາດນ ັບໄດ ື້ ແລະ ເສັ ື້ນ ເຊື່ ອມລະຫວາື່ ງຈອມທາື້ ຍ 2 ຈອມ ເອີນ ື້ ວາື່ ເສັ ື້ນລະບຸທິດທາງ. ົ ຢື່າງ 6.10 : ຈື່ງົ ພິ ຈາລະນາເບິື່ ງວ າື່ ການສະແດງຂໍື້ມນ ຕວ ູ ເຄອຂາື່ ຍຄອມພິວ ເຕີ ຂະໜາດນອ ື້ ຍໃນກຣາຟ D ທີື່ ມີເສັື້ນລູກສອນຊີທ ື້ ິດຕໍື່ ໄປນີື້ ເປັນກຣາຟລະບຸທິດທາງ ຫຼ ບໍື່ ? 139 ວິທີແກ:ື້ ື່ ຂອງຈອມ V(D) = x, u, v, y ເຫັ ນວາື່ ກຸມ ື່ ຂອງເສັື້ນເຊື່ ອມ E(D) = (x, u); (u, v); (v, u); (u, y) ເປັນຄູອ ແລະ ກຸມ ື່ ັນດ ັບທີື່ສາມາດນ ັບໄດ ື້ ໂດຍມີເສັ ື້ນເຊື່ ອມລະຫວາື່ ງຈອມທາື້ ຍ 2 ຈອມ x − y ເປັນເສັ ື້ນລະບຸທິດທາງ. ັື້ ກຣາຟ D ເປັນກຣາຟລະບຸທິດທາງ ສະນນ, ❖ນິຍ າມ 6.13: ກຣາຟລະບຸ ທິ ດ ທາງ D ທີື່ ມີກ ານກ ໍານ ດ ື່ ຈ ໍານວນຈິງ ເທິ ງ ເສັ ື້ ນ ເຊື່ ອມ e = (u, v) ົ ຄາ ທຸກໆເສັື້ນ, ແລວ ື້ ວາື່ ກຣາຟລະບຸທິດທາງຖວ ື້ D ຈະເອີນ ໍື້ ກ (Direct weighted graphs). ື່ ງນາໜັ ົ ຢື່າ ງ 6.11 : ຈື່ງົ ກວດເບິື່ ງວ າື່ ກຣາຟຖ ວ ຕວ ໍື້ ກ D = (V, E) ທີື່ ກ ໍານ ົດໃຫື້ດື່ງັ ຕໍື່ ໄປນີື້ ເປັ ນກຣາຟ ື່ ງນ າໜັ ລະບຸທິດທາງຖວ ໍື້ ກ ຫຼ ບໍື່ ? ື່ ງນາໜັ 2 ວິທີແກ:ື້ ື່ ຂອງຈອມ V(D) = a, b, c, d, e, f, g ແລະ ກຸມ ເຫັ ນວາື່ ກຸມ ື່ ຂອງເສັ ື້ນເຊື່ ອມ E(D) = (a, b); (a, c);(b, d); (c,a); (c, b); (c, f); (d, c); (e,a); (f,g); (f,e);(g, d); (g, e)ເປັນຄູື່ ອ ັນດ ັບທີື່ສາມາດນ ັບໄດ.ື້ ັື້ ກຣາຟ D ເປັນກຣາຟລະບຸທິດທາງຖວ ສະນນ, ໍື້ ກ. ື່ ງນາໜັ ❖ນິຍາມ 6.14: ກຣາຟໃດໆທີື່ ສາມາດແຕມ ື່ ທັບກ ັນ (ບໍື່ ຕດ ື້ ຢູື່ໜາື້ ພຽງ ໂດຍບໍື່ ມີເສັ ື້ນໄຂວ ັ ກ ັນ ຫຼ ບໍື່ ສ ໍາພັດ ື້ ວາື່ ກຣາຟໜາື້ ພຽງ ຫຼ ເອີນ ກ ັນ) ເອີນ ື້ ວາື່ ກຣາຟເທິງໜາື້ ພຽງ (Plane graph) ກໍື່ ໄດ.ື້ ື່ ົ ພິຈາລະນາເບິື່ ງວາື່ ກຣາຟ G ແລະ H ຕໍື່ ໄປນີເື້ ປັນກຣາຟເທິງໜາື້ ພຽງ ຫຼ ບໍື່ ? ຕ ົວຢາື່ ງ 6.12: ຈງ a b c d e f H 140 ວິທີແກ:ື້ ສ ໍາລັບກຣາຟ G ສາມາດແຕມ ື້ ໃໝໄ ື່ ດດ ື່ ັ ນີ:ື້ ື້ ງ f ຫຼ f e d e c ຮູບ (a) ຮູບ (b) ເຫັ ນວາື່ G ສາມາດແຕມ ື່ າື້ ພຽງທີື່ ບໍື່ ມີເສັ ື້ນໄຂວ ື້ ຢູໜ ື່ ທັບກ ັນໄດ ື້ ື່ ັ ນນ, ດງ ັື້ G ເປັນກຣາຟເທິງໜາື້ ພຽງ ສ ໍາລັບກຣາຟ H ແນະນ ໍາໃຫນ ື້ ັກສກສາແກ ື້ ຫຼ ເຮັດວຽກບາື້ ນ ໝາຍເຫດ: 1). ກຣາຟເຊື່ ອມຕໍື່ ທີື່ ເປັນກຣາຟໜາື້ ພຽງ ເອີນ ື້ ວາື່ ກຣາຟໜາື້ ພຽງເຊື່ ອມຕໍື່ 2). ກຣາຟເຊື່ ອມຕໍື່ ທີື່ ເປັນກຣາຟເທິງໜາື້ ພຽງ ເອີນ ື້ ວາື່ ກຣາຟເທິງໜາື້ ພຽງເຊື່ ອມຕໍື່ ❖ ນິຍາມ 6.15: ກຣາຟຕື່ ມເຕັ ມ (Complement graph) ຂອງກຣາຟ G ສ ັນຍາລັກດວ ື້ ຍ G ຄກຣາຟ ທີື່ ມີກມ ຸື່ ຂອງຈອມເທົື່ າ V(G) ແລະ ສ ໍາລັບແຕລ ື່ ະຈອມ u ແລະ v ໃນ V(G) ຈະໄດວ ື້ າື່ : uv ເປັນເສັ ື້ນໃນກຣາຟຕື່ ມເຕັ ມ G ກໍື່ ຕື່ ໍເມື່ ອ uv ບໍື່ ເປັນເສັ ື້ນເຊື່ ອມໃນກຣາຟ G ຕ ົວຢາື່ ງ 6.13: ື່ ົ ແຕມ ຈງ ື້ ກຣາຟຕື່ ມເຕັ ມຂອງກຣາຟ G ແລະ H ຕໍື່ ໄປນີ:ື້ ວິທີແກ:ື້ ເຮົາໄດ,ື້ 141  ັື້ ແລະ ຂະໜາດຂອງກຣາຟ 6.3 ລ ໍາດ ັບຂນ ❖ ນິຍ າມ 6.16: ລ ໍາດ ບ ັ ື້ (Order) ຂອງກຣາຟ G ແມ ນ ັ ຂນ ື່ ຈ ໍານວນຈອມຂອງ G ສ ນ ັ ຍາລັກ ດ ວ ື້ ຍ p = V(G) ແລະ ຂະໜາດ (size) ຂອງ G ຈານວນຂ ໍ ື້ ຍ q = E(G). າື້ ງຂອງ G ສ ັນຍາລັກດວ ຕ ົວຢາື່ ງ 6.14: ື່ ົ ບອກລ ໍາດ ັບຂນ ຈງ ັ ື້ ແລະ ຂະໜາດ ຂອງກຣາຟຕໍື່ ໄປນີ:ື້ ວິທີແກ:ື້ ສ ໍາາລັບ G ມີ 3 ຈອມ 3 ຂາື້ ງ ເຮົາໄດ ື້ V(G ) = 3 ແລະ E(G) = 3 ສ ໍາາລັບ H ມີ 4 ຈອມ 4 ຂາື້ ງ ເຮົາໄດ ື້ V(H ) = 4 ແລະ E(H) = 4 ສ ໍາາລັບ I ມີ 6 ຈອມ 11 ຂາື້ ງ ເຮົາໄດ ື້ V(I) = 6 ແລະ E(I) = 11 ໝາຍເຫດ: ຖາື້ ວາື່ G ເປັນກຣາຟສ ົມບູນ ທີື່ ມີ n ຈອມ, ຊື່ ງ n  2 ຈະມີລ ໍາດບ ັ ື້ p = V(G ) = n ັ ຂນ ຈອມ ແລະ ຂະໜາດ q = E(G) = C 2n ຂາື້ ງ. ເຊັື່ ນ: K 5 ເຮົາມີ: V(K5 ) = 5 ຈອມ ແລະ E(K 5 ) = C62 = 10 ຂາື້ ງ ຮູບທີ 6.12: ກຣາຟສ ົມບູນທີື່ ມີ 5 ຈອມ ແລະ 10 ຂາື້ ງ ❖ ນິຍາມ 6.17: ດີກຣີ (Degree) ຂອງຈອມ v ໃນກຣາຟ G ສນ ັ ຍາລັກດວ ື້ ຍ deg(v) ແມນ ື່ ຈ ໍານວນ ເສັື້ນເຊື່ ອມທີື່ ເຊື່ ອມຈອມ v ແລະ ຈອມ v ຈະເອີນ ື້ ວາື່ : ຈອມຄູື່ (Even vertex) ຖາື້ ວາື່ deg( v) ເປັນຈານວນຄູ ໍ ື່ ຈອມຄີກ (Odd vertex) ຖາື້ ວາື່ deg( v) ເປັນຈານວນຄີ ໍ ກ ຈອມໂດດດຽື່ ວ (Isolate vertex) ຖາື້ ວາື່ deg( v) = 0 ຈອມປາຍ (End vertex) ຖາື້ ວາື່ deg( v) = 1 ❖ ນິຍາມ 6.18: ດີກຣີນອ ື້ ຍ δ(G) ຄດີກຣີທື່ ີຕາື່ ໍ ື້ ຍສຸດ (Minimum Degree) ຂອງກຣາຟ G ສ ັນຍາລັກດວ ສຸດຂອງຈອມເມື່ ອປຽບທຽບກ ັບຂນຂອງຈອມທຸ ັ ື້ ກຈອມໃນກຣາຟ G ຄ: δ(G) = mindeg( v) / v  V(G) 142  ື່ ຸດ (Maximum degree) ຂອງກຣາຟ G ສ ນ ແລະ ດີກຣີໃຫຍ ສ ື້ ຍ  (G) ຄດີກ ຣີທື່ ີ ໃຫຍ ທ ັ ຍາລັກດວ ື່ ື່ ີ ສຸດຂອງຈອມເມື່ ອປຽບທຽບກ ັບຂນຂອງຈອມທຸ ັ ື້ ກຈອມໃນກຣາຟ G ຄ: (G) = Maxdeg( v) / v  V(G) ຕ ົວຢາື່ ງ 6.15: ຈງ ື່ ົ ບອກດີກຣີ, ຈອມຄູ,ື່ ຈອມຄີກ, ດີກຣີໃຫຍສ ື່ ດ ື້ ຍສຸດຂອງກຣາຟຕໍື່ ໄປນີ:ື້ ຸ ແລະ ນອ ວິທີແກ:ື້  ສ ໍາລັບກຣາຟ G1 ເຮົາມີ: deg(a) = 4, deg(c) = 2, deg(d) = 2 ແລະ deg(f) = 4 ຈະໄດຈ ື້ ອມ a, c, d, f ເປັນຈອມຄູື່ deg(b) = 3 ແລະ deg(e) = 3 ຈະໄດຈ ື້ ອມ b, e ເປັນຈອມຄີກ ດີກຣີຕາື່ ໍ ສຸດຂອງກຣາຟ G1 ແມນຈອມ ື່ c, d ໂດຍມີ δ(G) = 2 ດີກຣີໃຫຍສ ື່ ດ ຸ ຂອງກຣາຟ G1 ແມນຈອມ ື່ a, f ໂດຍມີ (G) = 4  ສ ໍາລັບກຣາຟ G 2 ເຮົາມີ: deg(a) = 4 ແລະ deg(c) = 2 , ຈະໄດຈ ື້ ອມ a, c ເປັນຈອມຄູື່ deg(b) = 3 ແລະ deg(d) = 5 , ຈະໄດຈ ື້ ອມ b, d ເປັນຈອມຄີກ ດີກຣີຕາື່ ໍ ສຸດຂອງກຣາຟ G 2 ແມນຈອມ ື່ c ໂດຍມີ δ(G) = 2 ດີກຣີໃຫຍສ ື່ ດ ຸ ຂອງກຣາຟ G 2 ແມນຈອມ ື່ d ຈະໄດ ື້ (G) = 5  ສ ໍາລັບກຣາຟ G 3 ແນະນ ໍາໃຫນ ື້ ັກສກສາແກ ື້ ຫຼ ເປັນວຽກບາື້ ນ. ັ ື້ ໝາຍເຫດ: ຖາື້ ວາື່ ກຣາຟ G ເປັນກຣາຟງາື່ ຍດາຍທີື່ ມີລ ໍາດ ັບຂນເທົື່ າ n ແລະ v ເປັນຈອມຂອງກຣາຟ G, ເວລານນັື້ 0  δ(G)  deg(v)  (G)  n − 1. ັ ເກນ 1.1: ຖາື້ ວາື່ ກຣາຟ G ມີ V(G) = p; E(G) = q ແລະ V(G) = v1 ,v2......vp  ເວລານນັ ື້ ❖ ຫຼ ກ p  deg(v ) = 2 E(G) = 2q i =1 i ພິສດ ູ : ເນື່ ອງຈາກວາື່ ການນ ັບດີກຣີຂອງຈອມ ກຣາຟ G ລວມທັງໝດ ົ ນນັ ື້ ແຕລ ື່ ະເສັື້ນເຊື່ ອມຈະຖກນ ັບສອງ ຄງັື້ ແລະ ແຕລ ື້ ຍຈອມ 2 ຈອມເຊື່ ອມເຂົື້າກ ັນ. ື່ ະເສັ ື້ນເຊື່ ອມປະກອບດວ p ື່ ັ ນນ, ດງ ັື້  deg(V ) = 2q i =1 i 143 ຕ ົວຢາື່ ງ 6.16: ຈງ ງໝ ົດຂອງກຣຟ G ທີື່ ມີເສັື້ນເຊື່ ອມ 20 ເສັ ື້ນ, ມີ 4 ຈອມທີື່ ມີ ື່ ົ ຊອກຫາຈານວນຈອມທັ ໍ ດີກຣີເທົື່ າ 3 ແລະ ສວ ື່ ນທີື່ ເຫຼ ອມີມດ ີ ຣີເທົື່ າ 4 ີ ກ ວິທີແກ:ື້ ໃຫື້ vi : ີ ຣີເທົື່ າ 3, ຊື່ ງວາື່ deg(vi ) = 3, i = 1, 2, 3, 4 ເປັນຈອມຂອງກຣາຟທີື່ ມີດກ n : ເປັນຈານວນຈອມຂອງກຣາຟທີື່ ໍ ີ ຣີເທົື່ າ 4. ມີດກ ັ ເກນ 1 ຈະໄດ ື້ ອີງຕາມຫຼ ກ p  deg(v ) = 2q , i =1 i ຊື່ ງ q ແມນເສັ ື່ ື້ນເຊື່ ອມຂອງກຣາຟ G deg(v1 ) + deg(v2 ) +... + deg(vn ) = 2q 3 + 3 + 3 + 3+4 + 4 +... + 4 = 2  20 n 12 + 4n = 40 4n = 28 → n = 7 ັື້ ຈານວນຈອມທັ ສະນນ, ໍ ື່ 7 + 4 = 11 ຈອມ. ງໝ ົດຂອງກຣາຟ G ແມນ: ❖ ຫຼ ກ ັ ເກນ 6.2: ທຸກໆກຣາຟຈະມີຈານວນຈອມຄີ ໍ ກ ເປັນຈານວນຄູ ໍ ຈ ື່ ອມ. ພິສດ ູ : ໃຫື້ G ເປັນກຣາຟທີື່ ມີຂະໜາດ q , v ເປັນຈອມຂອງກຣາຟ G, Ve ເປັນກຸມ ື່ ຂອງບນ ັ ດາຈອມຄູື່ ແລະ V0 ເປັນກຸມ ັ ເກນ 1 ຈະໄດ ື້ ື່ ຂອງບ ັນດາຈອມຄີກ. ອີງຕາມຫຼ ກ  deg(v) = 2q vV(G) ແລະ  deg(v) +  deg(v) = 2q vV0 vVe ື່ ັ ນນ, ດງ ັ ື້  deg(v) = 2q −  deg(v) vVe vV0 ເນື່ ອງຈາກວາື່  deg(v) ເປັນຈານວນຄູ vVe ໍ.ື່ ື່ ັ ນນ, ດງ ັ ື້  deg(v) ເປັນຈານວນຄູ vV0 ໍ ,ື່ ທີື່ ເຮັດໃຫື້ V0 ເປັນຈານວນຄູ ໍ.ື່ 6.4 ອະນຸກຣາຟ (Subgraph) ❖ນິຍາມ 6.19: ກ ໍານ ົດໃຫື້ G ແລະ H ເປັນກຣາຟ, H ຈະເປັນອະນຸກຣາຟຂອງກຣາຟ G ກໍື່ ຕື່ ໍ ເມື່ ອ ວາື່ : V(H)  V(G) ແລະ E(H)  E(G). ❖ນິຍາມ 6.20: ກ ໍານ ົດໃຫື້ G, H ເປັນກຣາຟ ແລະ ຖາື້ ວາື່ H ເປັນອະນຸກຣາຟຂອງກຣາຟ G, ແລວ ື້ ື້ ວາື່ ອະນຸກຣາຟແທື້ (Properm Subgrap) ຂອງ G ກໍື່ ຕື່ ໍ ເມື່ ອ V(H) ເປັນອະນຸກຣາຟແທື້ຂອງ H ຈະເອີນ ື້ ຍ H  G V(G) ແລະ V(H) ບໍື່ ເທົື່ າກ ັບ V(G) ຊື່ ງສ ັນຍາລັກດວ 144 ❖ນິຍາມ 6.21: ກ ໍານ ົດໃຫື້ G, H ເປັນກຣາຟ ແລະ ຖາື້ ວາື່ H ເປັນອະນຸກຣາຟຂອງກຣາຟ G, ແລວ ື້ ື່ ອະນຸກ ຣາຟແບບປົກ ຄຸມ (Spanning Subgraph) ຂອງ G ກໍື່ ຕໍື່ ເມື່ ອ V(H) ເປັ ນ ອະ H ຈະເອີື້ ນ ວ າ ື້ ຍ H  G ນຸກຣາຟຂອງ V(G) ແລະ V(H) = V(G) ຊື່ ງສ ັນຍາລັກດວ ❖ນິຍາມ 6.22: ກ ໍານ ົດໃຫື້ G, H ເປັນກຣາຟ ແລະ ຖາື້ ວາື່ H ເປັນອະນຸກຣາຟຂອງກຣາຟ G, ແລວ ື້ ື່ ອະນຸກຣາຟແບບກໍື່ ກ ໍາເນີດ (Induced subgraph) ຂອງ G ກໍື່ ຕໍື່ ເມື່ ອ V(H) ເປັນອະ H ຈະເອີື້ນວ າ ນຸກຣາຟຂອງ V(G) ແລະ ສ ໍາລັບແຕລ ື່ ະຈຸດຈອມ u ແລະ v ໃນກຣາຟ H ຖາື້ ວ າື່ ຈຸດຈອມ u ເຊື່ ອມຈອດກ ັບຈຸດຈອມ v ໃນກຣາຟ G ແລວ ື້ ງເຊື່ ອມຈອດກ ັບ v ໃນກຣາຟ H. ື້ u ຕອ ຕ ົວຢາື່ ງ 6.17: ຈງ ື່ ົ ກວດເບິື່ ງວາື່ ກຣາຟ G1 , G 2 ແລະ G 3 ເປັນອະນຸກຣາຟແບບໃດຂອງກຣາຟ G ຕໍື່ ໄປນີ:ື້ ວິທີແກ:ື້ ເຮົາມີ: V(G) = a, b, c, d, e, f  ແລະ E(G) = ac, ae, ad, bd, be, bf , cf , ce, df  ສ ໍາລັບກຣາຟ G1 ເຮົາມີ: V(G 1 ) = a, c, e  V(G) ແລະ E(G1 ) = ac, ae, ce  E(G) ື່ ັ ນນ, ດງ ັື້ G1 ເປັນອະນຸກຣາຟແທຂ ື້ ອງກຣາຟ G ື້ ນວາື່ 2 ຈອມໃດໆໃນ V(G 1 ) = a, c, e ທີື່ ຕິດຈອດກ ັນໃນກຣາຟ G ແລວ ແລະ ຍອ ື້ ຈະເຫັ ນວາື່ 2 ັ ື້ ດຈອດກ ັນໃນກຣາຟ G1 ດງ ຈອມນນຕິ ື່ ັ ສະແດງໃນຮູບ ັ ື້ G1 ເປັນອະນຸກຣາຟແບບກໍື່ ກ ໍາເນີດຂອງກຣາຟ G ສະນນ, ສ ໍາລັບກຣາຟ G 2 ເຮົາມີ: V(G 2 ) = b, c, e, f   V(G) ແລະ E(G 2 ) = be, bf, cf , ce  E(G) ື່ ັ ນນ, ດງ ັື້ G 2 ເປັນອະນຸກຣາຟແທຂ ື້ ອງກຣາຟ G ື້ ນວາື່ 2 ຈອມໃດໆໃນ V(G 2 ) = b, c, e, f  ທີື່ ຕິດຈອດກ ັນໃນກຣາຟ G ແລວ ແລະ ຍອ ື້ ຈະເຫັ ນວາື່ 2 ັ ື້ ດຈອດກ ັນໃນກຣາຟ G 2 ດງ ຈອມນນຕິ ື່ ັ ສະແດງໃນຮູບ 145  ັ ື້ G 2 ເປັນອະນຸກຣາຟແບບກໍື່ ກ ໍາເນີດຂອງກຣາຟ G ສະນນ, ສ ໍາລັບກຣາຟ G 3 ເຮົາມີ: V(G 3 ) = a, b, c, d, e, f  = V(G) ແລະ E(G 3 ) = ac, ae, bd , bf, ce, df   E(G) ດງ ື່ ັ ຮູບ ັ ື້ G 3 ເປັນອະນຸກຣາຟແບບປົກຄຸມຂອງກຣາຟ G ສະນນ, 6.5 ກຣາຟຖອດແບບ (Graph Isomorphism) ກຣາຟ G ເທົື່ າກ ັບກຣາຟ H ກໍື່ ຕໍື່ ເມື່ ອ V(G) = V(H) ແລະ E(G) = E(H) ໃນທາງກ ົງກ ັນຂາື້ ມ ຖາື້ ວາື່ ກຣາຟ G ບໍື່ ເທົື່ າກ ັບກຣາຟ H ແຕວ ື່ າື່ ມີໂຄງສາື້ ງເປັນອນ ື້ G ຈະເອີື້ນວາື່ ຖອດ ັ ດຽວກ ັນ ແລວ ແບບ ຫຼ ໄອໂຊມອກຟິ ໋ ື່ ັ ສະແດງໃນຮູບລຸມ ສມ ກ ັບ ກຣາຟ H. ເຊັື່ ນ: ໃຫື້ H1 , H 2 ແລະ H 3 ດງ ື່ ນີ:ື້ ຖາື້ ວາື່ ແຕມ ື້ ກຣາຟ H 2 ແລະ H 3 ໃໝຕ ື່ າມຮູບຂາື້ ງເທິງ ຈະພົບວາື່ ກຣາຟ H1 , H 2 ແລະ H 3 ແຕກ ຕາື່ ງກ ັນພຽງຊື່ ຂອງຈອມດງ ື່ ັ ນີ:ື້ H1 H3 H2 146  ື້ ຮູບ ແລະ ຊື່ ຂອງຈອມ. ດງ ເຫັ ນວາື່ ກຣາຟທັງສາມມີໂຄງສາື້ ງອ ັນດຽວກ ັນຕາື່ ງພຽງການແຕມ ື່ ັ ນນ, ັ ື້ ື່ ະ i, j ໂດຍທີ 1  i, j  3 ແລະ ຈະໄດວ ແຕລ ື້ າື່ ກຣາຟ H i ຖອດແບບກ ັບກຣາຟ H j ❖ ນິຍາມ 6.23: ກຣາຟ G ແລະ H ເປັນກຣາຟຖອດແບບກ ັນ ຫຼ ໄອໂຊມອກຟິ ໋ ສມກ ັນ ສ ັນຍາລັກ ື້ ຍ G  H ແລະ G  H ຖາື້ ວາື່ ມີຕ ໍາລາ f : V(G) → V(H) ເປັນຕ ໍາລາໜື່ ງຕໍື່ ໜື່ ງ ແລະ ທົື່ ວ ດວ ເຖິງໂດຍທີື່ : uv  E(G) ກໍື່ ຕື່ ໍເມື່ ອ f(u)f(v)  E(H) ສ ໍາລັບທຸກໆຈອມ u ແລະ v ໃນກຣາຟ G ຕ ໍາລາ f : V(G) → V(H) ເອີື້ນວາື່ ຕ ໍາລາຖອດ ແບບ (Isomorphism Fucntion) ຈາກ G ໄປຫາ H ໝາຍເຫດ: ື້ ຍ G  H ກໍລະນີກຣາຟ G ບໍື່ ຖອດແບບກ ັບກຣາຟ H ສ ັນຍາລັກດວ ການສະແດງວາື່ ກຣາຟ G ຖອດແບບກ ັບກຣາຟ H ສາມາດເຮັດໄດ ື້ 2 ວິທີຄ: ວິທີທື່ ີໜື່ ງເປັນວິທີທື່ ີ ບໍື່ ເປັນທາງການ ໂດຍແຕມ ື້ ຮູບກຣາຟ G ແລະ H ໃຫມ ື່ ນວິທີທື່ ີສອງເປັນວິທີທື່ ີ ເປັ ນ ື້ ໂີ ຄງສາື້ ງທີື່ ຄກ ັນ, ສວ ທາງການຄ: ສະແດງ ຕ ໍາລາໄອໂຊມອກຟິ ໋ ສມ f ຈາກກຸມ ື່ V(G) ຫາ V ( H) ຕ ົວຢາື່ ງ 6.18: ຈງ ື່ ົ ສະແດງວາື່ ກຣາຟ G ຖອດແບບກ ັບກຣາຟ H ລຸມ ື້ ດຍໃຊນ ື່ ນີໂ ື້ ຍ ິ າມກາານຖອດແບບ ວິທີແກ:ື້ ຖາື້ ວາື່ ໃຫກ ື້ ຣາຟ G ຍ ັງຄເກົື່ າ ແລະ ແຕມ ື້ ກຣາຟ H ໃໝຈ ື່ ັ ນີ:ື້ ື່ ະເປັນດງ ເຫັ ນວາື່ ໂຄງສາື້ ງຂອງກຣາຟ H ຄກ ັນກ ັບກຣາຟ G ຊື່ ງເປັນການຢນຢັນວາື່ G ຖອດແບບກ ັບກຣາຟ H ແລະ ເນື່ ອງຈາກວາື່ G ແລະ H ເປັນກຣາຟບໍື່ ກ ໍານ ົດຊື່ ຈອມ. ດງ ື່ ັ ນນ, ັ ື້ ຕອ ື້ ງກ ໍາກ ໍານ ົດຊື່ ຈອມໃຫກ ື້ ຣາຟທັງ ສອງຄ: 147  ົ ໃຫື້ ຕ າໍ ລາ f : V(G) → V(H) ເປັ ນ ຕ າໍ ລາໜື່ ງຕໍື່ ໜື່ ງ ແລະ ທົື່ ວເຖິ ງ ຊື່ ງນິ ຍ າມໂດຍ ກ ໍານ ດ f(u1 ) = u 2 , f(v1 ) = w 2 , f(w1 ) = y 2 , f(x1 ) = v 2 ແລະ f(y1 ) = x 2 ຈະໄດ ື້ u1v1  E(G) ແລະ f(u1 )f(v1 ) = u 2 w 2  E(H) v1w1  E(G) ແລະ f(v1 )f(w1 ) = w 2 y 2  E(H) w1x1  E(G) ແລະ f(w1 )f(x1 ) = y 2 v 2  E(H) x1y1  E(G) ແລະ f(x1 )f(y1 ) = v 2 x 2  E(H) y1u1  E(G) ແລະ f(y1 )f(u1 ) = x 2 u 2  E(H) ື່ ະ uv  E(G) ເຮົາໄດ ື້ f(u)f(v)  E(H) ເຫັ ນວາື່ ສ ໍາລັບແຕລ ແລະ f ເປັນຕ ໍາລາໜື່ ງຕໍື່ ໜື່ ງ ແລະ ທົື່ ວເຖິງ ັື້ ກຣາຟ G ຖອດແບບກ ັບກຣາຟ H ສະນນ, ໝາຍເຫດ: ື້ V(G) = V(H) ແລະ E(G) = E(H) 1). ຖາື້ ວາື່ ກຣາຟ G ຖອດແບບກ ັບກຣາຟ H ແລວ 2). ຖາື້ ວາື່ V(G)  V(H) ຫຼ E(G)  E(H) ແລວ ື້ G ບໍື່ ໄອໂຊມອກມ ໋ ອກຟິ ໋ ສມກ ັບ H ຕ ົວຢາື່ ງ 6.19: ຈງ ື່ ົ ສະແດງວາື່ ວາື່ ກຣາຟ G ບໍື່ ຖອດແບບກ ັບກຣາຟ H ລຸມ ື່ ນີ:ື້ ວິທີແກ:ື້ ເນື່ ອງຈາກ E(G) = E(H) = 8 ແຕວ ື່ າື່ V(G) = 7 ແລະ V(H) = 6 ຊື່ ງເຫັ ນວາື່ E(G)  E(H) ື່ ັ ນນ, ດງ ັ ື້ ກຣາຟ G ບໍື່ ຖອດແບບກ ັບກຣາຟ H 6.6 ື້ ິດສະດີກຣາຟ (Application of Graph Theory) ການນ ໍາໃຊທ 6.6.1 ການນ ໍາໃຊກ ົື້ ື້ ຣາຟຕນໄມ ແຜ ື່ ື່ ວ ື້ ທ ົ ຕາື່ ໍ ສຸດ ົື້ ໄມ ແ ການຊອກຫາກຣາຟຕ ນ ື້ ຜື່ ທື່ ວຕ ົ າື່ ໍ ສຸດ ໂດຍທົື່ ວໄປເພິື່ ນນິຍ ມ ັ ື້ ົ ໃຊ ື້ຂ ນຕອນວິ ທີ ຂ ອງກຣູກໍ ລ (Kruskal’s algorithm) ຫຼ ຂນຕອນວິ ັ ື້ ທີຂອງພຣີມ (Prim’s algorithm). ໃນນີຈ ື້ ະສະເໜີແຕຂ ັ ື້ ື່ ນຕອນວິ ທີ ຂອງພຣີມຄ: ົື້ ໃຫື້ T ເປັນກຣາຟຕນໄມ ປົ ື້ ກຄຸມຂອງກຣາຟຖວ ໍື້ ກເຊື່ ອມຕໍື່ G ຊື່ ງວາື່ V(T) = V(G) ແລະ ື່ ງນາໜັ ັ ື້ ມີຂນຕອນດງື່ ັ ນີ:ື້ 148 (1). ຂນຕອນທີ ັື້ 1: ເລອກຈອມໜື່ ງຕາມໃຈທີື່ ມີນາໜັ ໍື້ ກຂອງເສັ ື້ນໜອ ື້ ຍສຸດຂອງກຣາຟ T ສ ົມມຸດວາື່ ຈອມ u (2). ຂນຕອນທີ ັື້ 2: ເລອກເສັື້ນ e1 ທີື່ ມີນາໜັ ໍື້ ກໜອ ື້ ຍສຸດທີື່ ກະທົບຈອມ u ຂອງກຣາຟ T ເປັນເສັ ື້ນທ ໍາອິດ (3). ຂນຕອນທີ ັື້ 3: ເລອກເສັື້ນ e 2 ທີື່ ມີນາໜັ ໍື້ ກໜອ ື້ ຍສຸດຖ ັດຕໍື່ ຈາກ e1 ຂອງກຣາຟ T ເປັນເສັ ື້ນທີ 2 (4). ຂນຕອນທີ ັື້ 4: ເລອກເສັື້ນ e 3 ທີື່ ມີນາໜັ ື້ ຍສຸດຖ ັດຕໍື່ ຈາກ e 2 ຂອງກຣາຟ T ເປັນເສັ ື້ນທີ 3 ໍື້ ກໜອ ໂດຍບໍື່ ໃຫເື້ ກີດວ ັກຖະຈ ັກໃນກຣາຟ T (5). ຂນຕອນທີ ັື້ 5: ເລອກເສັື້ນ e 4 ທີື່ ມີນາໜັ ື້ ຍສຸດຖ ັດຕໍື່ ຈາກ e 3 ຂອງກຣາຟ T ເປັນເສັ ື້ນທີ 4 ໍື້ ກໜອ ໂດຍບໍື່ ໃຫເື້ ກີດວ ັກຖະຈ ັກໃນກຣາຟ T ແລະ ດ ໍາເນີນໄປເລື້ອຍໆຈ ົນຈອມທຸກຈອມ ື້ ຍ 1 ເສັ ື້ນທີື່ ເລອກມາກອ ຂອງກຣາຟ T ກະທົບເສັ ື້ນຢື່າງໜອ ັ ື້ ື່ ນນນ. ັ ື້ ຈາກຂນຕອນນີ ຈ ື້ ະໄດວ ົື້ ື້ າື່ T ເປັນກຣາຟຕນໄມ ື້ ກຄຸມຕາື່ ໍ ສຸດຂອງກຣາຟຖວ ປົ ໍື້ ກເຊື່ ອມຕໍື່ G ື່ ງນາໜັ ຕ ົວຢື່າງ 6.20: ຈື່ງົ ຊອຫາກຣາຟຕນ ົື້ ໄມແ ື້ ຜື່ທື່ ວ ົ ຕາື່ ໍ ສຸດ ຂອງກຣາຟຖວ ໍື້ ກເຊື່ ອມຕໍື່ ຕໍື່ ໄປນີື້ ໂດຍໃຊຂ ື່ ງນາໜັ ັ ື້ ື້ ນ ຕອນວິທີຂອງພຣີມ (Prim’s algorithm) ? ວິທີແກ:ື້ ໃຫື້ T ເປັນກຣາຟ ຊື່ ງວາື່ V(T) = V(G) ແລະ ທ ໍາການເລອກຈອມອາດຈະເລອກຈອມ a, b, d ຫຼ e ື້ ເລອກເສັ ື້ນ ab, bd, de ແລະ ເສັ ື້ນ 2 ຕາມລ ໍາດ ັບດງ ຖາື້ ວາື່ ເລອກຈອມ b ແລວ ື່ ັ ນີ:ື້ ເລືອກຈອມ ື່ ັ ນນ, ດງ ັ ື້ ກຣາຟຕນໄມ ົື້ ື້ ກຄຸມຕາື່ ໍ ສຸດຂອງກຣາຟຖວ ປົ ໍື້ ກເຊື່ ອມຕໍື່ G ແມນ ື່ ງນາໜັ ື່ ຮູບສຸດທື້າຍຂອງກໍລະນີທີ 1 ແລະ 2, ຊື່ ງກຣາຟ T ເປັນກຣາຟຕນໄມ ົື້ ື້ ກຄຸມຕາື່ ໍ ສຸດຂອງກຣາຟຖວ ປົ ໍື້ ກເຊື່ ອມຕໍື່ G ຕາມຂນ ື່ ງນາໜັ ັ ື້ ຕອນວິທີຂອງພຣີມ ໂດຍໄດນ ື້ າໜັ ື່ 1 + 2 + 1 + 3 = 7. ໍື້ ກຕາື່ ໍ ສຸດແມນ 149 ຕ ົວຢື່າງ 6.21: ຈາກແຜນວາດຕໍື່ ໄປນີ.ື້ ຈງ ື່ ົ ພິຈາລະນາເບິື່ ງວາື່ ຄວນກໍື່ ສາື້ ງເສັ ື້ນທາງແບບໃດເພື່ ອໃຫມ ື້ ຄ ີ າື່ ື້ າື່ ຍໃນການກໍື່ ສາື້ ງທາງຕາື່ ໍ ສຸດ ແຕມ ໃຊຈ ື່ ເີ ງື່ ອນໄຂວາື່ ຕອ ື້ ງມີເສັ ື້ນທາງເຊື່ ອມຕໍື່ ທຸກໆເມອງ, ຊື່ ງແຜນວາດ ື້ າື່ ຍໃນການສາື້ ງທາງ (ໜວ ລະອຽດກຽື່ ວກ ັບເມອງ, ເສັື້ນທາງ ແລະ ຄາື່ ໃຊຈ ື່ ນີ:ື້ ື່ ຍ: 1,000$) ລຸມ a b $ c d $ $ e f g h ວິທີແກ:ື້  ຂນຕອນທີ ັື້ 1: ເລອກເມອງຕິດກ ັບເສັ ື້ນທາງທີື່ ມີຄາື່ ໃຊຈ ື້ າື່ ຍໃນການກໍື່ ສາື້ ງຕາື່ ໍ ສຸດຄ: d ຫຼ f ຈາກນນ ັ ື້ ເລອກເສັື້ນທາງ df ຫຼ fd  ຂນຕອນທີ ັື້ 2: ເລອກເສັື້ນທາງທີື່ ມີຄາື່ ໃຊຈ ື້ າື່ ຍໃນການກໍື່ ສາື້ ງຕາື່ ໍ ສຸດຖ ັດຕໍື່ຈາກເສັ ື້ນທາງ fd ຄ: da  ຂນຕອນທີ ັື້ 3: ເລອກເສັື້ນທາງທີື່ ມີຄາື່ ໃຊຈ ື້ າື່ ຍໃນການກໍື່ ສາື້ ງຕາື່ ໍ ສຸດຖ ັດຕໍື່ຈາກເສັ ື້ນທາງ da ຄ: ab  ຂນຕອນທີ ັື້ 4: ເລອກເສັື້ນທາງທີື່ ມີຄາື່ ໃຊຈ ື້ າື່ ຍໃນການກໍື່ ສາື້ ງຕາື່ ໍ ສຸດຖ ັດຕໍື່ຈາກເສັ ື້ນທາງ ab ຄ: be  ຂນຕອນທີ ັື້ 5: ເລອກເສັ ື້ນທາງທີື່ ມີຄາື່ ໃຊຈ ື້ າຍໃນການກໍື່ ື່ ສາື້ ງຕາື່ ໍ ສຸດຖ ັດຕໍື່ຈາກເສັ ື້ນທາງ be , ຊື່ ງເຫັ ນ ວາື່ ເສັື້ນທາງ ed ແຕຖ ື່ າື້ ເລອກເສັື້ນທາງນີຈ ື້ ະເກີດມີວ ັກຖະຈ ັກ ດງ ື່ ັ ນນ, ັ ື້ ຈິື່ ງເລອກເສັ ື້ນທາງ bh  ຂນຕອນທີ ັື້ 6: ເລອກເສັ ື້ນທາງທີື່ ມີຄາື່ ໃຊຈ ື້ າື່ ຍໃນການກໍື່ ສາື້ ງຕາື່ ໍ ສຸດຖ ັດຕໍື່ ຈາກເສັ ື້ນທາງ bh , ຊື່ ງເຫັ ນ ວາື່ ເສັື້ນທາງ hf ແຕຖ ື່ າື້ ເລອກເສັ ື້ນທາງນີຈ ື້ ະເກີດມີວ ັກຖະຈ ັກ ດງ ື່ ັ ນນ, ັ ື້ ຈິື່ ງເລອກເສັ ື້ນທາງ fg  ຂນຕອນທີ ັື້ 7: ເລອກເສັື້ນທາງທີື່ ມີຄາື່ ໃຊຈ ື້ າື່ ຍໃນການກໍື່ ສາື້ ງຕາື່ ໍ ສຸດຖ ັດຕໍື່ຈາກເສັ ື້ນທາງ fg ຄ: gc ັ ື້ ຈາກຂນຕອນທີ 7 ສ ັງເກດເຫັ ນວ າື່ ທຸກໆເມອງແມນມີ ື່ ເສັ ື້ນທາງເຊື່ ອມຕໍື່ ຄບ ົ ແລວ ື້ ຈິື່ ງຢຸດການຄ ໍານວນ. ດື່ງັ ນນ, ັື້ ຈະໄດກ ົື້ ໄມແ ື້ ຣາຟຕນ ື້ ຜື່ທື່ ວ ົ ຕາື່ ໍ ສຸດ ຫຼ ເສັ ື້ ນທາງເຊື່ ອມຕໍື່ ເມອງຕາື່ ງໆທີື່ ຄວນສາື້ ງເພື່ ອໃຫື້ມລ ີ າຍ ຈາຍໃນການກໍື່ ື່ ສາື້ ງຕາື່ ໍ ສຸດ, ຊື່ ງກຣາຟ ຫຼ ເສັ ື້ນເສັ ື້ນທາງດງ ື່ ັ ກາື່ ວສະແດງໄດດ ື່ ັ ນີ:ື້ ື້ ງ a a b b $ $ c d $ c d $ e $ e ຫຼ f f g h h g ື່ ັ ນນ, ດງ ື້ າື່ ຍໃນການກໍື່ ສາື້ ງ 90$ + 200$ + 150$ + 180$ + 350$ + 500$ + 160$ = 1,630$ ັື້ ຄາື່ ໃຊຈ ັື້ ຈະໄດຄ ສະນນ, ື້ າື່ ຍໃນການກໍື່ ສາື້ ງຕາື່ ໍ ສຸດແມນ ື້ າື່ ໃຊຈ ື່ 1,630,000$. 150 6.6.2 ການນ ໍາໃຊກ ື້ ຣາຟອອຍເລີ ໃນຫົວ ຂໍື້ທີ 6.1 ໄດ ກ ື້ າື່ ວເຖິງ ບ ນ ັ ຫາຂ ວ ົ ແຫື່ ງ ເມ ອງໂກນິກ ເບີ ກ (Konigsberg Bridge Problem) ື້ ເີ ກາະ 2 ເກາະຢູກ ໂດຍເມອງນີມ ື່ າງແມນ ໍື້ ປະຊາຊ ົນ ື່ າ. ໃນເມ ອງນີື້ໄ ດ ຕ ື້ ງັື້ ບ ນ ັ ຫາວ ື່າ ເປັ ນ ໄປໄດ ື້ ຫຼ ບໍື່ ທີື່ ຈະ ຂ າື້ ມຜື່າ ນຂ ວ ົ ໃຫື້ຄ ບ ົ ທຸກ ຂ ວ ົ ,ໂດຍແຕ ື່ລ ະຂ ວ ົ ຂ າື້ ມໄດ ື້ ັ ື້ ພຽງຄງດຽວແລວື້ ກ ັບມາສູຈ ື່ ດ ົື້ ຸ ເລີື່ ມຕນ. ທື່ານເລອອນຮາດອອຍເລີ ໄດພ ື້ ະຍາຍາມແກ ື້ ັ ຫານີື້ ໂດຍໄດແ ໄຂບນ ື້ ທນແຜື່ນດິນແຕລ ື່ ະເກາະດວ ື້ ຍ ຈອມ A, B, C, D ແລະ ເສັື້ ນ ເຊື່ ອມຕໍື່ ແຕະລະຈອມ ຮູບທີ 12: ຂ ົວທັງ 7 ແຫງ ື່ ເມອງໂກນິກເບີກ ແທນເສັື້ນທາງເດີນຂາື້ ມຂ ົວ. ອອຍເລີໄດ ໃື້ ຊ ມ ື້ ັນຕີ ກ ຣາຟເປັ ນ ຕ ວ ົ ແບບຂອງ ເມອງເພື່ ອແກບ ັ ຫາ ໂດຍມ ັນຕີກຣາຟໃນທີື່ ນີເື້ ອີື້ນວາື່ ື້ ນ ມ ັນຕີກ ຣາຟຂອງເມອງໂກນິກ ເບີ ກ M (Konigsberg multigraph) ຈະປະກອບດວ ື້ ຍ ຈອມ 4 ຈອມແທນຝັື່ງ ແລະ ເກາະ, ເສັື້ ນ ເຊື່ ອມ 7 ເສັື້ ນ ແທນຂ ວ ື້ ມດື່ ງັ ົ ຂາ ສະແດງໃນຮູບຕໍື່ ໄປນີ:ື້ ຮູບທີ 6.14: ມ ັນຕີກຣາຟຂອງເມອງໂກນິກເບີກ M ຕ ົວຢາື່ ງ 6.22: ຈາກມ ັນຕີກຣາຟຂອງເມອງໂກນິກເບີກ M ຮູບທີ 6.14. ຈງ ື່ ົ ພິຈາລະນາເບິື່ ງວາື່ ເປັນໄປໄດ ື້ ຫຼ ບໍື່ ທີື່ ຈະຂາື້ ມຜາື່ ນຂ ົວໃຫຄ ື້ ົບທຸກຂ ົວ,ໂດຍແຕລ ື່ ະຂ ົວຂາື້ ມໄດພ ັ ື້ ື້ ຽງຄງດຽວແລວື້ ກ ັບມາສູຈ ື່ ດ ົື້ ຸ ເລີື່ ມຕນ. ວິທີແກ:ື້ ຈາກຮູບທີ 13 ເຮົາມີ: deg M A = 5 ຄີກ ຈະໄດ,ື້ M ບໍື່ ເປັນມ ັນຕີກຣາຟອອຍເລີ ື່ ັ ນນ, ດງ ັື້ ເປັນໄປບໍື່ ໄດທ ື້ ື່ ີຈະຂາື້ ມຜາື່ ນທຸກຂ ົວ, ແຕລ ັ ື້ ື່ ະຂ ົວຂາື້ ມຜາື່ ນພຽງຄງດຽວ ແລວ ົື້ ື້ ກ ັບມາຈຸດເລີື່ ມຕນ. ັ ເມອງໂກນິກເບີກໄດ ື້ ສາື້ ງຂ ົວເພີື່ມ 2 ໃນປັດຈຸບນ ຂວ ົ ໂດຍຂ ວ ົ ທ ໍາອິ ດ ແມ ນ ົ ທີ 2 ແມ ນ ື່ BC, ຂ ວ ື່ BD ໂດຍໃຫື້ມ ັນຕີ ກຣາຟ M  ເປັນຕວ ົ ແບບຂອງເມອງກາລີ ນິນກຣາສ ຊື່ ງປະກອບດວ ື້ ຍຈອມແທນຝັື່ ງ ແລະ ເກາະ, ເສັື້ນແທນຂ ົວຄດງ ື່ ັ ຮູບແຕມ ື້ : ເນື່ ອງຈາກ degM  A = degM  B = 5 ແລະ deg M  C = deg M  D = 4 ື່ ັ ນນ, ດງ ື້ າື່ ມ ັນຕີກຣາຟ M  ບ ັນຈຸຮອຍເດີນອອຍເລີ ັື້ ຈິື່ ງໄດວ ັື້ ໃນປັດຈຸບນ ສະນນ, ິ ກຣາສ ສາມາດຫາເສັ ື້ນທາງເດີນທີື່ ຂາື້ ມຂ ົວໃຫຄ ັ ຊາວເມອງກາລີນນ ື້ ົບທຸກຂ ົວໂດຍແຕ ື່ ັື້ ລະຂ ົວຖກຂາື້ ມພຽງຄງດຽວ ື່ ື່ ໍສາມາດກ ັບມາຢູຈ ແຕບ ື່ ດ ົື້ ໄດ.ື້ ຸ ເລີື່ ມຕນ 151  ີ ໃນປີ ຄສ. 1962 ທື່ານ ເໝ-ກູ ັ ຫາການສື່ງົ ຈ ົດໝາຍຂອງພະນ ັກງານໄປຊະນີຈນ ພິຈາລະນາບນ ກວນ (Mei-gu Guan, ເກີດ ປີ ຄສ. 1934) ນ ັກຄະນິດສາດຄ ົນຈີນ ໄດຕ ັື້ ນ ື້ ງບ ັ ຫາພະນ ັກງານໄປຊະນີຈນ ີ (The Chinese Postman Problem) ວາື່ ພະນ ັກງານໄປຊະນີໄດນ ື້ ງການໄປຊະນີໄປສື່ງົ ື້ ໍາຈ ົດໝາຍຈາກຫອ ຕາມບາື້ ນທີື່ ຢູື່ແຄມທາງຕາື່ ງໆແລວ ື່ ື່ ີຫອ ື້ ກ ັບມາຢູທ ື້ ວນວາງແຜນ ື້ ງການໄປຊະນີ, ພະນ ັກງານໄປຊະນີຄ ົນນີຄ ສື່ງົ ຈ ົດໝາຍແນວໃດຈິື່ງຈະຄວບຄຸມເສັ ື້ນທາງທັງໝດ ົ ໂດຍທີື່ ມີຜນ ົ ບວກຂອງໄລຍະທາງນອ ື້ ຍທີື່ ສຸດ. ັ ື້ ຂນຕອນວິ ທີຂອງບນ ີ (An algorithm of Chinese postman) ຄ: ກ ໍາ ັ ຫາພະນ ັກງານໄປຊະນີຈນ ນ ົດໃຫື້ G ເປັນກຣາຟຖວ ໍື້ ກເຊື່ ອມຕໍື່ ທີື່ ບໍື່ ບ ັນຈຸເອົ າວ ົງຈອນອອຍເລີ, ການສາື້ ງມ ັນຕີກຣາຟຖວ ື່ ງນາໜັ ໍື້ ື່ ງນາໜັ ກ M ຊື່ ງເກີດຈາກກຣາຟຖວ ໍື້ ກ G ໂດຍເພີື່ ມເສັ ື້ນເຊື່ ອມຊາບາງເສັ ື່ ງນາໜັ ໍື້ ື້ນ ແລວ ື້ ເຮັ ດໃຫື້ມ ັນຕີກຣາຟ ຖວ ໍື້ ກ M ບ ັນຈຸເອົ າວ ົງຈອນອອຍເລີທື່ ີມີນາໜັ ື່ ງນາໜັ ໍື້ ກຂອງກຣາຟ w(M) ຕາື່ ໍ ສຸດ ມີຂນຕອນວິ ັ ື້ ື່ ັ ນີ:ື້ ທີດງ (1). ຂນຕອນທີ ັື້ 1: ເລອກຈອມຄີກທັງໝ ົດໃນກຣາຟ G (2). ຂ ນຕອນທີ ັື້ 2: ກ ໍານ ົດໃຫື້ P = {{u1 , v1}, {u 2 , v 2 },..., {u k , vk }} ເປັນກຸມ ື່ ແບງ ື່ ສວ ື່ ນໃດໆຂອງກຸມ ື່ ຂອງຈອມຄີກໂດຍແຕລ ຸື່ ມີຂະໜາດ 2, ຊື່ ງ w(P) ເອີື້ນວາື່ ນາໜັ ື່ ະອະນຸກມ ໍື້ ກຂອງກຸມ ື່ ແບງ ື່ ນຂອງ P ໂດຍທີື່ w(P) = w1 + w 2 +... + w k ເມື່ ອ w i ເປັ ນນາໜັ ື່ ສວ ໍື້ ກຕາື່ ໍ ສຸດຂອງບາດເດີນ ື່ ະ i ໂດຍທີື່ i  {1, 2,..., k} u i − v i ສ ໍາລັບແຕລ (3). ຂນຕອນທີ ັື້ 3: ກ ໍານ ົດໃຫື້ Q = {{x1 , y1},{x 2 , y2 },..., {x k , yk }} ເປັ ນກຸມ ື່ ແບງ ັ ື້ ື່ ຂນໃດໆຂອງກຸ ມ ື່ ຂອງຈອມຄີກໂດຍແຕລ ຸື່ ມີຂະໜາດ 2, ຊື່ ງວາື່ w(Q) ເອີື້ນວາື່ ນາໜັ ື່ ະອະນຸກມ ໍື້ ກຂອງ ກຸມ ື່ ແບງື່ ສວ ໍື້ ກຕາື່ ໍ ສຸດຄຂນຕອນທີ ື່ ນຂອງ Q ທີື່ ມີນາໜັ ັ ື້ 2. (4). ຂນຕອນທີ ັື້ ື່ ະ i  {1, 2,..., k} ເຮົານ ໍາເສັື້ນແຕລ 4: ສ ໍາລັບແຕລ ື່ ະບາດເດີນ x i − yi ທີື່ ມີນາໜັ ໍື້ ກຕາື່ ໍ ສຸດມາເພີື່ ມໃນກຣາຟຖວ ໍື້ ກ G ເພື່ ອສາື້ ງກຣາຟຫຼ າຍເສັ ື້ນຖວ ື່ ງນາໜັ ໍື້ ກ M ື່ ງນາໜັ ຕ ົວຢາ ື່ ງ 6.23: ໃຫື້ G ເປັນກຣາຟຖວ ໍື້ ກ, ຊື່ ງປະກອບດວ ື່ ງນາໜັ ື້ ຍເສັ ື້ນເຊື່ ອມແທນເສັ ື້ນທາງ, ຈອມແທນ ໍື້ ກ ຂອງເສັື້ ນ ເຊື່ ອມ ແທນໄລຍະທາງ (ກິໂລແມັດ ). ຈື່ງົ ວາງແຜນໃຫື້ພ ະນ ັກງານໄປ ບາື້ ນ ແລະ ນ າໜັ ຊະນີນ ໍາຈ ົດໝາຍທີື່ ຫື້ອ ງການໄປຊະນີ ສື່ ງົ ຕາມບ ື້ານທີື່ ຢູື່ແ ຄມທາງໃຫື້ຄ ວບຄຸມ ເສັື້ ນທາງທັງ ໝ ດ ົ ແລື້ວ ກ ັບເຂົື້າມາສູທ ື່ ື່ ີຫອ ື້ ງການໄປຊະນີ ໂດຍໃຫໄ ື້ ດຜ ື້ ນ ົ ບວກໄລຍະທາງນອ ື້ ຍທີື່ ສຸດ? ວິທີແກ:ື້ ເນື່ ອງຈາກພະນ ັກງານໄປຊະນີຕອ ື້ ງການເດີນທາງສື່ ງົ ຈ ົດໝາຍໃຫື້ຄວບຄຸມທາງທັງໝດ ື່ ື່ ີ ົ ແລະ ກ ັບມາສູທ ຫອ ື່ ັ ນນ, ື້ ງການໄປຊະນີ. ດງ ັ ື້ ຖາື້ ກ ໍານ ົດໃຫື້ a ເປັນທີື່ ຕງຂອງຫ ັ ື້ ື້ ງການໄປຊະນີ ແລະ ເນື່ ອງ G ມີຈອມ ອ ຄີກ 2 ຈອມຄ ຈອມ b ແລະ f ຈະໄດກ ື້ ຣາຟຖວ ໍື້ ກ G ບໍື່ ບ ັນຈຸເອົ ງວ ົງຈອນອອຍເລີ ື່ ງນາໜັ 152  ັ ື້ ໂດຍຂນຕອນວິ ໍື້ ກຂອງບາດເດີນ b − f ໃນ G ຊື່ ງເຮົາມີ: ທີຂາື້ ງເທິງ ເຮົາພິຈາລະນານາໜັ w{bc} + w{cf} = 3 + 3 = 6 w{be} + w{ef} = 3 + 4 = 7 = w{b f} ເຫັ ນວ ື່າ ບາດເດີ ນ b − f : b, c, f ມີນ າໜັ ໍື້ ກ ຕ ື່າໍ ສຸ ດ. ດື່ ງັ ນ ນ, ັ ື້ ກ ໍານ ດ ົ ໃຫື້ M ເປັ ນ ມ ັນຕີ ກ ຣາຟ ຖວ ໍື້ ກ, ຊື່ ງເກີດຈາກການຖວ ື່ ງນາໜັ ື່ ງນາໜັ ໍື້ ນ b − f : b, c, f ຄ: ເສັ ື້ນ ໍື້ ກ G ໂດຍເພີື່ ມເສັ ື້ນຊາໃນບາດເດີ bc ແລະ cf ດງື່ ັ ສະແດງໃນຮູບລຸມ ື່ ນີ:ື້ ື່ ັ ນນ, ດງ ັື້ M ບ ັນຈຸວ ົງຈອນອອຍເລີທື່ ີມີນາໜັ ື່ w(G}) + w(bc) + w(cf) = 26 + 3 + 3 = 32 ໍື້ ກຕາື່ ໍ ສຸດແມນ ັື້ ພະນ ັກງານໄປຊະນີສ າມາດເດີ ນ ທາງຈາກຫື້ ອ ງການໄປຊະນີ ໄປສື່ ງົ ຈ ົດໝາຍຕາມບ ື້າ ນທີື່ ຢູື່ ສະນ ນ, ື້ ວບຄຸມເສັ ື້ນທາງທັງໝ ດ ບໍລິເວນແຄມທາງໄດຄ ົ ແລວ ື້ ກ ັບມາຫາຫື້ອງການໄປຊະນີ ໂດຍທີື່ ຜົນບວກຂອງ ື້ ຍສຸດຄ 32 ກິໂລ ແມັດ, ຊື່ ງພະນ ັກງານໄປຊະນີຕອ ໄລຍະທາງນອ ື້ ງເດີນຜາື່ ນ bc ແລະ cf ຊາໍື້ 2 ຄງັ ື້ 6.6.3 ການນ ໍາໃຊກ ື້ ຣາຟຮາມິນຕ ັນ ັ ຫາການເດີນທາງຂອງພະນ ັກງານຂາຍ (The travelling salesman Problem) ມີ ພິຈາລະນາບນ ພະນ ກ ົ ໜື່ ງຕ ື້ ອ ງການເດີ ນ ທາງໄປຍ ງັ ເມ ອງຕ ື່ າ ງໆຕາມບໍ ລິ ສ ດ ັ ງານຂາຍຄ ນ ັ ກ ໍານ ດ ົ ໃຫື້ ບ ນ ັ ຫາຄ : ື້ ວນວາງແຜນການເດີນທາງແນວໃດໃນການໄປເມອງຕາື່ ງໆ ຕາມບໍລິສ ັດກ ໍານ ົດໃຫື້ ພະນ ັກງານຂາຍຄ ົນນີຄ ໂດຍແວແ ື່ ຕລ ັ ື້ ື່ ະເມອງພຽງຄງດຽວແລ ວ ົື້ ໂດຍໄລຍະທາງລວມໃນການເດີນທາງນອ ື້ ກ ັບມາເມອງເລີື່ ມຕນ ື້ ຍ ສຸດ, ບ ັນຫານີເື້ ອີນ ື້ ວາື່ ບ ັນຫາການເດີນທາງຂອງພະນ ັກງານຂາຍ. ບນ ື້ າເປັ ັ ຫານີຈ ໍ ນຕອື້ ງໄດໃື້ ຊກ ື້ ຣາຟຖວ ໍື້ ກເປັນຕວ ື່ ງນາໜັ ົ ແບບຂອງເສັ ື້ນທາງການ ໂດຍຈອມແທນ ັ ກ ໍານ ົດໃຫື້, ເສັ ື້ນເຊື່ ອມ ແທນເສັ ື້ນທາງເຊື່ ອມລະຫວາື່ ງເມອງ ແລະ ນາໜັ ເມອງຕາມບໍລິສດ ໍື້ ກຂອງເສັ ື້ ນ ເຊື່ ອມແທນໄລຍະທາງຂອງເສັ ື້ນທາງ. ຖາື້ ວາື່ ກຣາຟຖວ ໍື້ ກເປັ ນຕວ ື່ ງນາໜັ ົ ແບບບໍື່ ບນ