19,488
การแก้ไข
ล
จัดรูปแบบ +เก็บกวาดด้วยสจห.
ล (→นิยามทั่วไป) |
ล (จัดรูปแบบ +เก็บกวาดด้วยสจห.) |
||
|
[[ไฟล์:Directed.svg|125px|thumb|กราฟระบุทิศทาง]]
ใน[[ทฤษฎีกราฟ]] '''กราฟระบุทิศทาง''' หรือ '''ไดกราฟ''' คือ[[กราฟ (คณิตศาสตร์)|กราฟ]]ซึ่งเส้นเชื่อมมีทิศ กล่าวคือกราฟ ''G'' = (''V'',''A'') โดยที่▼
* [[เซต]] ''V'' เป็นเซตซึ่ง[[สมาชิก]]คือ[[จุดยอด]] หรืออาจะเรียกว่าโหนด หรือปม▼
▲ใน[[ทฤษฎีกราฟ]] '''กราฟระบุทิศทาง''' หรือ '''ไดกราฟ''' คือ[[กราฟ (คณิตศาสตร์)|กราฟ]]ซึ่งเส้นเชื่อมมีทิศ กล่าวคือกราฟ
* เซต ''A'' เป็นเซตของเส้นเชื่อมมีทิศทาง ซึ่งเป็น[[คู่อันดับ]]ของจุดยอด สำหรับเส้นเชื่อมของกราฟระบุทิศทาง อาจเรียกว่าเส้นเชื่อมมีทิศทางหรือลูกศร (และสำหรับเซตของเส้นเชื่อม (edge) นี้ ในบางครั้งอาจใช้ ''E'' แทน ''A'')
กราฟระบุทิศทางแตกต่างจาก[[กราฟไม่ระบุทิศทาง]]ตรงเซตของเส้นเชื่อม ซึ่งเส้นเชื่อมของกราฟระบุทิศทางจะเป็นคู่อันดับของจุดยอด ในขณะที่เส้นเชื่อมของกราฟไม่ระบุทิศทางจะเป็น[[คู่ไม่อันดับ]]ของจุดยอด
== นิยามทั่วไป ==
เส้นเชื่อมมีทิศทาง <math>e = (x, y) </math> เป็นเส้นเชื่อม''จาก'' <math>x</math> ''ไป'' <math>y</math> โดยที่ <math>y</math> เรียกว่า''หัว'' ส่วน <math>x</math> เรียกว่า''หาง''ของเส้นเชื่อม นอกจากนี้ ''y'' นั้นถือว่าเป็น''
กราฟระบุทิศทาง ''D'' จะถูกเรียกว่า''สมมาตร'' ก็ต่อเมื่อทุกๆเส้นเชื่อมนั้น มีเส้นเชื่อมกลับทิศอยู่ในกราฟด้วย ในแง่การไปถึงกันได้ กราฟระบุทิศทางที่สมมาตร D จะเทียบเท่ากับกราฟไม่ระบุทิศทาง G โดยที่เส้นเชื่อม (x,y) และ (y,x) เทียบเท่ากับเส้นเชื่อม {x,y} ดังนั้น หากเปรียบเทียบระหว่างกราฟระบุทิศทางที่สมมาตรและกราฟไม่ระบุทิศทางที่เทียบเท่ากัน จะได้ว่า |''E''| = |''A''|/2
การกำหนดทิศทาง คือการนำกราฟไม่ระบุทิศทางอย่างง่ายมากำหนดทิศทางของแต่ละเส้นเชื่อมอย่างไรก็ได้ให้กลายเป็นกราฟระบุทิศทาง กราฟที่ได้จากการกำหนดทิศทางนี้เรียกว่า[[กราฟกำหนดทิศทาง]] มีคุณสมบัติคือจะไม่มีวงวนหรือวัฏจักรขนาด 2 <ref>{{harvtxt|Diestel|2005}},
Section 1.10.</ref>
กราฟระบุทิศทางถ่วงน้ำหนัก คือกราฟระบุทิศทางที่เป็น[[กราฟถ่วงน้ำหนัก]]ด้วย อาจเรียกกราฟระบุทิศทางถ่วงน้ำหนักว่า''เครือข่าย''
นอกจากนี้ การเก็บข้อมูลกราฟระบุทิศทาง อาจใช้[[เมทริกซ์ตกกระทบ]]ก็ได้
== ระดับขั้นเข้าและระดับขั้นออก ==
[[ไฟล์:DirectedDegrees.svg|thumb|กราฟระบุทิศทาง แต่ละจุดยอดแสดงถึง (ระดับขั้นเข้า, ระดับขั้นออก)]]
สำหรับจุดยอดใดๆ ''ระดับขั้น''เข้าคือจำนวนเส้นเชื่อมที่พุ่งเข้าจุดยอดนั้นๆ (จุดยอดนั้นเป็นหัวของเส้นเชื่อม) ในขณะที่''ระดับขั้นออก''คือจำนวนเส้นเชื่อมที่พุ่งออกจากจุดยอดนั้นๆ (จุดยอดนั้นเป็นหางของเส้นเชื่อม) สำหรับ[[ต้นไม้_(ทฤษฎีกราฟ)|ต้นไม้]] ระดับขั้นออกคือ[[ระดับแตกกิ่ง]]
ระดับขั้นเข้าเขียนได้ว่า <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> กราฟนี้จะเป็น''กราฟสมดุล''<ref>{{citation|page=460|title=Discrete Mathematics and Graph Theory|first1=Bhavanari|last1=Satyanarayana|first2=Kuncham Syam|last2=Prasad|publisher=PHI Learning Pvt. Ltd.|isbn=978-81-203-3842-5}}; {{citation|page=51|title=Combinatorial matrix classes|volume=108|series=Encyclopedia of mathematics and its applications|first=Richard A.|last=Brualdi|publisher=Cambridge University Press|year=2006|isbn=978-0-521-86565-4}}.</ref>
== ความต่อเนื่องของกราฟระบุทิศทาง ==
{{main|ความต่อเนื่อง (ทฤษฎีกราฟ)}}
== อ้างอิง ==
| |||