ค้นหาทุกอย่างในเว็บครูบ้านนอก :
ชุมชนครู บุคลากรทางการศึกษา และนักเรียน แหล่งความรู้สำหรับครู นักเรียน ข่าวการศึกษา ห้องสมุดความรู้ทุกกลุ่มสาระการเรียนรู้ และความรู้ทั่วไป เผยแพร่ผลงานวิชาการ ที่นี่


ข่าวการศึกษา     ความรู้ทั่วไป     งานราชการ/รัฐวิสาหกิจ/บริการสังคมคณิตศาสตร์  ▶ ข่าว/บทความ ▶ หน้าแรก
เรื่องของกราฟ
คณิตศาสตร์ 3 ม.ค. 2551 เปิดอ่าน : 18,997 ครั้ง
☰แชร์เลย >  
เพิ่มเพื่อน
Advertisement

เรื่องของกราฟ
Advertisement

กราฟ โดย นายวิรุฬห์ บุญสมบัติ

   การที่เริ่มต้นทฤษฎีว่าด้วยกราฟนี้ เกิดขึ้นในราวปี  พ.ศ. 2279  คือ เมื่อออยเลอร์ นำปัญหาการเดินข้ามสะพานในเมืองเคอนิกสเบอร์ก ประเทศปรัสเซีย อันเป็นปัญหาเก่าแก่ที่ยังไม่เคยมีใครแก้ตกมาก่อนขึ้นมาพิจารณา ปัญหาดังกล่าวเป็นปัญหาเกี่ยวกับการเดินข้ามสะพานเจ็ดสะพาน ซึ่งเชื่อมโยงระหว่างฝั่งกับเกาะ และเกาะกับเกาะปัญหามีว่าเราจะเดินจากจุดใดจุดหนึ่งข้ามสะพานต่างๆ ให้ครบทุกสะพาน โดยเดินข้ามแต่ละสะพานเพียงครั้งเดียวแล้วกลับมาถึงจุดเดิมได้หรือไม่
          ออยเลอร์แทนแผ่นดิน อันได้แก่ฝั่งแม่น้ำกับเกาะด้วยจุดสี่จุด และแทนสะพานทั้งเจ็ดด้วยเส้นเจ็ดเส้น เชื่อมโยงจุดทั้งสี่ตามที่มีสะพานเชื่อมโยงแผ่นดิน ซึ่งแทนด้วยจุดเหล่านั้น
         รูปที่ได้นี้ก็คือกราฟแสดงการเชื่อมโยงแผ่นดินส่วนต่างๆ ด้วยสะพาน คงจะไม่ผิดหากเราจะกล่าวว่ากราฟรูปนี้ เป็นกราฟรูปแรกที่ถูกนำมาใช้ในการศึกษาทฤษฎีว่าด้วยกราฟ
          ปัญหาเกี่ยวกับการเดินข้ามสะพานนั้น เมื่อแปลงมาเป็นภาษาของทฤษฎีว่าด้วยกราฟก็กลายเป็นปัญหาที่ว่า เราจะเริ่มต้นจากจุดใดจุดหนึ่ง ลากทับรอยเส้นต่างๆ ในกราฟรูปนี้ให้ครบทุกเส้น เส้นละครั้งเดียว แล้วในที่สุดลากมาบรรจบที่จุดตั้งต้นได้หรือไม่
          ออยเลอร์มิได้จำกัดการแก้ปัญหาทำนองนี้ กับกราฟรูปนี้เพียงรูปเดียว เขาพิสูจน์ทฤษฎีบทซึ่งอาจนำไปใช้กับกราฟรูปใดๆ ก็ได้ การลองแก้ปัญหาในทำนองที่กล่าวไว้ข้างต้นกับรูปกราฟคงจะช่วยให้เราเข้าในทฤษฎีบทของออยเลอร์ได้ดีขึ้น
          ในกราฟรูป ก.  ถ้าเราตั้งต้นจากจุดใดจุดหนึ่ง แล้วลากทับรอยเส้นกราฟไปในทางใดทางหนึ่งเรื่อยๆ ไป ในที่สุดเราจะกลับมาถึงจุดเดิมได้โดยลากผ่านเส้นต่างๆ ครบทุกเส้น และเส้นละครั้งเดียว สำหรับกราฟรูป ข.  นั้นเราก็อาจตั้งต้นจากจุดใดๆ ลากทับรอยเส้นต่างๆ ไปเรื่อย ให้ครบทุกเส้น เส้นละครั้งเดียว แล้วกลับมาบรรจบที่จุดเดิมได้ไม่ยากนัก แต่เราคงพบอุปสรรคในการลากทับรอยเส้นของกราฟรูป ค.
          เพื่อความสะดวกในการกล่าวข้อความในตอนต่อๆ ไป เราจะเรียกกราฟใดๆ ที่เราอาจเริ่มต้นจากจุดใดจุดหนึ่งลากทับรอยเส้นของมันไปเรื่อยๆ ให้ครบทุกเส้น เส้นละครั้งเดียว แล้วในที่สุดกลับมาบรรจบที่จุดเดิมนี้ว่า กราฟที่ลากได้ ขอให้สังเกตว่าในกราฟแต่ละรูปที่เราลากได้นั้น จำนวนเส้นที่เราลากเข้าหาจุดใดๆ ย่อมเท่ากันกับจำนวนเส้นที่เราลากออกจากจุดนั้นๆ เสมอไปแสดงว่าจำนวนของเส้นที่พบกันที่จุดใดๆ ต้องเป็นจำนวนคู่เสมอ ดังนั้นกราฟที่ลากได้แต่ละรูปจำต้องมีจำนวนของเส้นที่พบกันที่แต่ละจุดเป็นจำนวนคู่ หากกราฟใดมีจุดสักจุดหนึ่ง หรือหลายๆ จุด ซึ่งเป็นที่พบกันของเส้นต่างๆ ที่มีจำนวนเส้นเป็นเลขคี่  กราฟนั้นย่อมไม่เป็นกราฟที่ลากได้
          เนื่องจากในกราฟแสดงสะพานตามปัญหาข้างต้น จุดต่างๆ เป็นที่พบกันของเส้น 3 เส้นบ้าง 5 เส้นบ้าง กราฟนี้จึงไม่ใช่กราฟที่ลากได้  ดังนั้นคำตอบของปัญหาการเดินข้ามสะพานข้างต้นก็คือ เราจะเดินข้ามสะพานตามเงื่อนไขดังกล่าวไม่ได้
         นอกจากในการศึกษาปัญหาเกี่ยวกับการลากเส้นตามรอยเส้นกราฟดังได้กล่าวมาแล้ว จำนวนของเส้นที่พบกันที่แต่ละจุดของกราฟ ยังมีบทบาทในการศึกษาปัญหาอย่างอื่นอีกด้วย ในภาษาของทฤษฎีว่าด้วยกราฟ เราเรียกจำนวนของเส้นที่พบกันที่จุดใดๆ ของกราฟว่า ดีกรี  ของจุดนั้น เช่น แต่ละจุดในกราฟรูป ก. เป็นจุดที่มีดีกรี 2 ส่วนกราฟรูป ข. ประกอบด้วยจุดที่มีดีกรี  2  สี่จุด  กับจุดที่มีดีกรี 4 หนึ่งจุด  ดังนั้น เราอาจกล่าวข้อสรุปข้างต้นเสียใหม่ด้วยภาษาของวิชาทฤษฎีด้วยกราฟได้ว่า   ในกราฟที่ลากได้ จุดทุกจุดต้องมีดีกรีเป็นเลขคู่
          ข้อน่าคิดต่อไปก็คือ บทกลับของข้อสรุปข้างบนนี้เป็นจริงหรือไม่  คือถ้ากราฟรูปหนึ่งมีแต่จุดที่มีดีกรีเป็นเลขคู่ กราฟรูปนั้นจำต้องเป็นกราฟที่ลากได้เสมอไปหรือไม่ เราจะพบว่าบทกลับนี้ไม่จำเป็นต้องเป็นจริงเสมอไป เช่น ถ้าสะพานเชื่อมโยงเกาะกับฝั่ง ดังรูป          
          เราจะพบว่ากราฟแสดงการเชื่อมโยงแผ่นดินทั้งสี่ด้วยสะพาน เป็นกราฟซึ่งแต่ละจุดมีดีกรีที่ 2 แต่กราฟนี้มิได้เป็นรูปที่ติดต่อเป็นชิ้นเดียวกัน จึงไม่เป็นกราฟที่ลากได้  ดังนั้นคุณสมบัติอีกอย่างหนึ่ง ซึ่งกราฟที่ลากได้จะต้องมีเสมอไปก็คือ การมีลักษณะติดต่อเป็นชิ้นเดียว
          ทฤษฎีบทว่าด้วยกราฟที่ลากได้ ซึ่งออยเลอร์พิสูจน์ไว้กล่าวว่า กราฟรูปหนึ่งรูปใด จะเป็นกราฟที่ลากได้ก็ต่อเมื่อกราฟนั้นติดต่อเป็นชิ้นเดียว และจุดทุกจุดมีดีกรีคู่เท่านั้น ปัจจุบันนี้เราเรียกกราฟเช่นนี้ว่า กราฟแบบออยเลอเรียน (Eulerien)
          ปัญหาเกี่ยวกับการลากทับรอยเส้นกราฟอีกประเภทหนึ่ง ซึ่งคล้ายกับปัญหาข้างต้น ปัญหาประเภทนี้มีว่า เราจะลากทับรอยเส้นกราฟไปเรื่อยๆ โดยให้ผ่านจุดต่างๆ  ของกราฟนั้นทุกจุด จุดละครั้งเดียว แล้วในที่สุดกลับมาบรรจบที่จุดเดิมได้หรือไม่  ถ้าเราลองพิจารณากราฟในรูป  ก. ข. ค. ในตัวอย่างข้างต้น เราจะพบว่ากราฟรูป ก. กับ ค. นั้นเราทำได้ ส่วนกราฟรูป  ข. นั้น เราจะลากไม่ได้ วิธีลากทับรอยกราฟ  รูป ค. ให้ผ่านทุกจุด จุดละครั้งเดียว และกลับมาถึงจุดเดิมนั้นเราอาจทำได้ตามวิธีใดวิธีหนึ่ง  ดังแสดงในรูป
          กราฟซึ่งเราสามารถลากทับรอยเส้นให้ผ่านทุกจุด จุดละครั้งเดียวและกลับมาบรรจบที่จุดเดิมได้ เราเรียกว่า กราฟแบบแฮมิลโทเนียน (Hamiltonian) ตามชื่อของเซอร์ วิลเลี่ยม โรแวน แฮมิลทัน นักคณิตศาสตร์ชาวอังกฤษ ซึ่งเป็นผู้หยิบ
