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

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม

ในบรรทัด

รุ่นแก้ไขเมื่อ 21:03, 3 พฤศจิกายน 2555

ในทฤษฎีกราฟ กราฟระบุทิศทาง หรือ ไดกราฟ คือกราฟซึ่งเส้นเชื่อมมีทิศ กล่าวคือกราฟ $G=(V,A)$ (หรืออาจจะใช้ $G=(V,E)$ ก็ได้) โดยที่^[1]

เซต 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 ^[2]

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

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

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

ระดับขั้นเข้าและระดับขั้นออก

กราฟระบุทิศทาง แต่ละจุดยอดแสดงถึง (ระดับขั้นเข้า, ระดับขั้นออก)

สำหรับจุดยอดใดๆ ระดับขั้นเข้าคือจำนวนเส้นเชื่อมที่พุ่งเข้าจุดยอดนั้นๆ (จุดยอดนั้นเป็นหัวของเส้นเชื่อม) ในขณะที่ระดับขั้นออกคือจำนวนเส้นเชื่อมที่พุ่งออกจากจุดยอดนั้นๆ (จุดยอดนั้นเป็นหางของเส้นเชื่อม) สำหรับต้นไม้ ระดับขั้นออกคือระดับแตกกิ่ง

ระดับขั้นเข้าเขียนได้ว่า $\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)$ กราฟนี้จะเป็นกราฟสมดุล^[3]

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

อ้างอิง

↑ Bang-Jensen & Gutin (2000). Diestel (2005), Section 1.10. Bondy & Murty (1976), Section 10.
↑ Diestel (2005), Section 1.10.
↑ Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Discrete Mathematics and Graph Theory, PHI Learning Pvt. Ltd., p. 460, ISBN 978-81-203-3842-5; Brualdi, Richard A. (2006), Combinatorial matrix classes, Encyclopedia of mathematics and its applications, vol. 108, Cambridge University Press, p. 51, ISBN 978-0-521-86565-4.

[1] Bang-Jensen & Gutin (2000). Diestel (2005), Section 1.10. Bondy & Murty (1976), Section 10.

[2] Diestel (2005), Section 1.10.

[3] Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Discrete Mathematics and Graph Theory, PHI Learning Pvt. Ltd., p. 460, ISBN 978-81-203-3842-5; Brualdi, Richard A. (2006), Combinatorial matrix classes, Encyclopedia of mathematics and its applications, vol. 108, Cambridge University Press, p. 51, ISBN 978-0-521-86565-4.

[1]

[2]

[3]

@@ บรรทัด 1: / บรรทัด 1: @@
+[[ไฟล์:Directed.svg|125px|thumb|กราฟระบุทิศทาง]]
-ใน[[ทฤษฎีกราฟ]] '''กราฟระบุทิศทาง''' หรือ '''ไดกราฟ''' คือ[[กราฟ (คณิตศาสตร์)|กราฟ]]ซึ่งเส้นเชื่อมมีทิศ กล่าวคือกราฟ ''G'' = (''V'',''A'') โดยที่
-* [[เซต]] ''V'' เป็นเซตซึ่ง[[สมาชิก]]คือ[[จุดยอด]] หรืออาจะเรียกว่าโหนด หรือปม
+ใน[[ทฤษฎีกราฟ]] '''กราฟระบุทิศทาง''' หรือ '''ไดกราฟ''' คือ[[กราฟ (คณิตศาสตร์)|กราฟ]]ซึ่งเส้นเชื่อมมีทิศ กล่าวคือกราฟ <math>G = (V, A)</math> (หรืออาจจะใช้ <math>G = (V, E)</math> ก็ได้) โดยที่<ref>{{harvtxt|Bang-Jensen|Gutin|2000}}. {{harvtxt|Diestel|2005}}, Section 1.10. {{harvtxt|Bondy|Murty|1976}}, Section 10.</ref>
+* [[เซต]] ''V'' เป็นเซตซึ่ง[[สมาชิก]]คือ[[จุดยอด]] หรืออาจเรียกว่าโหนด หรือปม
 * เซต ''A'' เป็นเซตของเส้นเชื่อมมีทิศทาง ซึ่งเป็น[[คู่อันดับ]]ของจุดยอด สำหรับเส้นเชื่อมของกราฟระบุทิศทาง อาจเรียกว่าเส้นเชื่อมมีทิศทางหรือลูกศร (และสำหรับเซตของเส้นเชื่อม (edge) นี้ ในบางครั้งอาจใช้ ''E'' แทน ''A'')
 กราฟระบุทิศทางแตกต่างจาก[[กราฟไม่ระบุทิศทาง]]ตรงเซตของเส้นเชื่อม ซึ่งเส้นเชื่อมของกราฟระบุทิศทางจะเป็นคู่อันดับของจุดยอด ในขณะที่เส้นเชื่อมของกราฟไม่ระบุทิศทางจะเป็น[[คู่ไม่อันดับ]]ของจุดยอด
@@ บรรทัด 7: / บรรทัด 9: @@
 == นิยามทั่วไป ==
-เส้นเชื่อมมีทิศทาง <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>
+เส้นเชื่อมมีทิศทาง <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 <ref>{{harvtxt|Diestel|2005}}, Section 1.10.</ref>
+การกำหนดทิศทาง คือการนำกราฟไม่ระบุทิศทางอย่างง่ายมากำหนดทิศทางของแต่ละเส้นเชื่อมอย่างไรก็ได้ให้กลายเป็นกราฟระบุทิศทาง กราฟที่ได้จากการกำหนดทิศทางนี้เรียกว่า[[กราฟกำหนดทิศทาง]] มีคุณสมบัติคือจะไม่มีวงวนหรือวัฏจักรขนาด 2 <ref>{{harvtxt|Diestel|2005}},
+Section 1.10.</ref>
 กราฟระบุทิศทางถ่วงน้ำหนัก คือกราฟระบุทิศทางที่เป็น[[กราฟถ่วงน้ำหนัก]]ด้วย อาจเรียกกราฟระบุทิศทางถ่วงน้ำหนักว่า''เครือข่าย''
@@ บรรทัด 18: / บรรทัด 21: @@
 นอกจากนี้ การเก็บข้อมูลกราฟระบุทิศทาง อาจใช้[[เมทริกซ์ตกกระทบ]]ก็ได้
+== ระดับขั้นเข้าและระดับขั้นออก ==
+[[ไฟล์: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|ความต่อเนื่อง (ทฤษฎีกราฟ)}}
 == อ้างอิง ==