Home
Education
Classroom
Knowledge
Blog
TV
ธรรมะ
กิจกรรม
โครงการทรูปลูกปัญญา

บทนำ

Posted By Plookpedia | 06 ก.ย. 60
197 Views

  Favorite

 

บทนำ 

 

 

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

 

การที่เริ่มต้นทฤษฎีว่าด้วยกราฟนี้ เกิดขึ้นในราวปี พ.ศ. ๒๒๗๙ คือ เมื่อออยเลอร์นำปัญหาการเดินข้ามสะพาน ในเมืองเคอนิกสเบอร์ก ประเทศปรัสเซีย อันเป็นปัญหาเก่าแก่ ที่ยังไม่เคยมีใครแก้ตกมาก่อนขึ้นมาพิจารณา

 

 

ปัญหาดังกล่าว เป็นปัญหาเกี่ยวกับการเดินข้ามสะพานเจ็ดสะพาน ซึ่งเชื่อมโยงระหว่างฝั่งกับเกาะ และ เกาะกับเกาะ ดังในรูปข้างบน ปัญหามีว่า เราจะเดินจากจุดใดจุดหนึ่งข้ามสะพานต่างๆ ให้ครบทุกสะพาน โดยเดินข้ามแต่ละสะพานเพียงครั้งเดียว แล้วกลับมาถึงจุดเดิมได้หรือไม่

 

กราฟแสดงสะพานในเมืองเคอนิกสเบอร์ก

 

ออยเลอร์แทนแผ่นดิน อันได้แก่ฝั่งแม่น้ำกับเกาะ ด้วยจุดสี่จุด และ แทนสะพานทั้งเจ็ด ด้วยเส้นเจ็ดเส้น เชื่อมโยงจุดทั้งสี่ ตามที่สะพานเชื่อมโยงแผ่นดิน ซึ่งแทนด้วยจุดเหล่านั้น รูปที่ออยเลอร์ได้ คงจะเป็นดังรูปทางขวามือ

รูปที่ได้นี้ก็คือ กราฟแสดงการเชื่อมโยงแผ่นดินส่วนต่างๆ ด้วยสะพาน คงจะไม่ผิดหากเราจะกล่าวว่า กราฟรูปนี้เป็นกราฟรูปแรก ที่ถูกนำมาใช้ในการศึกษาทฤษฎีว่าด้วยกราฟ

เว็บไซต์ทรูปลูกปัญญาดอทคอมเป็นเพียงผู้ให้บริการพื้นที่เผยแพร่ความรู้เพื่อประโยชน์ของสังคม ข้อความและรูปภาพที่ปรากฏในบทความเป็นการเผยแพร่โดยผู้ใช้งาน หากพบเห็นข้อความและรูปภาพที่ไม่เหมาะสมหรือละเมิดลิขสิทธิ์ กรุณาแจ้งผู้ดูแลระบบเพื่อดำเนินการต่อไป
Tags

Content

1
กราฟ
กราฟ ปัญหาเกี่ยวกับการเดินข้ามสะพานนั้น เมื่อแปลงมาเป็นภาษาของทฤษฎีว่าด้วยกราฟ ก็กลายเป็นปัญหาที่ว่า เราจะเริ่มต้นจากจุดใดจุดหนึ่ง ลากทับรอยเส้นต่าง ๆ ในกราฟรูปนี้ให้ครบทุกเส้น เส้นละครั้งเดียวแล้วในที่สุด ลากมาบรรจบที่จุดตั้งต้นได้ หรือ ไม่
657 Views
  • Posted By
  • Plookpedia
  • 15 Followers
  • Follow