ปัญหาเช่นนี้ขึ้นพิจารณา สาเหตุที่ทำให้เราลากให้ผ่านทุกจุดของกราฟ ข. จุดละครั้งเดียวไม่ได้ก็คือจุดๆ หนึ่งในกราฟรูปนี้มีคุณสมบัติพิเศษบางประการ ในรูปกราฟ ข. นี้  หากเราลบจุดหมายเลข 3 และลบทุกเส้นที่ต่อกับจุดนี้ออกเสีย เราจะได้กราฟที่เป็นสองส่วนแยกจากกัน เราเรียกจุดเช่นนี้ว่า จุดตัด จุดตัดจึงเป็นทางผ่านเพียงทางเดียว ที่เชื่อมต่อกราฟสองชิ้น ถ้าเริ่มต้นจากจากจุดใดจุดหนึ่งแล้วลากให้ผ่านทุกๆ จุด  ในกราฟเราย่อมต้องลากผ่านจุดตัดถึงสองครั้งเป็นอย่างหนึ่ง เราจึงสรุปได้ว่ากราฟที่มีจุดตัดย่อม ไม่เป็นกราฟแบบแฮมิลโทเนียน บทกลับของข้อสรุปนี้ไม่เป็นจริง กล่าวคือกราฟที่ไม่มีจุดตัดเลย แต่ไม่เป็นกราฟแบบแฮมิลโทเนียนก็มี 
          นักคณิตศาสตร์ยุคปัจจุบัน ได้พยายามค้นหาเงื่อนไขที่สะดวกต่อการใช้เป็นเกณฑ์พิจารณาว่ากราฟรูปใดรูปหนึ่งเป็นกราฟแบบแฮมิลโทเนียนหรือไม่ แต่ก็ยังไม่มีผู้ใดค้นพบเงื่อนไขที่ดีเท่าเทียมกับเงื่อนไขที่ใช้ในการพิจารณาว่า กราฟเป็นแบบออยเลอเรียนหรือไม่ เช่น มีผู้พบว่ากราฟใดๆ ที่มีสามจุดขึ้นไปและติดต่อกันเป็นชิ้นเดียว ถ้าผลรวมของดีกรีของจุด ที่ไม่ได้อยู่ติดกันแต่ละคู่ไม่น้อยกว่าจำนวนจุดทั้งหมดในกราฟนั้น กราฟนั้นย่อมเป็นแบบแฮมิลโทเนียน ส่วนที่ยังไม่ค่อยจะดีนักของทฤษฎีบทนี้ก็คือ เราไม่สามารถใช้ทฤษฎีบทนี้เพียงบทเดียว ตรวจสอบว่ากราฟเป็นแบบแฮมิลโทนเนียนหรือไม่ได้ทุกรูป เพราะกราฟแบบแฮมิลโทเนียนบางรูปที่ไม่เป็นไปตามเงื่อนไขของทฤษฎีบทนี้ก็มี เช่น รูปทางซ้ายมือ เป็นกราฟแบบแฮมิลโทเนียน ซึ่งจุดคู่ที่ห่างกันมีดีกรีรวมกันได้น้อยกว่าจำนวนของจุดในรูป

