ทฤษฎีกราฟของออยเลอร์

บทนิยามของกราฟ

      กราฟ เป็นเรื่องที่สำคัญเรื่องหนึ่งในสาขาวิชาวิยุตคณิต (Discrete mathematics) กราฟในที่นี้จะกล่าวถึงความสัมพันธ์ของจุด และเส้นที่เชื่อมระหว่างจุด เช่น แผนที่ถนนเชื่อมระหว่างเมืองต่าง ๆ แผนที่แสดงเส้นทางการบิน และจากตัวอย่างการแก้ปัญหาโดยใช้จุดและเส้นเป็นแบบจำลองที่กล่าวมาข้างต้น เป็นต้น ซึ่งจะให้ความหมายดังนิยามต่อไปนี้
บทนิยาม 1 กราฟจำกัด G คือคู่อันดับ (V(G)) ประกอบไปด้วยเซตจำกัด 2 เซต

1. V(G) เป็นเซตของจุดที่ไม่เป็นเซตว่าง ถ้าu เป็นสมาชิกใน V(G) เรียก u ว่าจุด (vertex)

2. E(G) เป็นเซตของเส้น ซึ่งเส้นแต่ละเส้น คือ คู่ที่ไม่เป็นอันดับ (unordered pair) ของจุด ที่เขียนอยู่ในรูป uv เรียก uv ว่า เส้น (edge)

บทนิยาม 2

1. เส้นที่มีจุดปลายทั้งสองเป็นจุดเดียวกัน เราเรียกว่า วงวน (loop)
2. เส้นตั้งแต่สองเส้นขึ้นไปที่เชื่อมจุดคู่เดียวกัน เราเรียกว่า เส้นหลายชั้น (multiple edges)
3. กราฟที่ไม่มีเส้นหลายชั้นและไม่มีวงวน เราเรียกว่า กราฟเชิงเดียว (Simple graph)
บทนิยาม 3 กำหนดกราฟ G = (V(G), D(G)) และ v Î V(G) ระดับขั้น (degree) ของ v คือจำนวนเส้นใน E(G) ที่ตกกระทบกับจุด v เราเขียน deg(v) แทนระดับขั้นของ v

(จำนวนเส้น ใน E(G) ที่ตกกระทบกับจุด v คือ จำนวนเส้นใน E(G) ที่ออกจาก จุด v นั่นเอง)

ถ้า deg(v)   เป็นจำนวนคู่ เราเรียก v ว่าจุดคู่ (even verte)
ถ้า deg(v)   เป็นจำนวนคี่ เราเรียก v ว่าจุดคี่ (odd vertex)

ทฤษฎีบท 1 ให้ G = (V(G), E(G)) แทนกราฟ โดย | V(G)| = p และ | E(G) | = q
ซึ่ง V(G) = {v₁, v₂, ..., v_p } และ E(G) = { e₁, e₂, ...., e_q } จะได้ว่า
 P
