ทฤษฎีกราฟ



ทฤษฎีกราฟ

กราฟมีบทบาทสำคัญกับชีวิตของเราอย่างไร ? ถนนที่เราใช้ในการสัญจรเป็นตัวอย่างหนึ่งที่มีการนำทฤษฎีกราฟมาใช้รวมทั้งการวางระบบท่อประปา และวงจรไฟฟ้า ชีวิตประจำวันของเราล้วนเกี่ยวข้องกับคณิตศาสตร์ในเรื่องต่างๆรวมถึงเรื่องทฤษฎีกราฟ
กราฟ G ประกอบด้วยคู่ลำดับของเซต คือ

1.         เซตของจุดยอด (Vertex) ที่ไม่เป็นเซตว่างV(G)

2.         เซตของเส้นเชื่อม(Edge) ระหว่างคู่ที่เชื่อมจุดยอด E(G)

ภาพที่ 1 ภาพประกอบจาก https://www3.nd.edu/~dgalvin1/40210/40210_F12/CGT_early.pdf


จากภาพ  เซตของจุดยอด หรือ V(G) คือ { a, b, c, d, e, f, g, h}

 เซตของเส้นเชื่อมที่เชื่อมจุดยอด หรือ E(G) คือ {{a, e},{a, d},{b, e},{b, g},{b, c},{c, f},{d, f},
                                                                              {d, g}, {g, h}}

จุดยอดประชิด หรือ adjacent vertices คือ เส้นเชื่อมสองเส้นที่มีจุดยอดเดียวกัน

จากภาพที่ 1 พบว่า  จุดยอด a และ d เป็นจุดยอดประชิด

จุดยอด a และ e เป็นจุดยอดประชิด

จุดยอด b และ e เป็นจุดยอดประชิด

จุดยอด b และ c เป็นจุดยอดประชิด

จุดยอด b และ g เป็นจุดยอดประชิด

จุดยอด c และ f เป็นจุดยอดประชิด

จุดยอด d และ f เป็นจุดยอดประชิด

จุดยอด d และ g เป็นจุดยอดประชิด

จุดยอด g และ h เป็นจุดยอดประชิด

กราฟเชิงเดียว (simple graph) คือ กราฟที่แต่ละเส้นเชื่อมเชื่อมจุดยอดที่แตกต่างกันและไม่มีเส้นเชื่อมที่ซ้ำกันที่จุดยอดคู่เดียวกัน ดังภาพต่อไปนี้



จากภาพเราจะพบว่าภาพแรกหรือภาพทางซ้ายไม่ใช่กราฟเชิงเดียว (simple graph) เนื่องจากจุด V1 และ V3 มีเส้นเชื่อมที่ซ้ำกัน นอกจากนี้จุด V2 ยังมีเชื่อมกันที่จุดยอดเดิม หรือที่เราเรียกว่าลูป (loop)

ภาพที่สองหรือภาพทางขวาเป็นกราฟเชิงเดียวหรือ (simple graph) เนื่องจากไม่มีลูปและไม่มีเส้นเชื่อมที่ซ้ำกันที่จุดยอดคู่เดียวกัน

มัลติกราฟ (Multi Graph) คือ กราฟที่มีเส้นเชื่อมซ้ำกันที่จุดยอดคู่เดียวกันและไม่มีลูป
ภาพประกอบจาก https://www.chegg.com/homework-help/questions-and-answers/1-graph-simple-graph-multigraph-pseudogr


จากภาพ กราฟ G1 เป็นมัลติกราฟ (multi graph) เนื่องจากมีเส้นเชื่อมซ้ำกันที่คู่ของจุดยอด b,d และคู่ของจุดยอด a,b  แต่กราฟ G2 ไม่เป็นมัลติกราฟ เพราะว่ามีลูป แต่จะเป็นมัลติกราฟระบุทิศทางซึ่งจะอธิบายภายหลัง


ความคิดเห็น

แสดงความคิดเห็น