กราฟแสดงสะพานในเมืองเคอนิกสเบอร์ก


กราฟ ข.


กราฟที่ไม่มีจุดตัดเลย


กราฟแบบแฮมิลโทเนียน

[ดูภาพทั้งหมดในเรื่องนี้]


บรรณานุกรม
นายวิรุฬห์ บุญสมบัติ


TAGS ที่เกี่ยวข้อง >> เรื่องของกราฟ << คลิกอ่านเพิ่มเติม

Advertisement

≡ เรื่องอื่นๆ ที่น่าอ่าน ≡

จำนวนตรรกยะ

จำนวนตรรกยะ
เปิดอ่าน 32,070 ครั้ง
ปีอธิกสุรทิน

ปีอธิกสุรทิน
เปิดอ่าน 37,619 ครั้ง
ประวัติย่อของคณิตศาสตร์ : ฟริดริก เกาส์

ประวัติย่อของคณิตศาสตร์ : ฟริดริก เกาส์
เปิดอ่าน 25,395 ครั้ง
จำนวนเฉพาะ (Prime Number) คืออะไร?

จำนวนเฉพาะ (Prime Number) คืออะไร?
เปิดอ่าน 84,993 ครั้ง
ประวัติเครื่องหมายหาร  (÷)

ประวัติเครื่องหมายหาร (÷)
เปิดอ่าน 222,319 ครั้ง
ประวัติย่อของคณิตศาสตร์ : อาร์คีมีดีส : Archimedes

