กราฟเบื้องต้น3

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


          กราฟซึ่งเราสามารถลากทับรอยเส้นให้ผ่านทุกจุด จุดละครั้งเดียวและกลับมาบรรจบที่จุดเดิมได้ เราเรียกว่า กราฟแบบแฮมิลโทเนียน (Hamiltonian) ตามชื่อของเซอร์ วิลเลี่ยม โรแวน แฮมิลทัน นักคณิตศาสตร์ชาวอังกฤษ ซึ่งเป็นผู้หยิบ


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


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


 

สร้างโดย: 
นางสาวสูชิตา และครูศรนรินทร์

มหาวิทยาลัยศรีปทุม ผู้ใหญ่ใจดี
 

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

ช่วยกันนะครับ 
ไทยกู๊ดวิวจะได้อยู่นานๆ 
ไม่ถูกปิดเสียก่อน

ขอขอบคุณในความร่วมมือครับ

อ่านรายละเอียด

ด่วน...... ขณะนี้
พระราชบัญญัติลิขสิทธิ์ (ฉบับที่ 2) พ.ศ. 2558 
มีผลบังคับใช้แล้ว 
ขอให้นักเรียนและคุณครูที่ใช้งาน
เว็บ thaigoodview ในการส่งการบ้าน
ระมัดระวังการละเมิดลิขสิทธิ์ด้วย
อ่านรายละเอียดที่นี่ครับ

 

สมาชิกที่ออนไลน์

ขณะนี้มี สมาชิก 0 คน และ ผู้เยี่ยมชม 8 คน กำลังออนไลน์