ทฤษฎีกราฟ…

     ทฤษฎีกราฟนั้น มีจุดเริ่มจากผลงานตีพิมพ์ของ เลออนฮาร์ด ออยเลอร์ ภายใต้ชื่อ Solutio problematis ad geometriam situs pertinentis ในปี ค.ศ. 1736 (พ.ศ. 2279) หรือที่รู้จักกันในนาม ปัญหาสะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก (Seven Bridges of Königsberg) เขาสนใจวิธีที่จะข้ามสะพานทั้ง 7 แห่งนี้ โดยข้ามแต่ละสะพานเพียงครั้งเดียวเท่านั้น ผลงานนี้ยังถือว่าเป็นงานแนวทอพอโลยีชิ้นแรกในเรขาคณิต กล่าวคือเป็นงานที่สนใจเฉพาะโครงสร้างของรูปเรขาคณิตที่ไม่ขึ้นกับขนาด ระยะ หรือการวัดใดๆ งานชิ้นสำคัญนี้ยังได้แสดงความเกี่ยวข้องอย่างลึกซึ้งระหว่างทฤษฎีกราฟและทอ พอโลยี

   ในปี ค.ศ. 1845 (พ.ศ. 2388) กุสตาฟ คีร์คฮอฟฟ์ ได้เผยแพร่ผลงานที่รู้จักกันภายใต้ชื่อกฎวงจรไฟฟ้าของคีร์คฮอฟฟ์ ที่แสดงความสัมพันธ์ของกระแสและความต่างศักย์ บนกราฟที่แทนวงจรไฟฟ้า

   ต่อมาในปี ค.ศ. 1852 (พ.ศ. 2395) ฟรานซิส กัทธรี ได้ตั้งปัญหาสี่สี (Four color problem) เพื่อศึกษาถึงความเป็นไปได้ที่จะใช้สีเพียง 4 สี เพื่อระบายให้กับประเทศต่าง ๆ บนแผนที่ใด ๆ โดยที่ประเทศเพื่อนบ้านจะไม่มีสีเดียวกัน. ปัญหานี้ได้ถูกแก้ในอีกมากกว่า 100 ปีถัดมา ในปี ค.ศ. 1976 (พ.ศ. 2519) โดย เคนเนธ แอปเพล และวูล์ฟกัง ฮาเคน ซึ่งใช้คอมพิวเตอร์เข้าช่วยในการพิสูจน์ ซึ่งทำให้ได้รับการวิพากษ์วิจารณ์อย่างกว้างขวาง. อย่างไรก็ตามจากความพยายามในการแก้ปัญหา 4 สีนี้ ทำให้มีการสร้างแนวคิดและนิยามพื้นฐานในทฤษฎีกราฟขึ้นอย่างมากมาย จนอาจจะกล่าวได้ว่าจุดเริ่มต้นของทฤษฎีกราฟเกิดจากปัญหาสี่สีนี้เอง

 การจำแนกชนิดของกราฟ

ตามลักษณะข้อมูลที่เก็บ

• กราฟแบบมีทิศทาง (directed graph) และ กราฟแบบไม่มีทิศทาง (undirected graph)
• กราฟแบบมีน้ำหนัก (weighted graph) และ กราฟแบบไม่มีน้ำหนัก (unweighted graph)

ตามการเชื่อมโยง

• กราฟสมบูรณ์ (complete graph)
• กราฟต่อเนื่อง (connected graph)
• กราฟไม่ต่อเนื่อง (unconnected graph)
• ต้นไม้ (โครงสร้างข้อมูล) (tree)

 

การประยุกต์ของกราฟ
บทนิยาม  วงจร (circuit) คือแนวเดินที่เส้นเชื่อมทั้งหมด แตกต่างกันโดยมีจุดเริ่มต้นและ จุดสุดท้ายเป็นจุดเดียวกัน
บทนิยามวงจรออยเลอร์ (Euler circuit) คือ วงจรที่ผ่านจุดยอดทุกจุด และ เส้นเชื่อมทุกเส้นของกราฟ
              โดยที่จุดสามารถซ้ำกันได้ และจะเรียกกราฟที่มีวงจรออยเลอร์ว่า กราฟออยเลอร์

 

ที่มาเนื้อหา

[ http://th.wikipedia.org/wiki/ทฤษฎีกราฟ ]

[http://invinciblemathematic.blogspot.com/]

[http://basicgraphtheory.blogspot.com/]

[http://www.youtube.com/watch?v=bMbJy75yrcY]

“ขอขอบพระคุณทุกเว็บไซด์ที่ได้นำข้อมูลมา เพื่อเป็นส่วนหนึ่งของการเรียนการสอน และเป็นสื่อในการศึกษา”

นางสาว พัทธ์ธีรา ธนาวุฒิธีรวงศ์