กราฟระบุทิศทาง

ในทฤษฎีกราฟ กราฟระบุทิศทาง หรือ ไดกราฟ คือกราฟซึ่งเส้นเชื่อมมีทิศ กล่าวคือกราฟ <math>G = (V, A)</math> (หรืออาจจะใช้ <math>G = (V, E)</math> ก็ได้) โดยที่
กราฟระบุทิศทางแตกต่างจากกราฟไม่ระบุทิศทางตรงเซตของเส้นเชื่อม ซึ่งเส้นเชื่อมของกราฟระบุทิศทางจะเป็นคู่อันดับของจุดยอด ในขณะที่เส้นเชื่อมของกราฟไม่ระบุทิศทางจะเป็นคู่ไม่อันดับของจุดยอด
เนื่องจากกราฟอาจจะเป็นกราฟอย่างง่ายหรือมัลติกราฟก็ได้ บางครั้งจึงอาจเรียกประเภทเข้าไปด้วยว่า กราฟระบุทิศอย่างง่าย หรือ มัลติกราฟที่มีทิศทาง ซึ่งสำหรับมัลติกราฟนั้น "A" จะเป็นมัลติเซตแทนที่เซต เพื่อให้สามารถมีเส้นเชื่อมมากกว่า 1 เส้นระหว่างคู่ของจุดยอดได้ อย่างไรก็ตาม มัลติกราฟจะสามารถมีวงวน (เส้นเชื่อมที่ปลายทั้งสองด้านต่อกับจุดยอดจุดเดียวกัน) ได้หรือไม่ก็ยังแตกต่างกันไปตามแต่ที่กำหนดให้
นิยามทั่วไป.
เส้นเชื่อมมีทิศทาง <math>e = (x, y) </math> เป็นเส้นเชื่อม"จาก" <math>x</math> "ไป" <math>y</math> โดยที่ <math>y</math> เรียกว่า"หัว" ส่วน <math>x</math> เรียกว่า"หาง"ของเส้นเชื่อม นอกจากนี้ "y" นั้นถือว่าเป็น"จุดยอดข้างหลังโดยตรง" ในขณะที่ "x" ถือว่าเป็น"จุดยอดก่อนหน้าโดยตรง" สำหรับวิถีจาก "x" ไปยัง "y" จะได้ว่า "y" เป็น"จุดยอดข้างหลัง" ส่วน "x" เป็น"จุดยอดก่อนหน้า" เส้นเชื่อมมีทิศทาง <math> (y, x) </math> จะถูกเรียกว่าเป็นเส้นเชื่อมกลับทิศของ <math> (x, y) </math>
กราฟระบุทิศทาง "D" จะถูกเรียกว่า"สมมาตร" ก็ต่อเมื่อทุก ๆ เส้นเชื่อมนั้น มีเส้นเชื่อมกลับทิศอยู่ในกราฟด้วย ในแง่การไปถึงกันได้ กราฟระบุทิศทางที่สมมาตร D จะเทียบเท่ากับกราฟไม่ระบุทิศทาง G โดยที่เส้นเชื่อม (x,y) และ (y,x) เทียบเท่ากับเส้นเชื่อม {x,y} ดังนั้น หากเปรียบเทียบระหว่างกราฟระบุทิศทางที่สมมาตรและกราฟไม่ระบุทิศทางที่เทียบเท่ากัน จะได้ว่า |"E"| = |"A"|/2
การกำหนดทิศทาง คือการนำกราฟไม่ระบุทิศทางอย่างง่ายมากำหนดทิศทางของแต่ละเส้นเชื่อมอย่างไรก็ได้ให้กลายเป็นกราฟระบุทิศทาง กราฟที่ได้จากการกำหนดทิศทางนี้เรียกว่ากราฟกำหนดทิศทาง มีคุณสมบัติคือจะไม่มีวงวนหรือวัฏจักรขนาด 2 
กราฟระบุทิศทางถ่วงน้ำหนัก คือกราฟระบุทิศทางที่เป็นกราฟถ่วงน้ำหนักด้วย อาจเรียกกราฟระบุทิศทางถ่วงน้ำหนักว่า"เครือข่าย"
การเก็บข้อมูลกราฟระบุทิศทางนั้น อาจทำได้โดยการใช้เมทริกซ์ประชิด ในกรณีที่กราฟเป็นกราฟเทียม (นั่นคือมีวงวนและเส้นเชื่อมขนานได้) เมทริกซ์เก็บข้อมูลจะเป็นเมทริกซ์ของตัวเลขขนาด <math>n \times n</math> โดย "n" คือจำนวนจุดยอดของกราฟ "aij" ซึ่ง <math>i \neq j</math> แสดงถึงจำนวนเส้นเชื่อมมีทิศทางจากจุดยอด "i" ไป "j" ส่วน "aii" แสดงถึงจำนวนของวงวนที่จุดยอด "i" หากเป็นกราฟอย่างง่าย จะได้ว่าเมทริกซ์ที่กล่าวมานี้จะเป็นเมทริกซ์ฐานสอง
นอกจากนี้ การเก็บข้อมูลกราฟระบุทิศทาง อาจใช้เมทริกซ์ตกกระทบก็ได้
ระดับขั้นเข้าและระดับขั้นออก.
สำหรับจุดยอดใด ๆ "ระดับขั้น"เข้าคือจำนวนเส้นเชื่อมที่พุ่งเข้าจุดยอดนั้น ๆ (จุดยอดนั้นเป็นหัวของเส้นเชื่อม) ในขณะที่"ระดับขั้นออก"คือจำนวนเส้นเชื่อมที่พุ่งออกจากจุดยอดนั้น ๆ (จุดยอดนั้นเป็นหางของเส้นเชื่อม) สำหรับต้นไม้ ระดับขั้นออกคือระดับแตกกิ่ง
ระดับขั้นเข้าเขียนได้ว่า <math>\deg^-(v)</math> ส่วนระดับขั้นออกเขียนได้ว่า <math>\deg^+(v).</math> จุดยอดที่มี <math>\deg^-(v)=0</math> เรียกว่า "ต้นทาง" ในขณะที่จุดยอดที่มี <math>\deg^+(v)=0</math> เรียกว่า "ปลายทาง"
จาก"สูตรผลรวมระดับขั้น" สำหรับกราฟระบุทิศทางจะได้ว่า
 <math>\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) = |A|</math>