å deg (v _i ) =   2| E(G) |
E(i=1
บทแทรก 1 กราฟทุกกราฟจะมีจุดคี่เป็นจำนวนคู่
บทนิยาม 4 ให้ H = (V(H)), E(H)) และ G = (V(G)), E(G)) เป็นกราฟใด ๆ
1. ถ้า V(H) Ì V(G) และ E(H) Ì E(G)
เรากล่าวว่า H เป็นสับกราฟ (subgraph) ของ G
 2. ถ้า H เป็นสับกราฟของ G และ V(H) = V(G
เรากล่าวว่า H เป็นสับกราฟแผ่ทั่วถึง (spanning subgraph) ของ G
3. ถ้า V(H) = V(G) และ E(H) = E(G)
เรากล่าวว่า กราฟ H และกราฟ G เป็นกราฟเหมือนกัน (identical) เขียนแทน H = G
บทนิยาม 5 ให้ G = (V(G), E(G)) เป็นกราฟใด ๆ
  1. ถ้า U เป็นเซตของจุดที่ไม่เป็นเซตว่าง และเป็นสับเซตแท้ของ V(G) แล้ว G – U เป็นสับกราฟของ G ที่ได้จากการกำจัดจุดใน U และเส้นทุกเส้นที่ตกกระทบกับจุดแต่ละจุดใน U
  2. ถ้า F เป็นเซตของเส้นที่ไม่เป็นเซตว่าง และเป็นสับเซตของ E(G) แล้ว G – F คือสับกราฟของ G ที่ได้จากการกำจัดเส้นใน F โดยที่ไม่มีผลต่อจุด
บทนิยาม 6 แนวเดิน (Walk) W ในกราฟ G คือ ลำดับสลับของจุดและเส้นของกราฟ G ดังนี้
W : v₀ , e₁ , v₁ , e₂ , v₂ , ....., v_n-1 , e_n , v_n
ซึ่งเส้น e_i มีจุดปลาย คือ v_i-1 และ v_i สำหรับ 1 £ i £ n
บทนิยาม 7 ให้ v เป็นจุดใด ๆ ในกราฟ G และ W เป็นแนวเดินใน G โดยที่
W : v (ซึ่งมีความยาว = 0)
เราเรียกแนวเดิน W ที่ไม่มีเส้น (n = 0) ว่าแนวเดินชัด (trival walk)

บทนิยาม 8 ให้ u และ v เป็นจุดใด ๆ ในกราฟ G

เรากล่าวว่าแนวเดิน u – v เป็น แนวเดินปิด (closed walk) เมื่อ u = v

และ แนวเดิน u – v เป็นแนวเดินเปิด (open walk) เมื่อ u ¹ v

บทนิยาม 9

1. ถ้าเส้นในแนวเดิน u – v ไม่ซ้ำกัน เรากล่าวว่าแนวเดิน u – v เป็นรอยเดิน (trail)

2. ถ้าจุดในแนวเดิน u – v ไม่ซ้ำกัน เรากล่าวว่าแนวเดิน u – v เป็นวิถี (path)

ทฤษฎีบท 2 ให้ u และ v เป็นจุดในกราฟ G ทุก ๆ แนวเดิน u – v จะมีวิถี u – v

บทนิยาม 10

1. เราเรียกรอยเดินปิดที่ไม่ใช่แนวเดินชัดว่า วง (circuit)

2. เราเรียก วงที่มีจุดเริ่มต้น และจุดภายในไม่ซ้ำกันว่า วัฏจักร (cycle)

บทนิยาม 11 เมทริกซ์ประชิด (adjacency matrix)

ให้ V(G) = { v₁ , v₂ , ...., v_n} เป็นเซตของจุดในกราฟ เมื่อ n = | V(G)| เมทริกซ์ประชิดของ G เขียนแทนด้วย A(G) จะเป็นเมทริกซ์มีมิติnxnและA(G) =[a_ij]โดยที่a_ijเป็นจำนวนของเส้นที่เชื่อมจุดv_iและ v_j                                                                                                                

ทฤษฎีบท 3 ให้ V(G) = { v₁ , v₂ , ... , v_n} เป็นเซตของจุดในกราฟ G และ A = A(G) เป็นเมทริกซ์ประชิดของ G แล้วสมาชิก a_ij ของ A^k , k ³ 1 จะเป็นจำนวนของแนวเดิน v_i – v_j ที่มีความยาว k ที่แตกต่างกันใน G

บทนิยาม 12 เมทริกซ์ตกกระทบ (incidence matrix)

ให้ V(G) = { v₁ , v₂ , ... , v_n} และ E(G) = { e₁ , e₂ , ... , e_m} เป็นเซตของจุดและเซตของเส้นในกราฟ G เมื่อ n = V(G)| และ m = | E(G)|

เมทริกซ์ตกกระทบ (incidence matrix) ของกราฟ G เขียนแทนด้วย I(G) จะเป็นเมทริกซ์มีมิติ n x m และ I(G) = [ x_ij ] โดยที่ x_ij เป็นจำนวนครั้งที่จุด v_i ตกกระทบกับเส้น e_j ซึ่ง x_ij มีค่าดังนี้

0 ถ้า v_i ไม่เป็นจุดปลายของเส้น e_j

x_ij = 1 ถ้า v_i เป็นจุดปลายของเส้น e_i ที่ไม่เป็นวงวน

2 ถ้า v_i เป็นจุดปลายของเส้น e_i ที่เป็นวงวน

บทนิยาม 13 ให้ u และ v เป็นจุดใด ๆ ในกราฟ G เรากล่าวว่า u และ v เชื่อมโยงกันได้ (connect) เมื่อมีวิถี u – v

13.1 ถ้ามีวิถีระหว่างจุดสองจุดใดๆ แล้วกราฟ G เป็นกราฟเชื่อมโยง (connected graph)

13.2 ถ้าไม่มีวิถีระหว่างจุดสองจุดใดๆ แล้วกราฟ G เป็นกราฟไม่เชื่อมโยง (disconnected graph)

บทนิยาม 14 ให้กราฟ G เป็นกราฟเชื่อมโยง และ v เป็นจุดในกราฟ G เรียก จุด v ว่า จุดตัด (cut vertex) ถ้ากราฟ G – v กลายเป็นกราฟไม่เชื่อมโยง

บทนิยาม 15 ให้กราฟ G เป็นกราฟเชื่อมโยง และ e เป็นเส้นในกราฟ G เรียก เส้น e ว่า เส้นตัด (cut edge) ถ้ากราฟ G – e กลายเป็นกราฟไม่เชื่อมโยง

บทนิยาม 16 เรากล่าวว่ากราฟ G เป็น กราฟที่มีน้ำหนัก เมื่อเส้นแต่ละเส้น e ใน G ถูกกำหนดด้วยจำนวนจริงที่ไม่เป็นลบ และเราเรียกจำนวนจริงดังกล่าวนี้ว่า น้ำหนักของเส้น e เขียนแทนด้วย w(e)

บทนิยาม 17 ความยาวของวิถีในกราฟที่มีน้ำหนัก G คือ ผลรวมของน้ำหนักของเส้นในวิถีนั้น

บทนิยาม 18 ให้ G เป็นกราฟเชื่อมโยงที่มีน้ำหนัก u และ v เป็นจุดยอดใน G ระยะทาง d(u, v) คือ ค่าความยาวของวิถี u – v ที่น้อยที่สุด

ทฤษฎีบท 1

1.1 ถ้ากราฟ G มีวงวน แล้วกราฟ G ไม่เป็นต้นไม้

1.2 ถ้ากราฟ G เป็นต้นไม้ แล้วจุด 2 จุดใด ๆ ใน G เชื่อมโยงกันได้ด้วย วิถีเพียงวิถีเดียว

1.3 ถ้ากราฟ G เป็นต้นไม้ ที่มีจุด n จุด แล้ว กราฟ G จะมีจำนวนเส้น n – 1 เส้น

1.4 ถ้ากราฟ G เป็นต้นไม้ ที่มีจุด n > 1 กราฟ G จะมีจุดที่มีดีกรี 1 อย่างน้อย 2 จุด

บทนิยาม 1 ให้ G เป็นกราฟเชื่อมโยง

เรากล่าวว่า G เป็นกราฟออยเลอร์ (Eulerian graph) เมื่อ G มีรอยเดินปิดซึ่งผ่านเส้นทุกเส้นใน G และเรียกรอยเดินปิดดังกล่าวนี้ว่า รอยเดินออยเลอร์หรือ วงออยเลอร์ (Eulerian circuit) 

ทฤษฎีบท 1 ให้ G เป็นกราฟเชื่อมโยง และ | E(G) | ³ 1

จะได้ว่า G เป็นกราฟออยเลอร์ ก็ต่อเมื่อ จุดทุกจุดใน G เป็นจุดคู่

บทนิยาม 2 ให้ G เป็นกราฟเชื่อมโยง เราเรียกรอยเดินเปิดใน G ว่า รอยเดินเปิดออยเลอร์ (Eulerian trail) เมื่อรอยเดินดังกล่าวนี้ผ่านเส้นทุกเส้นใน G

ทฤษฎีบท 2 ให้ G เป็นกราฟเชื่อมโยง G มีรอยเดินเปิดออยเลอร์ ก็ต่อเมื่อ G มีจุดที่เป็นจุดคี่ไม่เกิน 2 จุด ยิ่งไปกว่านั้นจุดคี่เหล่านี้จะเป็นจุดเริ่มต้นและจุดปลายของรอยเดินเปิดออยเลอร์