ทฤษฎีกราฟ 2
Pseudograph คือ กราฟที่มีการเชื่อมต่อระหว่างจุดสองจุด และมีลูป
ภาพประกอบจาก sigma.ontologyportal.org:8080/sigma/TreeView.jsp?lang=EnglishLanguage&flang=TPTP&kb=SUMO&term=PseudoGraph
Directed graph หรือกราฟระบุทิศทาง จะมีลักษณะคล้ายกับกราฟเชิงเดียวหรือ simple graph แต่จะแตกต่างกันที่ Directed graph
นั้นมีการระบุทิศทาง (ลูกศร) และมีลูป
ภาพประกอบจาก https://commons.m.wikimedia.org/wiki/File:Small_directed_graph.JP
Directed multigraph หรือมัลติกราฟระบุทิศทาง
มีความคล้ายคลึงกับกราฟระบุทิศทางแต่จะต่างกันที่มัลติกราฟระบุทิศทางมีเส้นเชื่อมสองเส้นที่เชื่อมระหว่างจุดสองจุด
ภาพประกอบจาก https://math.stackexchange.com/questions/1070306/directed-multigraph-or-directed-simple-graph
จากภาพ หมายเลข 9 เป็นมัลติกราฟเป็นกราฟระบุทิศทาง แต่กราฟหมายเลข 7
เป็นกราฟระบุทิศทางสังเกตได้จากเครื่องหมายบอกทิศทางที่ได้ทำการไฮไลต์เอาไว้ ถ้าไปในทิศทางเดียวกัน
(ไฮไลต์สีเหลือง) จะเป็นมัลติกราฟระบุทิศทางก็คือ
มีเส้นเชื่อมตั้งแต่สองเส้นขึ้นไปที่เชื่อมระหว่างจุดสองจุด
ในขณะที่กราฟระบุทิศทางไม่มี
ดีกรีจุดยอดของกราฟ คือ
จำนวนครั้งที่เส้นเชื่อมเชื่อมกับจุดยอดโดยใช้สัญลักษณ์ deg
ภาพประกอบจาก https://www.python-course.eu/graphs_python.php
จากภาพ จุด a มีเส้นเชื่อมที่เชื่อมกับจุดยอด 1 ครั้ง ดีกรี = 1
จุด b มีเส้นเชื่อมที่เชื่อมกับจุดยอด 2
ครั้ง ดีกรี = 2
จุด c มีเส้นเชื่อมกับจุดยอด 4 ครั้ง ดีกรี = 4
จุด d มีเส้นเชื่อมกับจุดยอด 1 ครั้ง ดีกรี = 1
จุด e มีเส้นเชื่อมกับจุดยอด 2 ครั้ง ดีกรี = 2 และจุด f ไม่มีเส้นเชื่อมที่เชื่อมกับจุดยอด ดีกรี =
0
จุดยอดที่มีจำนวนดีกรีคู่ เรียกว่า จุดยอดคู่ จุดยอดที่มีจำนวนดีกรีคี่ เรียกว่า จุดยอดคี่
หมายเหตุ ถ้าเป็นลูป 1 ลูปจะเท่ากับ 2 ดีกรี
ภาพประกอบจาก https://cdncontribute.geeksforgeeks.org/wp-content/uploads/SIMPLE-GRAPH.jpg
จุด a มีดีกรีเท่ากับ 3 จุด b มีดีกรีเท่ากับ
2
จุด c มีดีกรีเท่ากับ 3 จุด d มีดีกรีเท่ากับ 2
จุด e มีดีกรีเท่ากับ 4 จุด f มีดีกรีเท่ากับ
2
เมื่อรวมดีกรีทั้งหมดเข้าด้วยกัน deg a + deg b + deg c + deg d + deg e + deg f = 16
จากข้อมูลดังกล่าวตรงกับทฤษฎี “ผลรวมของดีกรีของจุดยอดทั้งหมดในกราฟเท่ากับสองเท่าของเส้นเชื่อม” จากภาพจะได้ ดีกรี = 16 จำนวนเส้นเชื่อมจะเท่ากับ 16 / 2 ได้ 8 เส้นเชื่อม
และตรงกับทฤษฎี “ทุกกราฟจะมีจุดยอดคี่เป็นจำนวนคู่” คือ จุด a และจุด c ซึ่งทั้งสองจุดเป็น จุดยอดคี่
กราฟระบุทิศทางหรือ directed graph มีวิธีการนับดีกรีโดยการแบ่งเป็น
ดีกรีเข้า (in degree) และดีกรีออก (out degree)
จากภาพดีกรีเข้า (in degree ) จะมี A = 0 เนื่องจากไม่มีลูกศรใดเลยที่ชี้เข้าหา
A
B = 3 มีลูกศรจาก A , C, F ชี้เข้าหา B
C = 1 มีลูกศรจาก F ชี้เข้าหา C D = 2 มีลูกศรจาก A,B ชี้เข้า D
E = 1 มีลูกศรจาก D ชี้เข้า E และ F = 1 มีลูกศรจาก
E ชี้เข้า F
โดยรวม in degree จะได้ทั้งหมด = 8
ดีกรีออก(out degree) จะมี A = 2 มีลูกศรจาก
A ไป B,D
B = 1 ลูกศรชี้ไป D C = 1 ลูกศรชี้ไป B D = 1 ลูกศรชี้ไป E
E = 1 ลูกศรชี้ไป F และ F = 2 ลูกศรชี้ไปที่ B,C รวม
out degree = 8
ตรงกับทฤษฎี “ดีกรีเข้า = ดีกรีออก = จำนวนเส้นเชื่อม”
หมายเหตุ ลูป 1 ลูป จะมีดีกรีเข้า =1 และดีกรีออก = 1 (อย่างละหนึ่ง)
ความคิดเห็น
แสดงความคิดเห็น