ความรู้ทางคณิตศาสตร์

ทฤษฎีกราฟ
บทนิยามของกราฟ
กราฟ เป็นเรื่องที่สำคัญเรื่องหนึ่งในสาขาวิชาวิยุตคณิต (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 vertex)
ถ้า deg(v) เป็นจำนวนคี่ เราเรียก v ว่าจุดคี่ (odd vertex)
ทฤษฎีบท 1

ให้ G = (V(G), E(G)) แทนกราฟ โดย V(G) = p และ E(G) = q
ซึ่ง V(G) = {v1, v2, ..., vp } และ E(G) = { e1, e2, ...., eq } จะได้ว่า
P
å deg (v i ) = 2 E(G)
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 : v0 , e1 , v1 , e2 , v2 , ....., vn-1 , en , vn
ซึ่งเส้น ei มีจุดปลาย คือ vi-1 และ vi สำหรับ 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) = { v1 , v2 , ...., vn} เป็นเซตของจุดในกราฟ เมื่อ n = V(G) เมทริกซ์ประชิดของ G เขียนแทนด้วย A(G) จะเป็นเมทริกซ์มีมิติ n x n และ A(G) = [aij ] โดยที่ aij เป็นจำนวนของเส้นที่เชื่อมจุด vi และ vj
ทฤษฎีบท 3
ให้ V(G) = { v1 , v2 , ... , vn} เป็นเซตของจุดในกราฟ G และ A = A(G) เป็นเมทริกซ์ประชิดของ G แล้วสมาชิก aij ของ Ak , k ³ 1 จะเป็นจำนวนของแนวเดิน vi – vj ที่มีความยาว k ที่แตกต่างกันใน G
บทนิยาม 12
เมทริกซ์ตกกระทบ (incidence matrix)
ให้ V(G) = { v1 , v2 , ... , vn} และ E(G) = { e1 , e2 , ... , em} เป็นเซตของจุดและเซตของเส้นในกราฟ G เมื่อ n = V(G) และ m = E(G)
เมทริกซ์ตกกระทบ (incidence matrix) ของกราฟ G เขียนแทนด้วย I(G) จะเป็นเมทริกซ์มีมิติ n x m และ I(G) = [ xij ] โดยที่ xij เป็นจำนวนครั้งที่จุด vi ตกกระทบกับเส้น ej ซึ่ง xij มีค่าดังนี้
0 ถ้า vi ไม่เป็นจุดปลายของเส้น ej
xij = 1 ถ้า vi เป็นจุดปลายของเส้น ei ที่ไม่เป็นวงวน
2 ถ้า vi เป็นจุดปลายของเส้น ei ที่เป็นวงวน
บทนิยาม 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 จุด ยิ่งไปกว่านั้นจุดคี่เหล่านี้จะเป็นจุดเริ่มต้นและจุดปลายของรอยเดินเปิดออยเลอร์

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

อ้างอิง
http://www.punarworn.com/view.asp?ccode=2507
http://images.google.co.th/imgres