โพสต์ยอดนิยมจากบล็อกนี้

ทฤษฎีกราฟ 4

รูปภาพ
Euler Circuit คือ กราฟที่ต้องเดินผ่านทุกด้าน ไม่มีการซ้ำด้าน เริ่มตรงไหนจบตรงนั้น โดยจุดยอดทุกจุดจะมีดีกรีคู่ ภาพประกอบจาก https://www.geeksforgeeks.org/wp-content/uploads/Euler 2. png จากภาพจะพบว่าทุกจุดยอดมีดีกรีคู่ เมื่อมีการเดินผ่านทุกด้านโดยไม่ซ้ำจุดเริ่มต้นและสิ้นสุดจะเป็นจุดเดียวกัน Euler Path คือ กราฟที่ต้องเดินผ่านทุกด้าน ไม่มีการซ้ำด้าน แต่ เริ่มต้นกับสิ้นสุดต้องเป็นคนละจุด สามารถสังเกตได้จากกราฟว่าจะมีสองจุดยอดเท่านั้นที่มีดีกรีเป็นเลขคี่ ภาพประกอบจาก https://www.geeksforgeeks.org/eulerian-path-and-circuit/ จากภาพพบว่ามีสองจุดเท่านั้นที่มีดีกรีคี่ คือ จุด 0 และ จุด 4 เมื่อมีการเดินผ่านทุกด้านพบว่าจุดเริ่มต้นและสิ้นสุดเป็นคนละจุดกัน   Hamilton Circuit คือ กราฟที่ไม่จำเป็นต้องเดินผ่านทุกด้าน จุดเริ่มต้นและสิ้นสุดเป็นจุดเดียวกัน ไม่ซ้ำจุด ภาพประกอบจาก https://slideplayer.com/slide/ 7549367/ เมื่อเดินผ่านทุกจุดพบว่าจุดเริ่มต้นและสิ้นสุดเป็นจุดเดียวกัน ทั้งสองภาพ H...
อ่านเพิ่มเติม

ทฤษฎีกราฟ 3

รูปภาพ
Bipartite graph คือ กราฟที่สามารถแบ่งออกเป็นสองส่วน โดยทั้งสองส่วนนั้นจะมีเส้นเชื่อมเชื่อมกันแต่จะไม่มีเส้นเชื่อมภายในส่วนเดียวกัน ภาพประกอบจาก https://study.com/cimages/multimages/ 16/ bipartite 4. jpg จากภาพจะพบว่าสามารถแบ่งกราฟออกเป็นสองส่วน โดยแต่ละจุดยอดของกลุ่ม 1 จะมีเส้นเชื่อมไปยังกลุ่ม 2 ทุกเส้นแต่ไม่มีเส้นใดเลยที่เชื่อมกันเองภายในกลุ่ม การแทนที่กราฟและการสมสัณฐานของกราฟ (Representing graph and graph Isomorphism) การแทนที่กราฟด้วย Adjacency matrix แบ่งเป็น แบบไม่มีทิศทางและแบบมีทิศทาง ภาพประกอบจาก https://bournetocode.com/projects/AQA_A_Theory/pages/graph.html จากภาพเป็นการแทนที่กราฟด้วย Adjacency Matrix กราฟเป็นแบบไม่มีทิศทาง จุดยอดที่มีเส้นเชื่อมไปยังอีกจุดยอดหนึ่งจะแทนด้วย เลข 1 แต่ถ้าไม่มีจะแทนด้วย เลข 0 ในกรณีที่กราฟนั้นเป็นกราฟเชิงเดียวหรือ simple graph โดยอันดับแรกจะเขียนจุดยอดที่หลักและแถว จากนั้นให้สังเกตแต่ละจุดยอดว่ามีเส้นเชื่อมไปยังจุดใดบ้างให้ทำแบบนี้ไปเรื่อยๆจนถึงจุดยอดสุดท้าย ภาพประกอบจาก https://bournetocode.com...
อ่านเพิ่มเติม