ถ้าหากทุก ๆ จุดยอดนั้น <math>\deg^+(v) = \deg^-(v)</math> กราฟนี้จะเป็น"กราฟสมดุล"
ความต่อเนื่องของกราฟระบุทิศทาง.
กราฟระบุทิศทาง "G" จะเรียกว่า"กราฟต่อเนื่องแบบอ่อน" (weakly connected) หรืออาจเรียกว่า"กราฟต่อเนื่อง" (connected) ก็ต่อเมื่อนำกราฟระบุทิศทางนั้นมาเปลี่ยนเส้นเชื่อมที่มีทิศทางให้กลายเป็นเส้นเชื่อมไม่มีทิศทางให้หมด แล้วกราฟไม่ระบุทิศทางที่ได้เป็นกราฟต่อเนื่อง และกราฟระบุทิศทาง "G" จะเรียกว่า"กราฟต่อเนื่องแบบเข้ม" (strongly connected) ก็ต่อเมื่อทุก ๆ วิถีจาก "u" ไป "v" มีวิถีจาก "v" ไป "u" ด้วย นอกจากนี้ "ส่วนประกอบแบบเข้ม" (strongly components) คือกราฟย่อยที่มีขนาดมากที่สุดที่เป็นกราฟต่อเนื่องแบบเข้ม แนวคิดนี้นำไปสู่การแบ่งกราฟออกเป็นหลาย ๆ ส่วนโดยการหาส่วนประกอบแบบเข้มและลบออกจากกราฟเดิมไปเรื่อย ๆ สุดท้ายจะได้ส่วนประกอบที่เชื่อมกันแบบเข้ม (strongly connected component)