ผลต่างระหว่างรุ่นของ "กราฟระบุทิศทาง"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล จัดรูปแบบ +เก็บกวาดด้วยสจห. |
ล ปรับแก้ +เนื้อหา |
||
บรรทัด 34:
== ความต่อเนื่องของกราฟระบุทิศทาง ==
{{main|ความต่อเนื่อง (ทฤษฎีกราฟ)}}
กราฟระบุทิศทาง ''G'' จะเรียกว่า''กราฟต่อเนื่องแบบอ่อน'' (weakly connected) หรืออาจเรียกว่า''กราฟต่อเนื่อง'' (connected)<ref>{{harvtxt|Bang-Jensen|Gutin|2000}} p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).</ref> ก็ต่อเมื่อนำกราฟระบุทิศทางนั้นมาเปลี่ยนเส้นเชื่อมที่มีทิศทางให้กลายเป็นเส้นเชื่อมไม่มีทิศทางให้หมด แล้วกราฟไม่ระบุทิศทางที่ได้เป็นกราฟต่อเนื่อง และกราฟระบุทิศทาง ''G'' จะเรียกว่า''กราฟต่อเนื่องแบบเข้ม'' (strongly connected) ก็ต่อเมื่อทุกๆวิถีจาก ''u'' ไป ''v'' มีวิถีจาก ''v'' ไป ''u'' ด้วย นอกจากนี้ ''ส่วนประกอบแบบเข้ม'' (strongly components) คือกราฟย่อยที่มีขนาดมากที่สุดที่เป็นกราฟต่อเนื่องแบบเข้ม แนวคิดนี้นำไปสู่การแบ่งกราฟออกเป็นหลายๆส่วนโดยการหาส่วนประกอบแบบเข้มและลบออกจากกราฟเดิมไปเรื่อยๆ สุดท้ายจะได้[[ส่วนประกอบที่เชื่อมกันแบบเข้ม]] (strongly connected component)
== กราฟระบุทิศทางประเภทต่างๆ ==
[[File:Directed acyclic graph 2.svg|right|100px|thumb|กราฟอวัฏจักรระบุทิศทางอย่างง่าย]]
* [[กราฟอวัฏจักรระบุทิศทาง]] (directed acyclic graph: DAG) คือ กราฟระบุทิศทาง ที่ไม่มีวัฏจักร
** [[multitrees]]
** [[oriented trees]]
** [[rooted trees]]
* [[tournament]]
* [[quiver]]
== อ้างอิง ==
| |||