ບົດແນະນຳກ່ຽວກັບທິດສະດີກຣາຟ

ບົດນໍາກ່ຽວກັບທິດສະດີກຣາຟ

• ກຣາຟເປັນເຄື່ອງມືຄະນິດສາດທີ່ໃຊ້ຈໍາລອງບັນຫາດ້ວຍຮູບພາບ ແລະແກ້ໄຂບັນຫາດ້ວຍທິດສະດີຄອມບີນາຕໍຣິກ.
• ທິດສະດີກຣາຟເລີ່ມຕົ້ນໃນປີ 1736 ໂດຍ Leonhard Euler ຜູ້ທີ່ພະຍາຍາມແກ້ບັນຫາຂົວໂກນິກເບີກ.
• ເມືອງໂກນິກເບີກມີ 4 ສ່ວນຂອງແຜ່ນດິນທີ່ແບ່ງໂດຍແມ່ນ້ໍາ Pregel, ມີ 2 ເກາະຢູ່ກາງແມ່ນ້ໍາ ແລະ 7 ຂົວເຊື່ອມຕໍ່.
• ບັນຫາແມ່ນເປັນໄປໄດ້ບໍ່ທີ່ຈະຂ້າມຜ່ານທຸກຂົວພຽງເທື່ອດຽວ ແລະກັບຄືນສູ່ຈຸດເລີ່ມຕົ້ນ.
• Euler ວິເຄາະບັນຫານີ້ແລະພິສູດວ່າມັນເປັນໄປບໍ່ໄດ້.
• ຕໍ່ມາໃນປີ 1847 Kichhoft ໄດ້ນໍາໃຊ້ທິດສະດີກຣາຟເຂົ້າໃນການສຶກສາເຄືອຂ່າຍວົງຈອນໄຟຟ້າ.
• Cayley ນໍາໃຊ້ທິດສະດີກຣາຟເຂົ້າໃນວິຊາເຄມີ ແລະ Hamiton ໃຊ້ກຣາຟສຶກສາເກມປິດສະໜາ.
• ນັກຄະນິດສາດຫຼາຍທ່ານໄດ້ນໍາໃຊ້ທິດສະດີກຣາຟສຶກສາແຜນທີ່ແລະການລະບາຍສີແຜນທີ່.
• ໃນປີ 1936 Denes Koning ຂຽນປຶ້ມວິຊາທິດສະດີກຣາຟເປັນເຫຼັ້ມທໍາອິດ.
• ທິດສະດີກຣາຟຖືກນໍາໄປໃຊ້ຢ່າງກວ້າງຂວາງໃນວິທະຍາສາດຄອມພິວເຕີ, ເຄມີສາດ, ວິສະວະກໍາ, ພູມສາດ, ເສດຖະສາດ, ນິເວດວິທະຍາ, ວັດສະດຸສາດ, ແລະ ການຂົນສົ່ງ.
• ກຣາຟເປັນໂຄງສ້າງທີ່ປະກອບດ້ວຍຈອມ ແລະເສັ້ນເຊື່ອມລະຫວ່າງຈອມ, ສາມາດຈໍາລອງໄດ້ເກືອບທຸກສາຂາວິຊາ (ຕົວຢ່າງ: ເສັ້ນທາງເຊື່ອມຕໍ່ລະຫວ່າງເມືອງ).

ນິຍາມກຣາຟ

• ກຣາຟປະກອບດ້ວຍກຸ່ມຈອມ (V) ແລະ ກຸ່ມຂ້າງ (E), ໂດຍທີ່ V ເປັນກຸ່ມຈໍາກັດທີ່ບໍ່ມີຄ່າຫວ່າງເປົ່າ ແລະ E ເປັນກຸ່ມຂອງອະນຸກຸ່ມທີ່ມີສອງອົງປະກອບຂອງ V.
• ສັນຍາລັກຂອງກຣາຟຄື G = (V, E).
• ກຣາຟຖືກແບ່ງອອກເປັນ 2 ຊະນິດຄື: ກຣາຟລະບຸທິດທາງ ແລະ ກຣາຟບໍ່ລະບຸທິດທາງ.

ປະເພດຂອງກຣາຟ

