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

125px|thumb|กราฟระบุทิศทาง

ในทฤษฎีกราฟ **กราฟระบุทิศทาง** หรือ **ไดกราฟ** คือกราฟซึ่งเส้นเชื่อมมีทิศ กล่าวคือกราฟ G = (V, A) (หรืออาจจะใช้ G = (V, E) ก็ได้) โดยที่
* เซต *V* เป็นเซตซึ่งสมาชิกคือจุดยอด หรืออาจเรียกว่าโหนด หรือปม
* เซต *A* เป็นเซตของเส้นเชื่อมมีทิศทาง ซึ่งเป็นคู่อันดับของจุดยอด สำหรับเส้นเชื่อมของกราฟระบุทิศทาง อาจเรียกว่าเส้นเชื่อมมีทิศทางหรือลูกศร (และสำหรับเซตของเส้นเชื่อม (edge) นี้ ในบางครั้งอาจใช้ *E* แทน *A*)
กราฟระบุทิศทางแตกต่างจากกราฟไม่ระบุทิศทางตรงเซตของเส้นเชื่อม ซึ่งเส้นเชื่อมของกราฟระบุทิศทางจะเป็นคู่อันดับของจุดยอด ในขณะที่เส้นเชื่อมของกราฟไม่ระบุทิศทางจะเป็นคู่ไม่อันดับของจุดยอด

เนื่องจากกราฟอาจจะเป็นกราฟอย่างง่ายหรือมัลติกราฟก็ได้ บางครั้งจึงอาจเรียกประเภทเข้าไปด้วยว่า **กราฟระบุทิศอย่างง่าย** หรือ **มัลติกราฟที่มีทิศทาง** ซึ่งสำหรับมัลติกราฟนั้น *A* จะเป็นมัลติเซตแทนที่เซต เพื่อให้สามารถมีเส้นเชื่อมมากกว่า 1 เส้นระหว่างคู่ของจุดยอดได้ อย่างไรก็ตาม มัลติกราฟจะสามารถมีวงวน (เส้นเชื่อมที่ปลายทั้งสองด้านต่อกับจุดยอดจุดเดียวกัน) ได้หรือไม่ก็ยังแตกต่างกันไปตามแต่ที่กำหนดให้

## นิยามทั่วไป
เส้นเชื่อมมีทิศทาง e = (x, y)  เป็นเส้นเชื่อม*จาก* x *ไป* y โดยที่ y เรียกว่า*หัว* ส่วน x เรียกว่า*หาง*ของเส้นเชื่อม นอกจากนี้ *y* นั้นถือว่าเป็น*จุดยอดข้างหลังโดยตรง* ในขณะที่ *x* ถือว่าเป็น*จุดยอดก่อนหน้าโดยตรง* สำหรับวิถีจาก *x* ไปยัง *y* จะได้ว่า *y* เป็น*จุดยอดข้างหลัง* ส่วน *x* เป็น*จุดยอดก่อนหน้า* เส้นเชื่อมมีทิศทาง  (y, x)  จะถูกเรียกว่าเป็นเส้นเชื่อมกลับทิศของ  (x, y) 

กราฟระบุทิศทาง *D* จะถูกเรียกว่า*สมมาตร* ก็ต่อเมื่อทุก ๆ เส้นเชื่อมนั้น มีเส้นเชื่อมกลับทิศอยู่ในกราฟด้วย ในแง่การไปถึงกันได้ กราฟระบุทิศทางที่สมมาตร D จะเทียบเท่ากับกราฟไม่ระบุทิศทาง G โดยที่เส้นเชื่อม (x,y) และ (y,x) เทียบเท่ากับเส้นเชื่อม {x,y} ดังนั้น หากเปรียบเทียบระหว่างกราฟระบุทิศทางที่สมมาตรและกราฟไม่ระบุทิศทางที่เทียบเท่ากัน จะได้ว่า |*E*| = |*A*|/2

การกำหนดทิศทาง คือการนำกราฟไม่ระบุทิศทางอย่างง่ายมากำหนดทิศทางของแต่ละเส้นเชื่อมอย่างไรก็ได้ให้กลายเป็นกราฟระบุทิศทาง กราฟที่ได้จากการกำหนดทิศทางนี้เรียกว่ากราฟกำหนดทิศทาง มีคุณสมบัติคือจะไม่มีวงวนหรือวัฏจักรขนาด 2 

กราฟระบุทิศทางถ่วงน้ำหนัก คือกราฟระบุทิศทางที่เป็นกราฟถ่วงน้ำหนักด้วย อาจเรียกกราฟระบุทิศทางถ่วงน้ำหนักว่า*เครือข่าย*

