|
|
|
.......นิยาม 2 ทางเดิน X0 , X , , Xn-1 , Xn ในกราฟ G = (V,E) เราเรียกว่า ทางเดินฮามิลตัน ถ้า V = {X0 , X1 , , X n-1 ,Xn } และ X; น X; สำหรับ 0 ฃ I ฃ j ฃ n วงจร X0 , X1 , , X n-1 , Xn , X0 (เมื่อ n > 1) ในกราฟ G = (V,E) เราเรียกว่า วงจรฮามิลตัน ( ) ถ้า X0 , X1 , , X n-1 , Xn คือ ทางเดินแฮมิลตัน
..........คำนิยามนี้ ถูกค้นพบเมื่อปี 1857 โดยนักคณิตศาสตร์ชาวไอริส เซอร์วิลเลี่ยม โรวัล ฮามิลตัน รูปต่อของฮามิลตันทำด้วยไม้เป็นรูปทรงคล้ายวงกลม ตัดหน้าเป็นรูป 5 เหลี่ยมเท่าๆ กัน 12 รูป ดังภาพ 8(a) ซึ่งมีจุดหลักอยู่บนจุดยอดของแต่ละด้านและมีความยาว จุดยอด 20 จุด ของรูป 5 เหลี่ยม สมมติให้แทนเมืองต่าง ๆ ในโลก เราเริ่มต้นที่เมืองหนึ่งและเดินทางไปตามด้านของเหลี่ยมต่าง ๆ โดยผ่านเมืองทั้ง 19 เมือง เพียง 1 ครั้งและกลับมายังเมืองที่ตั้งต้น การเดินทางของวงจร เดินตามจุดที่กำหนดไว้โดยความยาวและจุดหลัก
รูปที่ 8 ( a , b )
..........ผู้แต่งไม่สามารถจัดหาไม้รูปทรง 12 เหลี่ยมให้ได้ เราจึงมาพิจารณาคำถามต่อไปนี้ กราฟในรูป 8(b) วงจรผ่านจุดยอดโดยผ่านจุดแต่ละจุดแค่เพียง 1 ครั้งหรือไม่ วิธีที่จะแก้ปัญหาได้จะต้องมีกราฟที่มีรูปร่างคล้ายกันประกอบไปด้วยจุดยอดและด้านของรูปทรงห้าเหลี่ยม คำตอบของรูปต่อฮามิลตัน แสดงใช้ในภาพที่ 9
รูปที่ 10
..หน้า [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ ทบ. 1 ] [ ทบ. 2 ] [ ทบ.3 ]