ประวัติย่อของคณิตศาสตร์ : อาร์คีมีดีส : Archimedes
เปิดอ่าน 34,718 ครั้ง
ดาวน์โหลดที่นี่ แบบฝึกหัดเพื่อพัฒนาทักษะการคิดเลขเร็ว  ชั้นประถมศึกษาปีที่ 1 - 6 เริ่มใช้ภาคเรียนที่ 1/2559

ดาวน์โหลดที่นี่ แบบฝึกหัดเพื่อพัฒนาทักษะการคิดเลขเร็ว ชั้นประถมศึกษาปีที่ 1 - 6 เริ่มใช้ภาคเรียนที่ 1/2559
เปิดอ่าน 131,261 ครั้ง
การพิจารณาค่าความจริง (Truth value)

การพิจารณาค่าความจริง (Truth value)
เปิดอ่าน 15,650 ครั้ง
การวัดระยะบนผิวทรงกลม

การวัดระยะบนผิวทรงกลม
เปิดอ่าน 19,755 ครั้ง
เทคนิคการคูณเลข

เทคนิคการคูณเลข
เปิดอ่าน 2,886 ครั้ง
วิธีนี้ดีนะ..คณิตฯ ประถม ลบเลขไม่ต้องยืม

วิธีนี้ดีนะ..คณิตฯ ประถม ลบเลขไม่ต้องยืม
เปิดอ่าน 49,914 ครั้ง
แบบฝึกเพื่อพัฒนาทักษะการคิดเลขเร็ว ชั้นประถมศึกษาปีที่ 1-3

