Please enable JavaScript.
Coggle requires JavaScript to display documents.
สรุปบทที่ 5 (กราฟแบบสองส่วน (นิยามที่ 5.6, Simple graph G จะเป็นกราฟแบบ 2…
สรุปบทที่ 5
กราฟแบบสองส่วน
นิยามที่ 5.6
Simple graph G จะเป็นกราฟแบบ 2 ส่วน (Bipartite graphs) ถ้า
เซตของจุด V สามารถที่จะแยกออกเป็น 2 เซตย่อยที่ไม่มีสมาชิกร่วมกัน (disjointset) คือ V1 และ V2
ซึ่งทุกๆ เส้นเชื่อมในกราฟจะเชื่อมต่อจุดหนึ่งใน V1 ไปยังจุดหนึ่งใน V2• ดังนั้นจะไม่มีเส้นเชื่อมที่เชื่อมต่อจุด 2 จุดใน V1 หรือเชื่อมต่อจุด 2 จุดใน V2
กราฟแบบสองส่วนสมบูรณ์ (Complete Bipartite Graph) คือ
กราฟแบบสองส่วนที่แต่ละจุดใน V1 เชื่อมต่อไปยังทุกจุดใน V2
เขียนแทนด้วย Km,n
ชนิดของกราฟ
Simple Graph
นิยามที่ 5.1 Simple graph G = (V, E) ประกอบด้วย
V ซึ่งเป็นเซตของจุด (Vertices) ที่ไม่ใช่เซตว่าง และ
E ซึ่งเป็นเซตของ unordered pairs ของแต่ละสมาชิกของ V เรียกว่าเส้นเชื่อม (Edges)
Multigraph
นิยามที่ 5.2 Multigraph G = (V, E) ประกอบด้วย
V ซึ่งเป็นเซตของจุด และ
E ซึ่งเป็นเซตของเส้นเชื่อม และ
ฟังก์ชัน f จาก E ไปยัง {{u, v} | u, v ∈ V, u ≠ v} แล้ว
เส้นเชื่อม e1 และ e2 จะเรียกว่า multiple หรือ parallel edges
ถ้า f(e1) = f(e2)
Pseudograph
นิยามที่ 5.3 Pseudograph G = (V, E) ประกอบด้วย
V ซึ่งเป็นเซตของจุด และ
E ซึ่งเป็นเซตของเส้นเชื่อม และ
ฟังก์ชัน f จาก E ไปยัง {{u, v} | u, v ∈ V}
โดยเส้นเชื่อมจะเป็น loop ถ้า f(e)={u,u}={u} สําหรับบางค่าของ u ∈ V
Directed graph
นิยามที่ 5.4 Directed graph (V, E) ประกอบด้วย
V ซึ่งเป็นเซตของจุด และ
E ซึ่งเป็นคู่ลําดับของสมาชิกของ V
Directed multigraph
นิยามที่ 5.5 Directed multigraph G = (V, E) ประกอบด้วย
V ซึ่งเป็นเซตของจุด และ
E ซึ่งเป็นเซตของเส้นเชื่อม และ
ฟังก์ชัน f จาก E ไปยัง {(u, v) | u, v ∈ V} แล้ว
เส้นเชื่อม e1 และ e2 จะเรียกว่า multiple edges ถ้า f(e1) = f(e2)
ทางเดินที่สั้นที่สุด
กราฟที่ใช้เพื่อแก้ปัญหาทางเดินที่สั้นที่สุดจะต้องมีตัวเลขกํากับที่แต่ละเส้นเชื่อม
กราฟลักษณะนี้เรียกว่า “กราฟแบบมีน้ําหนัก (Weighted graphs)”
อัลกอริทึมสําหรับการแก้ปัญหานี้มีหลากหลายอัลกอริทึม
สําหรับในวิชานี้จะศึกษาอัลกอริทึมที่ชื่อว่า "Dijkstra's Algorithm"
คิดค้นโดย Edsger Wybe Dijkstra ในปีค.ศ. 1959
การให้สีกราฟ
นิยามที่ 5.21
การให้สีกราฟ คือ การกําหนดสีให้แต่ละจุดของกราฟโดย 2 จุดที่เชื่อมติดกัน(adjacent) ต้องไม่มีสีเดียวกัน
การให้สีกราฟนั้นจะพยายามใช้สีให้น้อยที่สุด
จํานวนสีอย่างน้อยที่ต้องใช้ในการให้สีกราฟใดๆ เรียกว่า “Chromatic numberof a graph”
การประยุกต์ใช้งาน
แก้ปัญหาที่เกี่ยวข้องกับการจัดตารางและกําหนดการต่างๆ
การพ้องรูปของกราฟ
นิยามที่ 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 กันอยู่ด้วย
การพิจารณาแบบง่ายจะพิจารณาจาก
จํานวนจุดเท่ากันหรือไม่
จํานวนเส้นเชื่อมเท่ากันหรือไม่
จํานวนดีกรีของแต่ละจุดเท่ากันหรือไม่
ถ้าไม่เท่ากัน : กราฟทั้งสองไม่พ้องรูปกัน
ถ้าเท่ากัน : ต้องพิจารณาในรายละเอียดเพิ่มเติม
กราฟแบบระนาบ
กราฟใดๆ จะเป็นกราฟแบบระนาบ ถ้าสามารถวาดกราฟดังกล่าวโดยที่ไม่มีเส้นเชื่อมใดตัดกัน
กราฟใดๆ ก็ตามที่ประกอบด้วยกราฟย่อยซึ่งคล้ายรูป (Homeomorphic) กับ
กราฟ K5 และ K3, 3 ก็จะเป็นกราฟแบบไม่ระนาบด้วย
การคล้ายรูปกันของกราฟ
กราฟ 2 รูปจะคล้ายรูปกันก็ต่อเมื่อกราฟรูปหนึ่งสามารถเปลี่ยนเป็นกราฟอีกรูปหนึ่งได้โดย
การแทนเส้นเชื่อมที่มีอยู่ด้วยเส้นเชื่อมหลายๆ เส้นต่ออนุกรมกัน (คือ การเติมจุดซึ่งมีดีกรีเท่ากับสองในเส้นเชื่อมเดิม)
การรวมเส้นเชื่อมหลายๆ เส้นที่ต่ออนุกรมกันเป็นเส้นเชื่อมเดียวกัน (คือ การลบจุดเดิมที่มีดีกรีเป็น 2 ออก)
การตรวจสอบว่าเป็นกราฟแบบระนาบ
ลบเส้นเชื่อมแบบลูปออก
รวมเส้นเชื่อมที่ต่อแบบอนุกรมกันเป็นเส้นเชื่อมเดียว
ลบเส้นเชื่อมที่ขนานกันระหว่างคู่ของจุดออกให้เหลือเพียง1 เส้น
ค้นหาและวาดวงจรแบบง่ายซึ่งใช้เส้นเชื่อมมากที่สุด
วาดเส้นเชื่อมและจุดที่เหลือซึ่งไม่ได้อยู่ในวงจรแบบง่ายโดยพยายามหลีกเลี่ยงการตัดกันของเส้นเชื่อม
หากไม่สามารถหลีกเลี่ยงได้ก็ให้หากราฟย่อยที่คล้ายรูปกับ K5 หรือ K3, 3 เพื่อยืนยันว่ากราฟดังกล่าวเป็นกราฟแบบไม่ระนาบ
Simple Graphs แบบพิเศษ
Complete graph
มีจํานวน n จุด แทนด้วย Kn
Simple graph ที่มีเส้นเชื่อมเพียงเส้นเดียวระหว่างแต่ละคู่ของจุดที่แยกกัน
จํานวน edges = n(n-1)/2
จํานวน vertices = n
Cycle
แทนด้วย Cn โดย n ≥ 3
ประกอบด้วยจุดจํานวน n จุด คือ v1, v2, v3, ..., vn และมี
edges {v1, v2}, {v2, v3}, . . .,{vn-1, vn}, และ {vn, v1}
จํานวน edges = n
จํานวน vertices = n
Wheel
แทนด้วย Wn จะได้มาจาก
การเพิ่มจุดเข้าไปใน Cn (n ≥ 3) และเชื่อมต่อจุดใหม่นี้ไปยังแต่ละจุดเดิมใน Cn
จํานวน edges = 2n
จํานวน vertices = n+1
n-Cube
ลูกบาศก์ n มิติแทนด้วย Qn
กราฟที่มีจุดต่างๆ ซึ่งใช้แสดง bit string จํานวน 2nbit strings โดยที่ n คือจํานวนบิต ซึ่ง 2 จุดใดๆ จะต่อกันก็ต่อเมื่อ bit string ที่ใช้แสดงจุดนั้นต่างกัน 1บิต
จํานวน edges = 2n-1n
จํานวน vertices = 2n
วงจร ทางเดินแบบง่าย และวงจรแบบง่าย
ทางเดินที่เริ่มต้นและจบที่จุดเดียวกันเรียกว่า “วงจร (Circuit)”
ทางเดินหรือวงจรจะเรียกว่าเป็น “ทางเดินแบบง่าย (Simple path) หรือวงจรแบบง่าย (Simple circuit)” เมื่อผ่านเส้นเชื่อมเดียวกันแค่ 1 ครั้งเท่านั้น
ทางเดินและวงจรออยเลอร์
ทางเดินออยเลอร์
ทางเดินแบบง่ายที่ประกอบ
ด้วยทุกๆ เส้นเชื่อมของกราฟ G
วงจรออยเลอร์
G คือ วงจรแบบง่ายที่ประกอบด้วยทุกๆ
เส้นเชื่อมของกราฟ G
ทางเดินและวงจรฮามิลตัน
ทางเดิน
x0, x1, . . ., xn-1, xn ในกราฟ G = (V, E) จะเป็นทางเดินฮามิลตัน
ถ้า V = {x0, x1, . . ., xn-1, xn} และ xi ≠ xj สําหรับ 0 ≤ i < j ≤ n
วงจร
x0, x1, . . ., xn-1, xn, x0 (เมื่อ n > 1) ในกราฟ G = (V, E) จะเป็นวงจรฮามิลตัน
ทางเดิน
ให้ n เป็นจํานวนเต็มบวกและ G เป็นกราฟแบบไม่มีทิศทาง ทางเดินที่มีความยาว
n จากจุด u ไปยัง v ในกราฟ
ลําดับของเส้นเชื่อมจํานวน n เส้น คือ e1, e2 , . . ., en ของ G
ซึ่ง f(e1) = {x0, x1}, f(e2) = {x1, x2}, . . .,f(en) = {xn-1, xn} โดยที่ x0 = u และ xn =v
ลําดับของเส้นเชื่อมที่เริ่มที่จุดๆ หนึ่งของกราฟและเดินทางไปตามเส้นเชื่อมต่างๆของกราฟซึ่งจะเชื่อมต่อคู่ของจุดที่ adjacent กันเสมอ
ทางเดินและการพ้องรูป
พิจารณาจาก
จํานวนของจุด
จํานวนของเส้นเชื่อม
ดีกรีของจุดต่างๆ
ความยาวของวงจรแบบง่าย
ทางเดินแบบง่ายที่ผ่านทุกจุด
คําศัพท์ที่เกี่ยวข้องกับกราฟ
Adjacent
จุด 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}
Degree
Degree ของจุดๆ หนึ่งในกราฟแบบไม่มีทิศทาง คือ จํานวนของเส้นเชื่อมที่ต่อกับจุดนั้นๆ กรณี loop ที่จุดนั้นจะนับ degree เป็น 2 โดย degree ของจุด v เขียน
จุดที่มี degree = 0 เรียกว่า "Isolated".
จุดที่มี degree = 1 เรียกว่า "Pendant".
แทนด้วย deg (v)
มื่อ (u, v) เป็นเส้นเชื่อมแบบมีทิศทางของกราฟ G จะกล่าวได้ว่า
u adjacent to v และ v adjacent from u และ
เรียกจุด u ว่า จุดเริ่มต้น (initial vertex) ของ (u, v) และ
เรียก v ว่าเป็น จุดปลาย (terminal or end vertex) ของ (u, v)
ซึ่งในกรณีของ loop ทั้งจุดเริ่มต้นและจุดปลายจะเป็นจุดเดียวกัน
สําหรับกราฟแบบมีทิศทาง
in-degree ของจุด v ซึ่งแทนด้วย deg-(v) จะมีค่าเท่ากับจํานวนของเส้นเชื่อมที่มี v เป็นจุดปลาย
out-degree ของจุด v ซึ่งแทนด้วย deg+(v) จะมีค่าเท่ากับจํานวนของเส้นเชื่อมที่มี v เป็นจุดเริ่มต้น
ดังนั้นในกรณีของ loop ที่จุดนั้นจะมี
in-degree เป็น 1 และ out-degree เป็น 1