• ກຣາຟງ່າຍດາຍ (Simple Graph): ບໍ່ມີບ້ວງ ແລະລະຫວ່າງສອງຈອມໃດໆມີເສັ້ນເຊື່ອມບໍ່ເກີນ 1 ເສັ້ນ.
• ມັນຕີກຣາຟ (Multi Graph): ມີເສັ້ນເຊື່ອມຕໍ່ລະຫວ່າງສອງຈອມຫຼາຍກວ່າໜຶ່ງເສັ້ນ ຫຼື ມີບ້ວງ.
• ກຣາຟສົມບູນ (Complete Graph): ທຸກໆສອງຈອມມີເສັ້ນເຊື່ອມດຽວ, ສັນຍາລັກດ້ວຍ Kn.
• ກຣາຟພາກສ່ວນ (Path Graph): ສາມາດແບ່ງຈອມອອກເປັນຫຼາຍກຸ່ມທີ່ອົງປະກອບໃນກຸ່ມດຽວກັນບໍ່ມີເສັ້ນເຊື່ອມຕໍ່ກັນ.

ນິຍາມເພີ່ມເຕີມ

• ກຣາຟສອງພາກສ່ວນ (Bipertite Graph):ກຣາຟ G(V,E) ທີ່ແບ່ງເປັນສອງກຸ່ມຄື P1 ແລະ P2 ໂດຍທີ່ P1 ∩ P2 = ∅, ແຕ່ລະເສັ້ນເຊື່ອມ e ∈ E ຕິດຈອດກັບຈອມໜຶ່ງຂອງ P1 ແລະອີກຈອມໜຶ່ງຂອງ P2.
• ກຣາຟສອງພາກສ່ວນສົມບູນ (Complete Bipartite Graph): Krs ກໍານົດໂດຍຈໍານວນຈອມໃນແຕ່ລະພາກສ່ວນ.
• ກຣາຟວັກຖະຈັກ (Cycle Graph): Cn ເປັນກຣາຟງ່າຍດາຍທີ່ເປັນເສັ້ນອ້ອມຈອດເຊິ່ງແຕ່ລະຈອມມີເສັ້ນເຊື່ອມຕໍ່ສອງເສັ້ນ.
• ກຣາຟຕົ້ນໄມ້ (Tree Graph): Tn ເປັນກຣາຟງ່າຍດາຍເຊື່ອມຕໍ່, ຫຼາຍໆກຣາຟຕົ້ນໄມ້ຢູ່ລວມກັນເອີ້ນວ່າກຣາຟປ່າໄມ້ (Forest graph).
• ວົງຈອນອອຍເລີ (Euler Circuit): ບັນຈຸເອົາທຸກເສັ້ນຂອງກຣາຟ ແລະກຣາຟທີ່ບັນຈຸວົງຈອນອອຍເລີເອີ້ນວ່າກຣາຟອອຍເລີ.

ວັກຖະຈັກຮາມິນຕັນ

• ວັກຖະຈັກ (Hamiltonian cycle) ບັນຈຸຈອມທຸກຈອມຂອງກຣາຟ.
• ກຣາຟທີ່ບັນຈຸວັກຖະຈັກຮາມິນຕັນ ເອີ້ນວ່າກຣາຟຮາມິນຕັນ.
• ເກມໄອໂຄຊຽນ (Icosian Game) ຂອງ Rowan Hamilton ໄດ້ນໍາສະເຫນີການທ່ອງທ່ຽວຮອບໂລກໂດຍໃຊ້ຮູບກ້ອນ 12 ໜ້າ.
• ຈຸດປະສົງຄືເພື່ອຊອກຫາການເດີນທາງຜ່ານທຸກເມືອງໂດຍບໍ່ຊ້ໍາກັນ ແລະກັບຄືນສູ່ເມືອງເລີ່ມຕົ້ນ.

ກຣາຟລະບຸທິດທາງ

