ความรู้เบื้องต้นเกี่ยวกับทฤษฎีกราฟ

Abstract

บทคัดย่อ

ในบทความนี้ กราฟไม่ได้หมายถึงแผนภูมิแท่ง แผนภูมิวงกลม หรือสมการพาราโบลา แต่กราฟคือรูปที่ประกอบด้วยจุดและเส้นโดยกราฟจะอยู่ในลักษณะของภาพ โดยใช้จุดแทนจุดยอดแต่ละจุด และลากเส้นเชื่อมระหว่างจุดยอดถ้าจุดยอดทั้งสองนั้นมีความสัมพันธ์กัน ประโยชน์อย่างหนึ่งของกราฟ คือสามารถใช้เป็นแบบจำลองทางคณิตศาสตร์ ซึ่งทำให้ปัญหาต่างๆง่ายขึ้น ยกตัวอย่างเช่น ปัญหาสะพานทั้ง 7 แห่งเมืองโคนิกส์เบิร์ก และปัญหา 4 สี ปัญหาสะพานทั้ง 7 แห่งเมืองโคนิกส์เบิร์กคือการหาวิธีเดินให้ทั่วทั้งเมืองโดยที่เดินผ่านทุกสะพานแค่เพียงครั้งเดียวเท่านั้น โดยเลออนฮาร์ด ออยเลอร์ วาดกราฟเพื่อเป็นแบบจำลองของทั้ง 7 สะพานและพิสูจน์ว่าไม่มีวิธีเดินดังกล่าว การพิสูจน์นี้จัดว่าเป็นบทความแรกในประวัติศาสตร์ของทฤษฎีกราฟ ปัญหา 4 สีคือการหาว่าจริงหรือไม่ที่สามารถระบายสีแผนที่ โดยใช้สีไม่เกิน 4 สีเพื่อที่จะให้พื้นที่ที่อยู่ติดกันมีสีต่างกัน ปัญหานี้จัดได้ว่าเป็นปัญหาที่โด่งดังที่สุดปัญหาหนึ่งในทางทฤษฎีกราฟ

Abstract

In this article, a graph is neither a bar chart, a pie chart, nor a parabola, but a figure consisting of points and lines. A graph is presented in a form of picture in which each point represents a vertex and a line represents an edge when two vertices have a relation. One advantage of graph is to be used as mathematical model which can simplify several problems; for example, Seven Bridges of Königsberg and Four colors problems. The Seven Bridges of Königsberg problem concerns with finding a walk through the city that would cross each bridge only once. Leonhard Euler had drawn a graph representing the seven bridges and proved that it is impossible to find the walk. This proof has been the first paper in the history of graph theory. In the four color case, the problem is whether a map could be colored using a maximum of four colors, but no two adjacent regions have the same color. This problem is one of the most famous theorems in the field of graph theory.