การเก็บข้อมูลกราฟระบุทิศทางนั้น อาจทำได้โดยการใช้เมทริกซ์ประชิด ในกรณีที่กราฟเป็นกราฟเทียม (นั่นคือมีวงวนและเส้นเชื่อมขนานได้) เมทริกซ์เก็บข้อมูลจะเป็นเมทริกซ์ของตัวเลขขนาด n \times n โดย *n* คือจำนวนจุดยอดของกราฟ *a<sub>ij</sub>* ซึ่ง i \neq j แสดงถึงจำนวนเส้นเชื่อมมีทิศทางจากจุดยอด *i* ไป *j* ส่วน *a<sub>ii</sub>* แสดงถึงจำนวนของวงวนที่จุดยอด *i* หากเป็นกราฟอย่างง่าย จะได้ว่าเมทริกซ์ที่กล่าวมานี้จะเป็นเมทริกซ์ฐานสอง

นอกจากนี้ การเก็บข้อมูลกราฟระบุทิศทาง อาจใช้เมทริกซ์ตกกระทบก็ได้

## ระดับขั้นเข้าและระดับขั้นออก
thumb|กราฟระบุทิศทาง แต่ละจุดยอดแสดงถึง (ระดับขั้นเข้า, ระดับขั้นออก)
สำหรับจุดยอดใด ๆ *ระดับขั้น*เข้าคือจำนวนเส้นเชื่อมที่พุ่งเข้าจุดยอดนั้น ๆ (จุดยอดนั้นเป็นหัวของเส้นเชื่อม) ในขณะที่*ระดับขั้นออก*คือจำนวนเส้นเชื่อมที่พุ่งออกจากจุดยอดนั้น ๆ (จุดยอดนั้นเป็นหางของเส้นเชื่อม) สำหรับต้นไม้ ระดับขั้นออกคือระดับแตกกิ่ง

ระดับขั้นเข้าเขียนได้ว่า \deg^-(v) ส่วนระดับขั้นออกเขียนได้ว่า \deg^+(v). จุดยอดที่มี \deg^-(v)=0 เรียกว่า *ต้นทาง* ในขณะที่จุดยอดที่มี \deg^+(v)=0 เรียกว่า *ปลายทาง*

จาก*สูตรผลรวมระดับขั้น* สำหรับกราฟระบุทิศทางจะได้ว่า
: \sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) = |A|
ถ้าหากทุก ๆ จุดยอดนั้น \deg^+(v) = \deg^-(v) กราฟนี้จะเป็น*กราฟสมดุล*

## ความต่อเนื่องของกราฟระบุทิศทาง

กราฟระบุทิศทาง *G* จะเรียกว่า*กราฟต่อเนื่องแบบอ่อน* (weakly connected) หรืออาจเรียกว่า*กราฟต่อเนื่อง* (connected) ก็ต่อเมื่อนำกราฟระบุทิศทางนั้นมาเปลี่ยนเส้นเชื่อมที่มีทิศทางให้กลายเป็นเส้นเชื่อมไม่มีทิศทางให้หมด แล้วกราฟไม่ระบุทิศทางที่ได้เป็นกราฟต่อเนื่อง และกราฟระบุทิศทาง *G* จะเรียกว่า*กราฟต่อเนื่องแบบเข้ม* (strongly connected) ก็ต่อเมื่อทุก ๆ วิถีจาก *u* ไป *v* มีวิถีจาก *v* ไป *u* ด้วย นอกจากนี้ *ส่วนประกอบแบบเข้ม* (strongly components) คือกราฟย่อยที่มีขนาดมากที่สุดที่เป็นกราฟต่อเนื่องแบบเข้ม แนวคิดนี้นำไปสู่การแบ่งกราฟออกเป็นหลาย ๆ ส่วนโดยการหาส่วนประกอบแบบเข้มและลบออกจากกราฟเดิมไปเรื่อย ๆ สุดท้ายจะได้ส่วนประกอบที่เชื่อมกันแบบเข้ม (strongly connected component)

## กราฟระบุทิศทางประเภทต่าง ๆ
right|100px|thumb|กราฟอวัฏจักรระบุทิศทางอย่างง่าย
* กราฟอวัฏจักรระบุทิศทาง (directed acyclic graph: DAG) คือ กราฟระบุทิศทาง ที่ไม่มีวัฏจักร
** multitrees
** oriented trees
** rooted trees
* tournament
* quiver

## อ้างอิง

หมวดหมู่:ทฤษฎีกราฟ
หมวดหมู่:กราฟระบุทิศทาง