ผลต่างระหว่างรุ่นของ "กราฟระบุทิศทาง"
บรรทัด 15: | บรรทัด 15: | ||
กราฟระบุทิศทางถ่วงน้ำหนัก คือกราฟระบุทิศทางที่เป็น[[กราฟถ่วงน้ำหนัก]]ด้วย อาจเรียกกราฟระบุทิศทางถ่วงน้ำหนักว่า''เครือข่าย'' |
กราฟระบุทิศทางถ่วงน้ำหนัก คือกราฟระบุทิศทางที่เป็น[[กราฟถ่วงน้ำหนัก]]ด้วย อาจเรียกกราฟระบุทิศทางถ่วงน้ำหนักว่า''เครือข่าย'' |
||
การเก็บข้อมูลกราฟระบุทิศทางนั้น อาจทำได้โดยการใช้[[เมทริกซ์ประชิด]] ในกรณีที่กราฟเป็น[[กราฟเทียม]] (นั่นคือมีวงวนและเส้นเชื่อมขนานได้) [[เมทริกซ์]]เก็บข้อมูลจะเป็นเมทริกซ์ของตัวเลขขนาด <math>n \times n</math> โดย ''n'' คือจำนวนจุดยอดของกราฟ '' |
การเก็บข้อมูลกราฟระบุทิศทางนั้น อาจทำได้โดยการใช้[[เมทริกซ์ประชิด]] ในกรณีที่กราฟเป็น[[กราฟเทียม]] (นั่นคือมีวงวนและเส้นเชื่อมขนานได้) [[เมทริกซ์]]เก็บข้อมูลจะเป็นเมทริกซ์ของตัวเลขขนาด <math>n \times n</math> โดย ''n'' คือจำนวนจุดยอดของกราฟ ''a<sub>ij</sub>'' ซึ่ง <math>i \neq j</math> แสดงถึงจำนวนเส้นเชื่อมมีทิศทางจากจุดยอด ''i'' ไป ''j'' ส่วน ''a<sub>ii</sub>'' แสดงถึงจำนวนของวงวนที่จุดยอด ''i'' หากเป็น[[กราฟอย่างง่าย]] จะได้ว่าเมทริกซ์ที่กล่าวมานี้จะเป็น[[เมทริกซ์ฐานสอง]] |
||
นอกจากนี้ การเก็บข้อมูลกราฟระบุทิศทาง อาจใช้[[เมทริกซ์ตกกระทบ]]ก็ได้ |
นอกจากนี้ การเก็บข้อมูลกราฟระบุทิศทาง อาจใช้[[เมทริกซ์ตกกระทบ]]ก็ได้ |
รุ่นแก้ไขเมื่อ 20:13, 3 พฤศจิกายน 2555
ในทฤษฎีกราฟ กราฟระบุทิศทาง หรือ ไดกราฟ คือกราฟซึ่งเส้นเชื่อมมีทิศ กล่าวคือกราฟ G = (V,A) โดยที่
- เซต V เป็นเซตซึ่งสมาชิกคือจุดยอด หรืออาจะเรียกว่าโหนด หรือปม
- เซต A เป็นเซตของเส้นเชื่อมมีทิศทาง ซึ่งเป็นคู่อันดับของจุดยอด สำหรับเส้นเชื่อมของกราฟระบุทิศทาง อาจเรียกว่าเส้นเชื่อมมีทิศทางหรือลูกศร (และสำหรับเซตของเส้นเชื่อม (edge) นี้ ในบางครั้งอาจใช้ E แทน A)
กราฟระบุทิศทางแตกต่างจากกราฟไม่ระบุทิศทางตรงเซตของเส้นเชื่อม ซึ่งเส้นเชื่อมของกราฟระบุทิศทางจะเป็นคู่อันดับของจุดยอด ในขณะที่เส้นเชื่อมของกราฟไม่ระบุทิศทางจะเป็นคู่ไม่อันดับของจุดยอด
เนื่องจากกราฟอาจจะเป็นกราฟอย่างง่ายหรือมัลติกราฟก็ได้ บางครั้งจึงอาจเรียกประเภทเข้าไปด้วยว่า กราฟระบุทิศอย่างง่าย หรือ มัลติกราฟที่มีทิศทาง ซึ่งสำหรับมัลติกราฟนั้น A จะเป็นมัลติเซตแทนที่เซต เพื่อให้สามารถมีเส้นเชื่อมมากกว่า 1 เส้นระหว่างคู่ของจุดยอดได้ อย่างไรก็ตาม มัลติกราฟจะสามารถมีวงวน (เส้นเชื่อมที่ปลายทั้งสองด้านต่อกับจุดยอดจุดเดียวกัน) ได้หรือไม่ก็ยังแตกต่างกันไปตามแต่ที่กำหนดให้
นิยามทั่วไป
เส้นเชื่อมมีทิศทาง เป็นเส้นเชื่อมจาก ไป โดยที่ เรียกว่าหัว ส่วน เรียกว่าหางของเส้นเชื่อม นอกจากนี้ y นั้นถือว่าเป็นปลายทางโดยตรง ในขณะที่ x ถือว่าเป็นต้นทางโดยตรง หากมีวิถีจาก x ไปยัง y จะได้ว่า y เป็นปลายทาง ส่วน x เป็นต้นทาง เส้นเชื่อมมีทิศทาง จะถูกเรียกว่าเป็นเส้นเชื่อมกลับทิศของ
กราฟระบุทิศทาง D จะถูกเรียกว่าสมมาตร ก็ต่อเมื่อทุกๆเส้นเชื่อมนั้น มีเส้นเชื่อมกลับทิศอยู่ในกราฟด้วย ในแง่การไปถึงกันได้ กราฟระบุทิศทางที่สมมาตร D จะเทียบเท่ากับกราฟไม่ระบุทิศทาง G โดยที่เส้นเชื่อม (x,y) และ (y,x) เทียบเท่ากับเส้นเชื่อม {x,y} ดังนั้น หากเปรียบเทียบระหว่างกราฟระบุทิศทางที่สมมาตรและกราฟไม่ระบุทิศทางที่เทียบเท่ากัน จะได้ว่า |E| = |A|/2
การกำหนดทิศทาง คือการนำกราฟไม่ระบุทิศทางอย่างง่ายมากำหนดทิศทางของแต่ละเส้นเชื่อมอย่างไรก็ได้ให้กลายเป็นกราฟระบุทิศทาง กราฟที่ได้จากการกำหนดทิศทางนี้เรียกว่ากราฟกำหนดทิศทาง มีคุณสมบัติคือจะไม่มีวงวนหรือวัฏจักรขนาด 2 [1]
กราฟระบุทิศทางถ่วงน้ำหนัก คือกราฟระบุทิศทางที่เป็นกราฟถ่วงน้ำหนักด้วย อาจเรียกกราฟระบุทิศทางถ่วงน้ำหนักว่าเครือข่าย
การเก็บข้อมูลกราฟระบุทิศทางนั้น อาจทำได้โดยการใช้เมทริกซ์ประชิด ในกรณีที่กราฟเป็นกราฟเทียม (นั่นคือมีวงวนและเส้นเชื่อมขนานได้) เมทริกซ์เก็บข้อมูลจะเป็นเมทริกซ์ของตัวเลขขนาด โดย n คือจำนวนจุดยอดของกราฟ aij ซึ่ง แสดงถึงจำนวนเส้นเชื่อมมีทิศทางจากจุดยอด i ไป j ส่วน aii แสดงถึงจำนวนของวงวนที่จุดยอด i หากเป็นกราฟอย่างง่าย จะได้ว่าเมทริกซ์ที่กล่าวมานี้จะเป็นเมทริกซ์ฐานสอง
นอกจากนี้ การเก็บข้อมูลกราฟระบุทิศทาง อาจใช้เมทริกซ์ตกกระทบก็ได้
อ้างอิง
- ↑ Diestel (2005) , Section 1.10.