แบบฝึกเพื่อพัฒนาทักษะการคิดเลขเร็ว ชั้นประถมศึกษาปีที่ 1-3
เปิดอ่าน 9,287 ครั้ง
ใช้หมากรุกเป็นวิชา แก้ตกเลขซ้ำซาก

ใช้หมากรุกเป็นวิชา แก้ตกเลขซ้ำซาก
เปิดอ่าน 12,793 ครั้ง
สูตรลูกบิด สูตรรูบิค Rubik

สูตรลูกบิด สูตรรูบิค Rubik's Cube
เปิดอ่าน 140,769 ครั้ง
สูตรปริมาตรทรงกระบอก

สูตรปริมาตรทรงกระบอก
เปิดอ่าน 33,339 ครั้ง

:: เรื่องปักหมุด ::

วีดิทัศน์ประกอบการสอนคณิตศาสตร์ชั้น ป.5 โดย สสวท.
วีดิทัศน์ประกอบการสอนคณิตศาสตร์ชั้น ป.5 โดย สสวท.
เปิดอ่าน 17,299 ☕ คลิกอ่านเลย

Advertisement

≡ เรื่องน่าสนใจในหมวดหมู่นี้ ≡
โครงงานคณิตศาสตร์
โครงงานคณิตศาสตร์
เปิดอ่าน 128,022 ☕ คลิกอ่านเลย

สรุปสูตรวงรี
สรุปสูตรวงรี
เปิดอ่าน 81,010 ☕ คลิกอ่านเลย

ความน่าจะเป็น
ความน่าจะเป็น
เปิดอ่าน 73,938 ☕ คลิกอ่านเลย

เคล็ดเด็กเก่งวิชา เรขาคณิต-พีชคณิต
เคล็ดเด็กเก่งวิชา เรขาคณิต-พีชคณิต
เปิดอ่าน 18,773 ☕ คลิกอ่านเลย

โจทย์เลขสิงคโปร์ป่วนเน็ต หาคำตอบกันทั้งโลก
โจทย์เลขสิงคโปร์ป่วนเน็ต หาคำตอบกันทั้งโลก
เปิดอ่าน 16,809 ☕ คลิกอ่านเลย

การหาพื้นที่ผิวของร่างกาย
การหาพื้นที่ผิวของร่างกาย
เปิดอ่าน 45,180 ☕ คลิกอ่านเลย

≡ เรื่องน่าอ่าน/สาระน่ารู้ ≡

ขนมเสริมมงคล 12 ราศี
ขนมเสริมมงคล 12 ราศี
เปิดอ่าน 13,600 ครั้ง

