ทฤษฏีกราฟออยเลอร์

ทฤษฎีกราฟของออยเลอร์ 


อยเลอร์ได้ให้ทฤษฎีที่เกี่ยวกับปัญหานี้ไว้ดังนี้

    • เครือข่าย ที่แสดงเป็นกราฟจะประกอบด้วยจุดเชื่อมโยง
      (Vertices) และเส้นเชื่อมโยงระหว่างจุด เรียกว่า arcs
    • จุด
      ที่มีจำนวนเส้นที่เชื่อมออกไปยังจุดอื่นเป็นจำนวนคี่ เรียกว่า odd
      และถ้าจุดนั้นมีเส้นเชื่อมออกไปยังจุดอื่นเป็นจำนวนคู่ จะเรียกว่า even
    • เส้นทางออยเลอร์ คือเส้นทางที่ลากผ่านเส้นต่าง ๆ
      ในเครือข่าย โดยแต่ละเส้นลากผ่านได้เพียงครั้งเดียว
    • ทฤษฎีของออยเลอร์ กล่าวว่า ถ้าหากว่าเครือข่ายใดมีจุดที่เป็น odd มากกว่าสองขึ้นไป
      จะไม่มีทางสร้างเส้นทางออยเลอร์ได้

 

ลองพิจารณาจากปัญหากราฟต่อไปนี้

 

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s

%d bloggers like this: