ผลต่างระหว่างรุ่นของ "กราฟระบุทิศทาง"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข |
ล เริ่มบทความ ป้ายระบุ: ผู้ใช้แก้หน้าเปลี่ยนทาง |
||
บรรทัด 1:
ใน[[ทฤษฎีกราฟ]] '''กราฟระบุทิศทาง''' หรือ '''ไดกราฟ''' คือ[[กราฟ (คณิตศาสตร์)|กราฟ]]ซึ่งเส้นเชื่อมมีทิศ กล่าวคือกราฟ ''G'' = (''V'',''A'') โดยที่
* [[เซต]] ''V'' เป็นเซตซึ่ง[[สมาชิก]]คือ[[จุดยอด]] หรืออาจะเรียกว่าโหนด หรือปม
* เซต ''A'' เป็นเซตของเส้นเชื่อมมีทิศทาง ซึ่งเป็น[[คู่อันดับ]]ของจุดยอด สำหรับเส้นเชื่อมของกราฟระบุทิศทาง อาจเรียกว่าเส้นเชื่อมมีทิศทางหรือลูกศร (และสำหรับเซตของเส้นเชื่อม (edge) นี้ ในบางครั้งอาจใช้ ''E'' แทน ''A'')
กราฟระบุทิศทางแตกต่างจาก[[กราฟไม่ระบุทิศทาง]]ตรงเซตของเส้นเชื่อม ซึ่งเส้นเชื่อมของกราฟระบุทิศทางจะเป็นคู่อันดับของจุดยอด ในขณะที่เส้นเชื่อมของกราฟไม่ระบุทิศทางจะเป็น[[คู่ไม่อันดับ]]ของจุดยอด
เนื่องจากกราฟอาจจะเป็น[[กราฟอย่างง่าย]]หรือ[[มัลติกราฟ]]ก็ได้ บางครั้งจึงอาจเรียกประเภทเข้าไปด้วยว่า '''กราฟระบุทิศอย่างง่าย''' หรือ '''มัลติกราฟที่มีทิศทาง''' ซึ่งสำหรับมัลติกราฟนั้น ''A'' จะเป็น[[มัลติเซต]]แทนที่เซต เพื่อให้สามารถมีเส้นเชื่อมมากกว่า 1 เส้นระหว่างคู่ของจุดยอดได้ อย่างไรก็๋ตาม มัลติกราฟจะสามารถมี[[วงวน]] (เส้นเชื่อมที่ปลายทั้งสองด้านต่อกับจุดยอดจุดเดียวกัน) ได้หรือไม่ก็ยังแตกต่างกันไปตามแต่ที่กำหนดให้
== นิยามทั่วไป ==
เส้นเชื่อมมีทิศทาง <math>e = (x, y)</math> เป็นเส้นเชื่อม''จาก'' <math>x</math> ''ไป'' <math>y</math> โดย <math>y</math> เรียกว่า''หัว'' ส่วน ''x'' เรียกว่า''หาง''ของเส้นเชื่อมมีทิศทาง ''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>
[[en:directed graph]]
| |||