ทฤษฎีกราฟเบื้องต้นและการประยุกต์

บทคัดย่อ

บทคัดย่อ

ในบทความวิชาการฉบับนี้ได้อภิปรายถึงปัญหาคลาสสิกที่น่าสนใจ 3 ปัญหาในทฤษฎีกราฟได้แก่ปัญหาการจับมือทักทายในงานเลี้ยงปัญหาการเดินข้ามสะพานทั้งเจ็ดแห่งเมืองเคอนิกส์แบร์ก และปัญหาการหาวงแฮมิลตันและรอยเดินออยเลอร์ในกราฟ การหาคำตอบของทั้งสามปัญหาอาศัยทฤษฎีที่เกี่ยวข้องกับกราฟออยเลอร์และกราฟแฮมิลตันการแก้ปัญหาแรกก่อให้เกิดทฤษฎีบทแรกในทฤษฎีกราฟซึ่งรู้จักในอีกชื่อหนึ่งว่าบทตั้งการจับมือ (Handshaking Lemma)

คำสำคัญ: ทฤษฎีกราฟ กราฟออยเลอร์กราฟแฮมิลตัน

Abstract

In this paper, we discuss three interesting classic problems in graph theory: the Handshake problem, the Kӧnigsberg Bridge problem and the problem of finding Hamiltonian cycles and Euler trails. The solutions for the first three problems are obtained by applying theories related to Eulerian and Hamilto-nian Graphs. The first problem solving provided the first theory in graph theory known as Handshaking Lemma.

Keywords: Graph Theory, Eulerian Graphs, Hamil-tonian Graphs