Please enable JavaScript.
Coggle requires JavaScript to display documents.
ทฤษฏีกราฟ (Graphs Theory) (ชนิดของกราฟ (Simple Graph (เป็นกราฟที่ G = (V…
ทฤษฏีกราฟ (Graphs Theory)
ชนิดของกราฟ
Simple Graph
เป็นกราฟที่ G = (V,E) ประกอบด้วย
V เป็นเซตของจุดและไม่ใช่เซตว่าง
E เป็นเซตของแต่ละสมาชิกของ V เรียกว่า เส้นเชื่อม
Multigraph
เป็นกราฟที่ G = (V,E) ประกอบด้วย
V เป็นเซตของจุด
E เป็นเซตของเส้นเชื่อม
มีฟังก์ชัน f จาก E ไปยัง {{u, v} | u, v ∈ V, u ≠ v}
ถ้า f(e1) = f(e2)จะเรียกว่า multiple หรือ parallel edges
Pseudograph
เป็นกราฟที่ G = (V,E) ประกอบด้วย
V เป็นเซตของจุด E เป็นเซตของเส้นเชื่อม ฟังก์ชัน f จาก E ไปยัง {{u, v} | u, v ∈ V}
เส้นเชื่อมจะเป็น loop ถ้า f(e)={u,u}={u} สำหรับบางค่าของ u ∈ V
Directed Graph
เป็นกราฟที่มี (V,E) ประกอบด้วยV ซึ่งเป็นเซตของจุดและ E ซึ่งเป็นคู่ลำดับของสมาชิกของ V
Directed Multigraph
เป็นกราฟที่ G = (V, E) ประกอบด้วย V เป็นเซตของจุด E เป็นเซตของเส้นเชื่อม
ถ้าฟังก์ชัน f จาก E ไปยัง {(u, v) | u, v ∈ V}แล้วเส้นเชื่อม e1 และ e2 จะเรียกว่า multiple edges ถ้า f(e1) = f(e2)
การพ้องรูปของกราฟ (Isomorphism of Graphs)
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
มีฟังก์ชันแบบ bijection ระหว่างจุดของกราฟทั้ง 2 ซึ่งยังคงมีความสัมพันธ์แบบ adjacent กันอยู่ด้วย
การพิจารณาแบบง่ายจะพิจารณาจาก
1.จำนวนจุดเท่ากันหรือไม่
2.จำนวนเส้นเชื่อมเท่ากันหรือไม่
3.จำนวนดีกรีของแต่ละจุดเท่ากันหรือไม่
ถ้าเท่ากัน : ต้องพิจารณาในรายละเอียดเพิ่มเติม
ถ้าไม่เท่ากัน : กราฟทั้งสองไม่พ้องรูปกัน
การเชื่อมต่อ (Connectivity)
การเชื่อมต่อกันในกราฟแบบมีทิศทาง (Connectedness in directed
graphs)
ทางเดินและการพ้องรูปกันของกราฟ (Paths and Isomorphism)
การเชื่อมต่อกันในกราฟแบบไม่มีทิศทาง (Connectedness in undirected
graphs)
ทางเดิน (Paths)
ให้ n เป็นจำนวนเต็มบวกและ G เป็นกราฟแบบไม่มีทิศทาง ทางเดินที่มีความยาว n จากจุด u ไปยัง v ในกราฟ G คือ
ลำดับของเส้นเชื่อมจำนวน 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 กันเสมอ
ทางเดินและวงจรฮามิลตัน (Hamilton Paths and Circuyits)
ทางเดิน x0, x1, . . ., xn-1, xn ในกราฟ G = (V, E) จะเป็นทางเดินฮามิลตัน
วงจร x0, x1, . . ., xn-1, xn, x0 (เมื่อ n > 1) ในกราฟ G = (V, E) จะเป็นวงจร
ฮามิลตัน
คุณสมบัติบางประการ
กราฟที่มีจุดซึ่งมีดีกรีเท่ากับ 1
ถ้าจุดใดในกราฟที่มีดีกรีเท่ากับ 2 แล้ว เส้นเชื่อมทั้ง 2 ที่ต่อกับจุดดังกล่าวไม่ได้เป็นส่วนหนึ่งของวงจรฮามิลตัน
วงจรฮามิลตันจะไม่มีวงจรฮามิลตันอยู่ภายใน
ทางเดินและวงจรออยเลอร์ (Euler Paths and Circuits)
ทางเดินออยเลอร์ (Euler path) ในกราฟ G คือ ทางเดินแบบง่ายที่ประกอบด้วยทุกๆ เส้นเชื่อมของกราฟ G
วงจรออยเลอร์ (Euler circuit) ในกราฟ G คือ วงจรแบบง่ายที่ประกอบด้วยทุกๆเส้นเชื่อมของกราฟ G
ทางเดินที่สั้นที่สุด (Shortest-Path)
ใช้เพื่อแก้ปัญหาทางเดินที่สั้นที่สุดจะต้องมีตัวเลขกำกับที่แต่ละเส้นเชื่อม เรียกว่า กราฟแบบมีน้ำหนัก ใช้ อัลกอริทึม Dijkstra's Algorithm ในการแก้ปัญหา
กราฟแบบระนาบ (Planar Graphs)
กราฟใดๆ จะเป็นกราฟแบบระนาบ ถ้าสามารถวาดกราฟดังกล่าวโดยที่ไม่มีเส้นเชื่อมใดตัดกัน
คุณสมบัติบางประการ
กราฟทั้งสองเป็นกราฟที่มีดีกรีของทุกๆ จุดในกราฟเท่ากัน
กราฟทั้งสองเป็นกราฟแบบไม่ระนาบ (Nonplanar graph)
ถ้าลบเส้นเชื่อมเส้นใดเส้นหนึ่งออกจากกราฟจะทำให้เป็นกราฟแบบระนาบได้
K5 เป็นกราฟแบบไม่ระนาบซึ่งมีจำนวนจุดน้อยที่สุด
K3, 3 เป็นกราฟแบบไม่ระนาบที่มีจำนวนเส้นเชื่อมน้อยที่สุด
ทั้ง K5 และ K3, 3 เป็นกราฟแบบไม่ระนาบที่มีรูปแบบซับซ้อนน้อยที่สุด
การตรวจสอบว่าเป็นกราฟแบบระนาบหรือไม
ลบเส้นเชื่อมแบบลูปออก
รวมเส้นเชื่อมที่ต่อแบบอนุกรมกันเป็นเส้นเชื่อมเดียว
ลบเส้นเชื่อมที่ขนานกันระหว่างคู่ของจุดออกให้เหลือเพียง 1 เส้น
ค้นหาและวาดวงจรแบบง่ายซึ่งใช้เส้นเชื่อมมากที่สุด
วาดเส้นเชื่อมและจุดที่เหลือซึ่งไม่ได้อยู่ในวงจรแบบง่ายโดยพยายามหลีกเลี่ยงการตัดกันของเส้นเชื่อม
หากไม่สามารถหลีกเลี่ยงได้ก็ให้หากราฟย่อยที่คล้ายรูปกับ K5 หรือ K3, 3 เพื่อยืนยันว่ากราฟดังกล่าวเป็นกราฟแบบไม่ระนาบ
การให้สีกราฟ (Graph Colouring)
การกำหนดสีให้แต่ละจุดของกราฟโดย 2 จุดที่เชื่อมติดกัน
ต้องไม่มีสีเดียวกันและจะต้องพยายามใช้สีให้น้อยที่สุดสามารถใช้สีซ้ำกับจุดที่ไม่ได้ติดกันได้ จำนวนสีอย่างน้อยที่ใช้ในการให้สีกราฟ
เรียกว่า "Chromatic number of a graph" ใช้ในการแก้ปัญหาที่เกี่ยวข้องกับการจัดตารางและกำหนดการต่างๆ
วงจรทางเดินแบบง่าย และวงจรแบบง่าย
ทางเดินที่เริ่มต้นและจบที่จุดเดียวกันเรียกว่า “วงจร (Circuit)”
ทางเดินหรือวงจรจะเรียกว่าเป็น “ทางเดินแบบง่าย (Simple path) หรือวงจร
แบบง่าย (Simple circuit)” เมื่อผ่านเส้นเชื่อมเดียวกันแค่ 1 ครั้งเท่านั้น
การเชื่อมต่อกันของกราฟแบบไม่มีทิศทาง
กราฟแบบไม่มีทิศทางจะกล่าวว่า “ถูกเชื่อมต่อกัน (connected)” ถ้ามีทางเดิน
ระหว่างทุกๆ คู่ของจุดในกราฟ
กราฟที่ไม่เชื่อมต่อกัน
ประกอบด้วย connected subgraphs ตั้งแต่ 2 subgraphs ขึ้นแต่ละ connected subgraphs จะเรียกว่า "Connected components" ของกราฟ
ศัพท์ที่เกี่ยวข้องกับกราฟ
Degree ของจุดๆหนึ่งในกราฟแบบไม่มีทิศทาง คือ จำนวนของเส้นเชื่อมที่ต่อกับจุดๆนั้นกรณี loop จะนับจุดนั้นเป็น 2 degree ของจุด v เขียนแทนด้วย deg(v) ในกรณีที่ degree = 0 เรียกว่า "Isolate" และ degree = 1 เรียกว่า "Pendant"
Handshaking Theorem ให้ G =(V,E) เป็นกราฟแบบไม่มีทิศทางมี e เป็นเส้นเชื่อมแล้วจะได้ว่า 2e = ผลรวมของ deg(v) โดยที่ v เป็นสมาชิกของ V
สำหรับกราฟแบบมีทิศทาง ให้ (u,v) เป็นเส้นเชื่อมแบบมีทิศทางของกราฟ G เรียกจุด u ว่า จุดเริ่มต้น และ จุด v ว่าจุดปลาย ในกรณี loop ให้นับเป็นจุดต้นและจุดปลายเป็นจุดเดียวกัน