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

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


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


     เนื่องจากในกราฟแสดงสะพานตามปัญหาข้างต้น จุดต่างๆ เป็นที่พบกันของเส้น 3 เส้นบ้าง 5 เส้นบ้าง กราฟนี้จึงไม่ใช่กราฟที่ลากได้  ดังนั้นคำตอบของปัญหาการเดินข้ามสะพานข้างต้นก็คือ เราจะเดินข้ามสะพานตามเงื่อนไขดังกล่าวไม่ได้


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


          ข้อน่าคิดต่อไปก็คือ บทกลับของข้อสรุปข้างบนนี้เป็นจริงหรือไม่  คือถ้ากราฟรูปหนึ่งมีแต่จุดที่มีดีกรีเป็นเลขคู่ กราฟรูปนั้นจำต้องเป็นกราฟที่ลากได้เสมอไปหรือไม่ เราจะพบว่าบทกลับนี้ไม่จำเป็นต้องเป็นจริงเสมอไป เช่น ถ้าสะพานเชื่อมโยงเกาะกับฝั่ง ดังรูป

       
          เราจะพบว่ากราฟแสดงการเชื่อมโยงแผ่นดินทั้งสี่ด้วยสะพาน เป็นกราฟซึ่งแต่ละจุดมีดีกรีที่ 2 แต่กราฟนี้มิได้เป็นรูปที่ติดต่อเป็นชิ้นเดียวกัน จึงไม่เป็นกราฟที่ลากได้  ดังนั้นคุณสมบัติอีกอย่างหนึ่ง ซึ่งกราฟที่ลากได้จะต้องมีเสมอไปก็คือ การมีลักษณะติดต่อเป็นชิ้นเดียว


          ทฤษฎีบทว่าด้วยกราฟที่ลากได้ ซึ่งออยเลอร์พิสูจน์ไว้กล่าวว่า กราฟรูปหนึ่งรูปใด จะเป็นกราฟที่ลากได้ก็ต่อเมื่อกราฟนั้นติดต่อเป็นชิ้นเดียว และจุดทุกจุดมีดีกรีคู่เท่านั้น ปัจจุบันนี้เราเรียกกราฟเช่นนี้ว่า กราฟแบบออยเลอเรียน (Eulerien)

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

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

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

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

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

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

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

 

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

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