• ກຣາຟທີ່ມີລູກສອນຊີ້ບອກທິດທາງ, ປະກອບດ້ວຍກຸ່ມຈອມ V(D) ແລະ ກຸ່ມເສັ້ນເຊື່ອມ E(D) ທີ່ເປັນຄູ່ອັນດັບ.
• ເສັ້ນເຊື່ອມລະຫວ່າງສອງຈອມເອີ້ນວ່າເສັ້ນລະບຸທິດທາງ.
• ກຣາຟລະບຸທິດທາງທີ່ມີການກໍານົດຄ່າຈໍານວນຈິງເທິງເສັ້ນເຊື່ອມເອີ້ນວ່າກຣາຟລະບຸທິດທາງແບບຖ່ວງນໍ້າໜັກ.
• ກຣາຟໜ້າພຽງ: ກຣາຟທີ່ສາມາດແຕ້ມຢູ່ໜ້າພຽງໂດຍບໍ່ມີເສັ້ນໄຂວ້ກັນເອີ້ນວ່າກຣາຟໜ້າພຽງ.

ກຣາຟຕື່ມເຕັມ

• ກຣາຟຕື່مເຕັມ (Complement graph) ຂອງກຣາຟ G (ສັນຍາລັກG´) ຄື ກຣາຟທີ່ມີກຸ່ມຂອງຈອມເທົ່າກັບ V(G).
• ລະຫວ່າງຈອوم u ແລະ v ໃນ V(G): uv ເປັນເສັ້ນໃນກຣາຟຕື່ມເຕັມ ຖ້າ uv ບໍ່ເປັນເສັ້ນເຊື່ອມໃນກຣາຟ G.

ດີກຣີແລະຂະໜາດຂອງກຣາຟ

• ລໍາດັບຂັ້ນຄືຈໍານວນຈອມໃນກຣາຟ (ສັນຍາລັກ p = |V(G)|) ແລະ ຂະໜາດຄືຈໍານວນຂ້າງ (q = |E(G)|).
• ດີກຣີຂອງຈອມ v ໃນກຣາຟ G (deg(v)) ຄືຈໍານວນເສັ້ນເຊື່ອمต่อ ທີ່ເຊື່ອມຈອມ v.
• ຈອមຄູ່ ຖ້າ deg(v) ເປັນຈໍານວນຄູ່, ຈອມຄີກ ຖ້າ deg(v) ເປັນຈໍານວນຄີກ.
• ດີກຣີນ້ອຍสุด (δ(G)) ຄືດີກຣີທີ່ຕ່ໍາສຸດຂອງຈອມ, ດີກຣີໃຫຍ່ສຸດ (△(G)) ຄືດີກຣີທີ່ໃຫຍ່ສຸດຂອງຈອມ.
• ຫຼັກເກນ: ຜົນລວມຂອງດີກຣີທັງໝົດຂອງຈອມໃນກຣາຟເທົ່າກັບສອງເທົ່າຂອງຈໍານວນຂ້າງ (∑ deg(vi) = 2q).

ຫຼັກການຄຳນວນ

• ຫຼັກການ ກຣາφήທຸກກລາຟມີຈໍານວນຈອມຄິກເປັນຈໍານວນຄະ.

ກ່ຽວກັບອະນຸກຣາຟ

• ອະນຸກຣາຟ (Subgraph):H ເປັນອະນຸກຣາຟຂອງ Gl ຖ້າ V(H) ⊆ V(G) ແລະ E(H) ⊆ E(G).
• ອະນຸກຣາຟແທ້ (Properm Subgrap):
• ອະນຸກຣາຟແບບປົກຄຸມ (Spanning Subgraph).
• ອະນຸກຣາຟແບບກໍ່ກໍາເນີດ (Induced subgraph).

ກຣາຟຖອດແບບ

• ກຣາຟທີ່ຮູບຮ່າງພາຍນອກຄືກັນ
• ກຣາฟถອດແບບກັບຮນມ(Isomorphism Fucntion)
• ກຣກສາດຖອດແບບສັລລະຫຼອງຮ່າฟ

ການນຳໃຊ້ທິດສະດີກຣາຟ

• ການນໍາໃຊ້ກຣາຟຕົ້ນໄມ້ແບບບານ
• ຂັ້ນຕອມວິທໍກົມແຮງຮານ
• ການນໍາໃຊ້ຊາຫົນອໍເລ່ສກາບີຣຍ
• การใช้งานเถิกาพร์รามลกัน

ບົດຝຶກຫັດ

• (ສຶກສາບົດຝຶກຫັດນຳ!!)