ผลต่างระหว่างรุ่นของ "กราฟระบุทิศทาง"

ปรับแก้ +เนื้อหา
(จัดรูปแบบ +เก็บกวาดด้วยสจห.)
(ปรับแก้ +เนื้อหา)
== ความต่อเนื่องของกราฟระบุทิศทาง ==
{{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]]
 
== อ้างอิง ==