Please enable JavaScript.
Coggle requires JavaScript to display documents.
หน่วยที่ 5 ทฤษฎีกราฟ (Graphs Theory) :<3: (ชนิดของกราฟ…
หน่วยที่ 5 ทฤษฎีกราฟ (Graphs Theory)
:<3:
บทนำ
แนวคิดพื้นฐานของกราฟเริ่มต้นในศตวรรษที่ 18 โดย Leonhard Euler เพื่อแก้ปัญหา “Konigsberg Bridge Problem”
กราฟ คือ โครงสร้างที่แยกส่วนอย่างชัดเจน (Discrete structure) ซึ่งประกอบด้วยจุด (vertices) และเส้นเชื่อม (edges) ที่ต่อจุดต่างๆ เข้าด้วยกัน
ทางเดินที่สั้นที่สุด (Shortest-Path)
กราฟที่ใช้เพื่อแก้ปัญหาทางเดินที่สั้นที่สุดจะต้องมีตัวเลขกำกับที่แต่ละเส้นเชื่อม
อัลกอริทึมสำหรับการแก้ปัญหานี้มีหลากหลายอัลกอริทึม
สำหรับในวิชานี้จะศึกษาอัลกอริทึมที่ชื่อว่า "Dijkstra's Algorithm"คิดค้นโดย Edsger Wybe Dijkstra ในปีค.ศ. 1959
กราฟลักษณะนี้เรียกว่า “กราฟแบบมีน้ำหนัก (Weighted graphs)” : :
ชนิดของกราฟ
นิยามที่ 5.4 Directed graph (V, E)
V ซึ่งเป็นเซตของจุด
E ซึ่งเป็นคู่ลำดับของสมาชิกของ V
เส้นเชื่อม มีทิศทาง , มีหลายเส้นเชื่อม ไม่ได้, มีลูป ได้
นิยามที่ 5.3 Pseudograph G = (V, E)
ฟังก์ชัน f จาก E ไปยัง {{u, v} | u, v ∈ V}
โดยเส้นเชื่อมจะเป็น loop ถ้า f(e)={u,u}={u} สำหรับบางค่าของ u ∈ V
เส้นเชื่อม ไม่มีทิศทาง , มีหลายเส้นเชื่อม ได้, มีลูป ได้
นิยามที่ 5.5 Directed multigraph G = (V, E)
ฟังก์ชัน f จาก E ไปยัง {(u, v) | u, v ∈ V} แล้ว
เส้นเชื่อม e1 และ e2 จะเรียกว่า multiple edges ถ้า f(e1) = f(e2)
เส้นเชื่อม มีทิศทาง , มีหลายเส้นเชื่อม ได้, มีลูป ได้
นิยามที่ 5.2 Multigraph G = (V, E)
ฟังก์ชัน f จาก E ไปยัง {{u, v} | u, v ∈ V, u ≠ v}
เส้นเชื่อม e1 และ e2 จะเรียกว่า multiple หรือ parallel edges ถ้า f(e1) = f(e2)
เส้นเชื่อม ไม่มีทิศทาง , มีหลายเส้นเชื่อม ได้, มีลูป ไม่ได้
กราฟแบบสองส่วน (Bipartite Graphs)
นิยามที่ 5.6
Simple graph G จะเป็นกราฟแบบ 2 ส่วน (Bipartite graphs)
ถ้าเซตของจุด V สามารถที่จะแยกออกเป็น 2 เซตย่อยที่ไม่มีสมาชิกร่วมกัน (disjointset) คือ V1 และ V2
ซึ่งทุกๆ เส้นเชื่อมในกราฟจะเชื่อมต่อจุดหนึ่งใน V1 ไปยังจุดหนึ่งใน V2
ดังนั้นจะไม่มีเส้นเชื่อมที่เชื่อมต่อจุด 2 จุดใน V1 หรือเชื่อมต่อจุด 2 จุดใน V
นิยามที่ 5.1 Simple graph G = (V, E)
V ซึ่งเป็นเซตของจุด (Vertices) ที่ไม่ใช่เซตว่าง
E ซึ่งเป็นเซตของ unordered pairs ของแต่ละสมาชิกของ V เรียกว่าเส้นเชื่อม (Edges)
เส้นเชื่อม ไม่มีทิศทาง , มีหลายเส้นเชื่อม ไม่ได้, มีลูป ไม่ได้
Simple graph แบบพิเศษ
Complete graph
ที่มีจำนวน n จุด แทนด้วย Kn
Simple graph ที่มีเส้นเชื่อมเพียงเส้นเดียวระหว่างแต่ละคู่ของจุดที่แยกกัน
Cycle
แทนด้วย Cn โดย n ≥ 3
ประกอบด้วยจุดจำนวน n จุด คือ v1, v2, v3, ..., vn และมี
edges {v1, v2}, {v2, v3}, . . .,{vn-1, vn}, และ {vn, v1}
Wheel
แทนด้วย Wn
การเพิ่มจุดเข้าไปใน Cn (n ≥ 3) และเชื่อมต่อจุดใหม่นี้ไปยังแต่ละจุดเดิมใน Cn
n-Cube
กราฟที่มีจุดต่างๆ ซึ่งใช้แสดง bit string จำนวน 2n bit strings โดยที่ n คือ
จำนวนบิต ซึ่ง 2 จุดใดๆ จะต่อกันก็ต่อเมื่อ bit string ที่ใช้แสดงจุดนั้นต่างกัน 1 บิต
หรือลูกบาศก์ n มิติแทนด้วย Qn
คำศัพท์ที่เกี่ยวข้องกับกราฟ (Graph Terminology)
นิยามที่ 5.8
Degree
ของจุดๆ หนึ่งในกราฟแบบไม่มีทิศทาง
จำนวนของเส้นเชื่อมที่ต่อกับ จุดนั้นๆ กรณี loop ที่จุดนั้นจะนับ degree เป็น 2 โดย degree ของจุด v
เขียน แทนด้วย deg (v)
degree = 0 เรียกว่า "Isolated".
degree = 1 เรียกว่า "Pendant".
Handshaking Theorem
ทฤษฎีนี้สามารถใช้ได้กับกราฟที่มี multiple edges และ loops ด้วย
นิยามที่ 5.7
จุด 2 จุด คือ u และ v ในกราฟแบบไม่มีทิศทาง G จะเรียกว่า adjacent (หรือneighbors) ถ้า {u, v} เป็นเส้นเชื่อมของ G
และถ้า e = {u, v} จะเรียกเส้นเชื่อม e ว่า incident กับจุด u และ v
อาจกล่าวว่าเส้นเชื่อม e connect u และ v โดยจุด u และ v จะเรียกว่าเป็น endpoints ของเส้นเชื่อม {u, v}
นิยามที่ 5.9
เมื่อ (u, v) เป็นเส้นเชื่อมแบบมีทิศทางของกราฟ G
u adjacent to v และ v adjacent from u
เรียกจุด u ว่า จุดเริ่มต้น (initial vertex) ของ (u, v)
เรียก v ว่าเป็น จุดปลาย (terminal or end vertex) ของ (u, v)
ซึ่งในกรณีของ loop ทั้งจุดเริ่มต้นและจุดปลายจะเป็นจุดเดียวกัน
นิยามที่ 5.10
สำหรับกราฟแบบมีทิศทาง
out-degree ของจุด v ซึ่งแทนด้วย deg+ (v) จะมีค่าเท่ากับจำนวนของเส้นเชื่อมที่มี v เป็นจุดเริ่มต้น
in-degree เป็น 1 และ out-degree เป็น 1
in-degree ของจุด v ซึ่งแทนด้วย deg- (v) จะมีค่าเท่ากับจำนวนของเส้นเชื่อมที่มี v เป็นจุดปลาย
การพ้องรูปของกราฟ (Isomorphism of Graphs)
นิยามที่ 5.11
Simple graph G1 = (V1, E1) และ G2 = (V2, E2) จะพ้องรูปกัน (isomorphic)
ถ้ามีฟังก์ชัน f แบบ bijection จาก V1 ไปยัง V2 ที่มีคุณสมบัติ
a และ b จะเชื่อมต่อกัน (adjacent) ใน G1 ก็ต่อเมื่อ f(a) และ f(b)
เชื่อมต่อกันใน G2 สำหรับทุก a และ b ใน V1
simple graph 2 อันจะพ้องรูปกัน
มีฟังก์ชันแบบ bijection ระหว่างจุดของกราฟทั้ง 2 ซึ่งยังคงมีความสัมพันธ์แบบ adjacent กันอยู่ด้วย
การพิจารณาแบบง่ายจะพิจารณาจาก
จำนวนจุดเท่ากันหรือไม่
จำนวนเส้นเชื่อมเท่ากันหรือไม
จำนวนดีกรีของแต่ละจุดเท่ากันหรือไม่
ถ้าไม่เท่ากัน : กราฟทั้งสองไม่พ้องรูปกัน
ถ้าเท่ากัน : ต้องพิจารณาในรายละเอียดเพิ่มเติม
การเชื่อมต่อ (Connectivity)
ทางเดิน (Paths)
นิยามที่ 5.12
ให้ n เป็นจำนวนเต็มบวกและ G เป็นกราฟแบบไม่มีทิศทาง ทางเดินที่มีความยาว
n จากจุด u ไปยัง v ในกราฟ G คือลำดับของเส้นเชื่อมจำนวน n เส้น
ลำดับของเส้นเชื่อมจำนวน n เส้น คือ e1, e2 , . . ., en ของ G
ซึ่ง f(e1) = {x0, x1}, f(e2) = {x1, x2}, . . .,f(en) = {xn-1, xn} โดยที่ x0 = u และ xn =v
Informal definition คิอ ลำดับของเส้นเชื่อมที่เริ่มที่จุดๆ หนึ่งของกราฟและเดินทางไปตามเส้นเชื่อมต่างๆของกราฟซึ่งจะเชื่อมต่อคู่ของจุดที่ adjacent กันเสมอ
วงจร ทางเดินแบบง่าย และวงจรแบบง่าย
นิยามที่ 5.13
ทางเดินที่เริ่มต้นและจบที่จุดเดียวกันเรียกว่า “วงจร (Circuit)”
นิยามที่ 5.14
ทางเดินหรือวงจรจะเรียกว่าเป็น “ทางเดินแบบง่าย (Simple path) หรือวงจรแบบง่าย (Simple circuit)” เมื่อผ่านเส้นเชื่อมเดียวกันแค่ 1 ครั้งเท่านั้น
การเชื่อมต่อกันในกราฟแบบไม่มีทิศทาง
(Connectedness in undirected graphs)
นิยามที่ 5.15
กราฟแบบไม่มีทิศทางจะกล่าวว่า “ถูกเชื่อมต่อกัน (connected)” ถ้ามีทางเดิน
ระหว่างทุกๆ คู่ของจุดในกราฟ
กราฟที่ไม่เชื่อมต่อกัน
ประกอบด้วย connected subgraphs ตั้งแต่ 2 subgraphs ขึ้นไป
แต่ละ connected subgraphs จะเรียกว่า "Connected components" ของกราฟ
การเชื่อมต่อกันในกราฟแบบมีทิศทาง (Connectedness in directedgraphs)
นิยามที่ 5.16
กราฟแบบมีทิศทางจะเป็น strongly connected ถ้ามีทางเดินจาก a ไป b และ จาก b ไป a เมื่อใดก็ตามที่ a และ b เป็นจุดในกราฟ
นิยามที่ 5.17
กราฟแบบมีทิศทางจะเป็น weakly connected ถ้ามีทางเดินระหว่างทุกๆ
คู่ของจุดในกราฟ โดยไม่สนใจทิศทาง
ทางเดินและการพ้องรูปกันของกราฟ (Paths and Isomorphism)
ทางเดินและวงจรจะช่วยในการพิจารณาว่ากราฟ 2 กราฟจะพ้องรูปกันหรือไม
สามารถพิจารณา ได้โดย ขั้นตอน ดังนี้
จำนวนของจุด
จำนวนของเส้นเชื่อม
ดีกรีของจุดต่างๆ
ความยาวของวงจรแบบง่าย
ทางเดินแบบง่ายที่ผ่านทุกจุด
ทางเดินและวงจรออยเลอร์ (Euler Paths and Circuits)
นิยามที่ 5.18
ทางเดินออยเลอร์ (Euler path) ในกราฟ G คือ ทางเดินแบบง่ายที่ประกอบด้วย
ทุกๆ เส้นเชื่อมของกราฟ G
วงจรออยเลอร์ (Euler circuit) ในกราฟ G คือ วงจรแบบง่ายที่ประกอบด้วยทุกๆ
เส้นเชื่อมของกราฟ G
Theorems
Theorems 4
Connected multigraph ใดๆ จะมีวงจรออยเลอร์ก็ต่อเมื่อทุกจุดของกราฟมี
ดีกรีเป็นคู่
Theorems 5
Connected multigraph ใดๆ จะมีทางเดินออยเลอร์แต่ไม่มีวงจรออยเลอร์ก็
ต่อเมื่อมีเพียง 2 จุดของกราฟเท่านั้นที่มีดีกรีเป็นคี่
ทางเดินและวงจรฮามิลตัน (Hamilton Paths and Circuits)
นิยามที่ 5.19
ถ้า v ผ่านทุกจุดโดยไม่ซ้ำจุดเดิม จะเป็น ทางเดิน ฮามิลตัน
ถ้าสามารถหาทางเดินฮามิลตันได้ ผ่านทุกจุดแค่ 1 ครั้ง และสามารถกลับมาจุดเดิมได้ จะเป็นวงจรฮามิลตัน
คุณสมบัติบางประการของกราฟที่ไม่มีวงจรฮามิลตัน
ถ้าจุดใดในกราฟที่มีดีกรีเท่ากับ 2 แล้ว เส้นเชื่อมทั้ง 2 ที่ต่อกับจุดดังกล่าวไม่
ได้เป็นส่วนหนึ่งของวงจรฮามิลตัน
วงจรฮามิลตันจะไม่มีวงจรฮามิลตันอยู่ภายใน
กราฟที่มีจุดซึ่งมีดีกรีเท่ากับ 1
กราฟแบบระนาบ (Planar Graphs)
นิยามที่ 5.20
กราฟใดๆ จะเป็นกราฟแบบระนาบ ถ้าสามารถวาดกราฟโดยที่ไม่มีเส้นเชื่อมใดตัดกัน
การคล้ายรูปกันของกราฟ
กราฟ 2 รูปจะคล้ายรูปกันก็ต่อเมื่อกราฟรูปหนึ่งสามารถเปลี่ยนเป็นกราฟอีกรูปหนึ่งได้
การเติมจุดซึ่งมีดีกรีเท่ากับสองในเส้นเชื่อมเดิม
การลบจุดเดิมที่มีดีกรีเป็น 2 ออก
คุณสมบัติบางประการของ K3, 3 และ K5
กราฟทั้งสองเป็นกราฟแบบไม่ระนาบ (Nonplanar graph)
ถ้าลบเส้นเชื่อมเส้นใดเส้นหนึ่งออกจากกราฟจะทำให้เป็นกราฟแบบระนาบได้
กราฟทั้งสองเป็นกราฟที่มีดีกรีของทุกๆ จุดในกราฟเท่ากัน
K5 เป็นกราฟแบบไม่ระนาบซึ่งมีจำนวนจุดน้อยที่สุด
K3, 3 เป็นกราฟแบบไม่ระนาบที่มีจำนวนเส้นเชื่อมน้อยที่สุด
ทั้ง K5 และ K3, 3 เป็นกราฟแบบไม่ระนาบที่มีรูปแบบซับซ้อนน้อยที่สุด
ทฤษฎีที่ 6
กราฟใดๆ ก็ตามที่ประกอบด้วยกราฟย่อยซึ่งคล้ายรูป (Homeomorphic) กับ กราฟ K5 และ K3, 3 ก็จะเป็นกราฟแบบไม่ระนาบด้วย
การตรวจสอบว่าเป็นกราฟแบบระนาบหรือไม่
ลบเส้นเชื่อมที่ขนานกันระหว่างคู่ของจุดออกให้เหลือเพียง 1 เส้น
ค้นหาและวาดวงจรแบบง่ายซึ่งใช้เส้นเชื่อมมากที่สุด
รวมเส้นเชื่อมที่ต่อแบบอนุกรมกันเป็นเส้นเชื่อมเดียว
วาดเส้นเชื่อมและจุดที่เหลือซึ่งไม่ได้อยู่ในวงจรแบบง่ายโดยพยายามหลีกเลี่ยงการตัดกันของเส้นเชื่อม
ลบเส้นเชื่อมแบบลูปออก
หากไม่สามารถหลีกเลี่ยงได้ก็ให้หากราฟย่อยที่คล้ายรูปกับ K5 หรือ K3, 3 เพื่อยืนยันว่ากราฟดังกล่าวเป็นกราฟแบบไม่ระนาบ
การให้สีกราฟ (Graph Colouring)
นิยามที่ 5.21
การให้สีกราฟ คือ การกำหนดสีให้แต่ละจุดของกราฟโดย 2 จุดที่เชื่อมติดกัน (adjacent) ต้องไม่มีสีเดียวกัน
การประยุกต์ใช้งาน
แก้ปัญหาที่เกี่ยวข้องกับการจัดตาราง
จัดกำหนดการต่างๆ
การให้สีกราฟนั้นจะพยายามใช้สีให้น้อยที่สุด
จำนวนสีอย่างน้อยที่ต้องใช้ในการให้สีกราฟใดๆ เรียกว่า “Chromatic number of a graph”
การนำ ทฤษฎีกราฟ มาประยุกต์ใช้ในงานด้านคอมพิวเตอร์
เพิ่มประสิทธิภาพของ อัลกอริทึม โดยลดเวลาในการค้นหาข้อมูล
แผนภาพเครือข่ายคอมพิวเตอร์
สามารถนำ กราฟไปใช้ในการเขียนระบบ โครงสร้างข้อมูลในคอมพิวเตอร์ เช่น การให้สีกราฟใช้ในการจัดกลุ่ม ที่ไม่ต้องการ
แผนภาพแสดงเส้นทางการบิน
