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