กราฟ

จุดกำเนิดของทฤษฎีกราฟ

• ทฤษฎีกราฟ เกิดขึ้นเมื่อ ค.ศ. 1736 โดยนักคณิตศาสตร์ชาว สวิสเซอร์แลนด์ ชื่อ เลออนฮาร์ด ออยเลอร์ (Leonhard Euler)

• ออยเลอร์ ได้สร้างทฤษฎีที่เรียกว่า “ทฤษฎีออยเลอร์” (ทฤษฎีกราฟ) ขึ้นมาเพื่อแก้ปัญหาสะพานเคอนิกส์เบอร์ก “Konigsberg Bridge Problem” ได้เป็นผลสำเร็จ

• ดังนั้น เลออนฮาร์ด ออยเลอร์ จึงได้ชื่อว่าเป็นบิดาของทฤษฎีกราฟ จุดกำเนิดของทฤษฎีกราฟ

• ปัญหาสะพานเคอนิกส์เบอร์ก มีเกาะ 2 เกาะ อยู่กลางแม่น้ำพรีเกล (Pregel) ในเมืองเคอนิกส์เบอร์ก (ปัจจุบันเปลี่ยนชื่อเป็น คาลินิการ์ด: Kalinigrad) ระหว่างเกาะกับแผ่นดิน ดังรูปมีสะพาน 7 สะพาน เชื่อม

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

• ออยเลอร์ได้ไขปริศนานี้โดยแปลงปัญหาดังกล่าวเป็นกราฟโดยให้พื้นดิน แทนจุดยอด และสะพานแทนด้วยเส้นเชื่อม ดังรูป 

• ออยเลอร์สามารถพิสูจน์ยืนยันคำตอบว่าเป็นไปไม่ได้้ที่จะหาเส้นทาง ดังกล่าว

• จะมีเส้นทางดังกล่าวได้ก็ต่อเมื่อกราฟนั้นจะต้องต่อเนื่องและมีจำนวนเส้นของแต่ละจุดเป็นจำนวนคู่

บทนิยาม กราฟ G ประกอบด้วย เซตจำกัด 2 เซต คือ  1. เซตที่ไม่เป็นเซตว่างของจุดยอด (Vertex) แทนด้วยสัญลักษณ์ V(G)  2. เซตของเส้นเชื่อม (Edge) ที่เชื่อมระหว่างจุดยอด แทนด้วยสัญลักษณ์ E(G)

ข้อสังเกต V(G) ≠ ∅ แต่ E(G) อาจเป็นเซตว่างได้

ตัวอย่างของกราฟ

  

 บทนิยาม เส้นเชื่อมตั้งแต่ 2 เส้นที่เชื่อมระหว่างจุดยอดคู่เดียวกัน เรียกว่า

เส้นเชื่อมขนาน(Parallel Edges)   เส้นเชื่อมที่เชื่อมจุดยอดเพียงจุดเดียว เรียกว่า วงวน (Loop) 

จากรูปข้างต้นจะเห็นว่า 

                    e₁ และ e₂ เป็น เส้นเชื่อมขนาน เส้นเชื่อม e₅ เป็นวงวน  ในกรณีที่กราฟไม่มีเส้นเชื่อมขนาน สามารถใช้สัญลักษณ์ 

         AB เพื่อแทนเส้นเชื่อมระหว่างจุดยอด A และ B ได้ เช่น กราฟในตัวอย่างที่ 1 สามารถเขียนเซตของเส้นเชื่อม E(G)

     ได้ใหม่เป็น E(G) = {AB, BC, AC, CD}

ตัวอย่าง จุดยอดประชิด

จากกราฟของตัวอย่างที่ 1 จะเห็นว่า

                                จุดยอด A และจุดยอด B เป็นจุดยอดประชิด

                                จุดยอด A และจุดยอด C เป็นจุดยอดประชิด

                                จุดยอด B และจุดยอด C เป็นจุดยอดประชิด

                                จุดยอด C และจุดยอด D เป็นจุดยอดประชิด

                                แต่  จุดยอด A และจุดยอด D ไม่เป็นจุดยอดประชิด

                                       จุดยอด B และจุดยอด D ไม่เป็นจุดยอดประชิด