ตะไคร้สมุนไพรใกล้ตัวแก้เวียนหัว
ตะไคร้สมุนไพรใกล้ตัวแก้เวียนหัว
เปิดอ่าน 28,081 ครั้ง

ลูกชิดกับลูกจาก มาจากไหน
ลูกชิดกับลูกจาก มาจากไหน
เปิดอ่าน 59,236 ครั้ง

วิธีปฐมพยาบาลคนเป็นลม
วิธีปฐมพยาบาลคนเป็นลม
เปิดอ่าน 80,509 ครั้ง

อ้างพบธาตุหนักที่สุดมีเลขอะตอม 122
อ้างพบธาตุหนักที่สุดมีเลขอะตอม 122
เปิดอ่าน 13,851 ครั้ง

เกมส์ รวมเกมส์สนุกๆ มากมาย
สนามเด็กเล่น

แหล่งรวมเกมส์ เกมส์ให้เล่นมากมาย ศูนย์รวมเกมส์สนุกๆ เกมส์ความรู้ เกมส์ลับสมอง เกมส์ประลองยุทธ แหล่งรวบรวมข้อมูล เกมส์ เกมส์ออนไลน์ เกมส์มันๆ เกมส์ตัดผม ไว้มากมายที่นี่ ให้เด็กๆได้เลือกเล่นมากมาย คลิกเลย


เว็บไซต์ที่น่าสนใจ

  • IELTS Test
  • SAT Test
  • สอบ IELTS
  • สอบ TOEIC
  • สอบ SAT
  • เว็บไซต์พันธมิตร

  • IELTS
  • TOEIC Online
  • chulatutor
  • เพลงเด็กอนุบาล
  •  
    หมวดหมู่เนื้อหา
    เนื้อหา แยกตามหมวดหมู่ สามารถเลืออ่านได้ตามหมวดหมู่ที่นี่


    · Technology
    · บทความเทคโนโลยีการศึกษา
    · e-Learning
    · Graphics & Multimedia
    · OpenSource & Freeware
    · ซอฟต์แวร์แนะนำ
    · การถ่ายภาพ
    · Hot Issue
    · Research Library
    · Questions in ETC
    · แวดวงนักเทคโนฯ

    · ความรู้ทั่วไป
    · คณิตศาสตร์
    · วิทยาศาสตร์และเทคโนโลยี
    · ภาษาต่างประเทศ
    · ภาษาไทย
    · สุขศึกษาและพลศึกษา
    · สังคมศึกษา ศาสนาฯ
    · ศิลปศึกษาและดนตรี
    · การงานอาชีพ

    · ข่าวการศึกษา
    · ข่าวตามกระแสสังคม
    · งาน/บริการสังคม
    · คลิปวิดีโอยอดนิยม
    · เกมส์
    · เกมส์ฝึกสมอง

    · ทฤษฎีทางการศึกษา
    · บทความการศึกษา
    · การวิจัยทางการศึกษา
    · คุณครูควรรู้ไว้
    · เตรียมประเมินวิทยฐานะ
    · ผลงานวิชาการเล่มเต็ม
    · เครื่องมือสำหรับครู

    ครูบ้านนอกดอทคอม

    เว็บไซต์เพื่อครู ข่าวการศึกษา ความรู้ การศึกษาไทย

          kroobannok.com

    © 2000-2020 Kroobannok.com  
    All rights reserved.


    Design by : kroobannok.com


    ครูบ้านนอกดอทคอม
    การจัดอันดับของ Truehits Web Directory

    วิธีนำแบนเนอร์ของครูบ้านนอก.คอมไปแปะในเว็บท่าน บันทึกภาพแบนเนอร์นี้และลิงค์มาที่เราครับ (มีแบนเนอร์ 2 แบบ)
     

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

    เว็บนี้ถือกำเนิดเมื่อ 5 มกราคม 2548

    Email : kornkham@hotmail.com
    Tel : 081-3431047

    สนใจสนับสนุนเรา โดยลงโฆษณา
    คลิกดูรายละเอียดที่นี่ครับ