|
|
|
ความจำเป็นและสภาพเงื่อนไขสำหรับวงจร และ ทางเดินออยเลอร์
.................วงจรออยเลอร์ จะมีโครงสร้าง ถ้าทุก ๆ ด้านนำมาใช้หมด การพิจารณา ความแตกต่าง ของ graph H โดยได้มาจาก Graph G โดยลบด้านที่ใช้จุดยอดในการ path ของเส้น เมื่อลบวงจร a,f,c,b,a จาก ภาพที่ 5 แล้ว จะได้กราฟย่อย ( subgraph ) รูป H ออกมา
.................ตั้งแต่กราฟ G เป็น connected กราฟ H จะมีจุดยอดที่น้อยทีสุด ซึ่งถูกลบออกจากกราฟ G ให้ w เป็นจุดยอด ( ในตัวอย่างอื่น ๆ C คือจุดยอด )
.................ทุก ๆ จุดยอดใน H มีดีกรีคู่ ( เพราะใน G ทุก ๆ จุดยอดมีดีกรีคู่ และในแต่ละคู่มีการกระทบด้านกับจุด จะถูกลบออกไปจากรูป H ) H อาจจะไม่ใช้ connected เริ่มที่ w เป็นโครงสร้าง Simple path ใน H โดยเลือกด้านที่เป็นไปได้ และถูกต้องใน G ( กราฟนี้สามารถเข้าได้โดยเริ่มตั้งแต่ w เป็นจุดตัดในวงจร ) สามารถทำได้ในกราฟภาพที่ 5 เราสามารถรวมวงจรได้เป็น a,f,c,d,e,c,b,a
.................จะเชื่อมด้านจนกระทั่งครบทุกด้านที่ถูกใช้ ( ในการกระทำนั้นต้องมีจุดสิ้นสุด โดยต้องมีด้านสิ้นสุดนั้นอยู่ภายในกราฟด้าย ) นี่เป็นการสร้างวงจรออยเลอร์ โครงสร้างจะแสดง ถ้าจุดยอดของ connected multigraph ทุกจุดมีดีกรีคู่ ดังนั้น กราฟจะมีวงจรออยเลอร์ .
..หน้า [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ ทบ. 1 ] [ ทบ. 2 ] [ ทบ.3 ]