ບົດທີ 6 Graphs

2. ປະເພດຂອງ graph

ມີຫຼາຍປະເພດຂອງກາຟ, ແຕ່ລະຄົນມີຄຸນສົມບັດແລະຄໍາຮ້ອງສະຫມັກທີ່ເປັນເອກະລັກຂອງຕົນເອງ. ນີ້ແມ່ນບາງປະເພດຂອງກາຟທົ່ວໄປທີ່ສຸດ:

1. 1. Directed Graph: ກຣາຟຊີ້ທາງ, ເຊິ່ງເອີ້ນກັນວ່າ digraph, ແມ່ນກາຟທີ່ຂອບມີທິດທາງທີ່ກ່ຽວຂ້ອງກັບພວກມັນ. ນີ້ຫມາຍຄວາມວ່າແຕ່ລະຂອບໄປຈາກຈຸດຫນຶ່ງ (ແຫຼ່ງ) ໄປອີກຈຸດຫນຶ່ງ (ຈຸດຫມາຍປາຍທາງ).

   2. Undirected Graph: ກຣາຟທີ່ບໍ່ມີທິດທາງແມ່ນກາຟທີ່ຂອບບໍ່ມີທິດທາງທີ່ກ່ຽວຂ້ອງກັບພວກມັນ. ນີ້ຫມາຍຄວາມວ່າແຕ່ລະຂອບເຊື່ອມຕໍ່ສອງແນວຕັ້ງໂດຍບໍ່ໄດ້ລະບຸແຫຼ່ງຫຼືຈຸດຫມາຍປາຍທາງ.

   3. Weighted Graph: ເສັ້ນສະແດງນ້ຳໜັກແມ່ນກາຟທີ່ແຕ່ລະຂອບມີນ້ຳໜັກ ຫຼື ຄ່າໃຊ້ຈ່າຍທີ່ກ່ຽວຂ້ອງກັບມັນ. ນ້ຳໜັກເຫຼົ່ານີ້ສາມາດສະແດງເຖິງໄລຍະທາງ, ຄ່າໃຊ້ຈ່າຍ, ຫຼືປະລິມານອື່ນໆທີ່ກ່ຽວຂ້ອງກັບແອັບພລິເຄຊັນ.

   4. Bipartite Graph: ກຣາຟ bipartite ແມ່ນເສັ້ນສະແດງທີ່ຈຸດຕັ້ງສາມາດແບ່ງອອກເປັນສອງຊຸດທີ່ບໍ່ຕິດກັນ. ຂອບທັງໝົດເຊື່ອມຕໍ່ຈຸດຕັ້ງຈາກຊຸດໜຶ່ງໄປຫາຈຸດຕັ້ງໃນຊຸດອື່ນ.

   5. Graph ສົມບູນ: ເສັ້ນສະແດງທີ່ສົມບູນແມ່ນເສັ້ນສະແດງທີ່ທຸກໆຄູ່ຂອງຈຸດເຊື່ອມຕໍ່ຖືກເຊື່ອມຕໍ່ດ້ວຍຂອບ.

   6. ຕົ້ນໄມ້: ຕົ້ນໄມ້ແມ່ນເສັ້ນສະແດງ acyclic ເຊື່ອມຕໍ່. ມັນ​ບໍ່​ມີ​ຮອບ​ວຽນ​ແລະ​ມີ​ແທ້​ຫນຶ່ງ​ເສັ້ນ​ທາງ​ລະ​ຫວ່າງ​ສອງ​ຈຸດ​ຕັ້ງ​.

   7. Cyclic Graph: ກຣາຟວົງຈອນແມ່ນກາຟທີ່ປະກອບດ້ວຍຢ່າງໜ້ອຍໜຶ່ງຮອບ, ເຊິ່ງເປັນເສັ້ນທາງທີ່ເລີ່ມຕົ້ນ ແລະສິ້ນສຸດຢູ່ຈຸດສູງສຸດດຽວກັນ.

   8. Acyclic Graph: ກຣາຟ acyclic ແມ່ນກາຟທີ່ບໍ່ມີຮອບວຽນ.

   9. Planar Graph: ກຣາບ Planar ແມ່ນກາຟທີ່ສາມາດແຕ້ມຢູ່ເທິງຍົນໄດ້ໂດຍບໍ່ມີຂອບຂ້າມ.

   10. Hypergraph: hypergraph ແມ່ນເສັ້ນສະແດງທີ່ແຕ່ລະຂອບສາມາດເຊື່ອມຕໍ່ຫຼາຍກວ່າສອງຈຸດ.

ຄວາມເຂົ້າໃຈກ່ຽວກັບຄຸນສົມບັດແລະປະເພດຂອງກາຟແມ່ນສໍາຄັນສໍາລັບການຂຽນໂປລແກລມທີ່ມີປະສິດທິພາບແລະສໍາລັບການເລືອກໂຄງສ້າງຂໍ້ມູນທີ່ເຫມາະສົມກັບຄໍາຮ້ອງສະຫມັກທີ່ກໍານົດໄວ້.

3. ຄວາມສາມາດພື້ນຖານຂອງ Graph

Graphs ສະຫນັບສະຫນູນບາງການດໍາເນີນງານພື້ນຖານທີ່ຖືກນໍາໃຊ້ທົ່ວໄປໃນການດໍາເນີນໂຄງການ. ນີ້ແມ່ນບາງການດໍາເນີນງານທີ່ສໍາຄັນທີ່ສຸດ:

1. 1. ແຊກ: ການເພີ່ມຈຸດ ຫຼື ຂອບໃໝ່ໃສ່ກຣາຟ.

   2. ການລຶບ: ການຖອນຈຸດ ຫຼື ຂອບອອກຈາກກຣາຟ.

   3. ເສັ້ນທາງຜ່ານ: ການໄປຢ້ຽມຢາມແຕ່ລະຈຸດໃນກາຟໃນຄໍາສັ່ງສະເພາະ. ມີສອງປະເພດຕົ້ນຕໍຂອງການຂ້າມຜ່ານ:

• • • ໄລຍະຂ້າມຜ່ານຄວາມເລິກຄັ້ງທຳອິດ: ໄປຢ້ຽມຢາມຈຸດຍອດໃນລັກສະນະຄວາມເລິກກ່ອນ, ບ່ອນທີ່ພວກເຮົາສຳຫຼວດເທົ່າທີ່ເປັນໄປໄດ້ຕາມແຕ່ລະສາຂາກ່ອນທີ່ຈະຕິດຕາມ.

    • Breadth-first traversal: ການໄປຢ້ຽມຢາມຈຸດຍອດໃນລັກສະນະທີ່ກວ້າງ-first, ບ່ອນທີ່ພວກເຮົາຄົ້ນຫາຈຸດສູງສຸດທັງຫມົດຢູ່ທີ່ຄວາມເລິກໃນປະຈຸບັນກ່ອນທີ່ຈະກ້າວໄປສູ່ຄວາມເລິກຕໍ່ໄປ.

1. 4. ເສັ້ນທາງສັ້ນທີ່ສຸດ: ຊອກຫາເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດລະຫວ່າງສອງຈຸດໃນກາຟ, ບ່ອນທີ່ຄວາມຍາວຂອງເສັ້ນທາງຖືກວັດແທກເປັນຜົນລວມຂອງນ້ໍາຫນັກຂອບ.

   5. Minimum Spanning Tree: ຊອກຫາຕົ້ນໄມ້ທີ່ກວ້າງຕໍ່າສຸດຂອງເສັ້ນກຣາຟ, ເຊິ່ງເປັນຕົ້ນໄມ້ທີ່ເຊື່ອມຕໍ່ບັນດາແນວຕັ້ງທັງໝົດດ້ວຍນ້ຳໜັກຂອບຂັ້ນຕ່ຳ.

   6. ການເຊື່ອມຕໍ່: ການກໍານົດວ່າກາຟແມ່ນເຊື່ອມຕໍ່, ຊຶ່ງຫມາຍຄວາມວ່າມີເສັ້ນທາງລະຫວ່າງສອງຈຸດ.

   7. ການກວດຫາຮອບວຽນ: ການກໍານົດວ່າກາຟມີຮອບວຽນໃດ.

ຄວາມສັບສົນທີ່ໃຊ້ເວລາຂອງການດໍາເນີນງານເຫຼົ່ານີ້ແມ່ນຂຶ້ນກັບການປະຕິບັດສະເພາະຂອງກາຟ. ຕົວຢ່າງ, ການປະຕິບັດການແຊກ ແລະການລຶບໃນລາຍການທີ່ຢູ່ຕິດກັນໃຊ້ເວລາ O(1) ໂດຍສະເລ່ຍ, ໃນຂະນະທີ່ການດໍາເນີນການດຽວກັນຢູ່ໃນຕາຕະລາງທີ່ຢູ່ຕິດກັນໃຊ້ເວລາ O(n^2), ບ່ອນທີ່ n ແມ່ນຈໍານວນຈຸດຕັ້ງຢູ່ໃນກຣາບ. ເສັ້ນທາງຜ່ານ, ເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດ, ແລະຂັ້ນຕອນວິທີທາງຕົ້ນໄມ້ຂັ້ນຕ່ຳໂດຍປົກກະຕິຈະໃຊ້ເວລາ O(V E), ບ່ອນທີ່ V ແມ່ນຈຳນວນຂອງແນວຕັ້ງ ແລະ E ແມ່ນຈຳນວນຂອບໃນກາຟ.

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