ข้ามไปเนื้อหา

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

ไม่มีความย่อการแก้ไข
 
== นิยามทั่วไป ==
เส้นเชื่อมมีทิศทาง <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>
 
กราฟระบุทิศทางถ่วงน้ำหนัก คือกราฟระบุทิศทางที่เป็น[[กราฟถ่วงน้ำหนัก]]ด้วย อาจเรียกกราฟระบุทิศทางถ่วงน้ำหนักว่า''เครือข่าย''
 
การเก็บข้อมูลกราฟระบุทิศทางนั้น อาจทำได้โดยการใช้[[เมทริกซ์ประชิด]] ในกรณีที่กราฟเป็น[[กราฟเทียม]] (นั่นคือมีวงวนและเส้นเชื่อมขนานได้) [[เมทริกซ์]]เก็บข้อมูลจะเป็นเมทริกซ์ของตัวเลขขนาด <math>n \times n</math> โดย ''n'' คือจำนวนจุดยอดของกราฟ ''a_{ij}'' ซึ่ง <math>i \neq j</math> แสดงถึงจำนวนเส้นเชื่อมมีทิศทางจากจุดยอด ''i'' ไป ''j'' ส่วน ''a_{ii}'' แสดงถึงจำนวนของวงวนที่จุดยอด ''i'' หากเป็น[[กราฟอย่างง่าย]] จะได้ว่าเมทริกซ์ที่กล่าวมานี้จะเป็น[[เมทริกซ์ฐานสอง]]
 
นอกจากนี้ การเก็บข้อมูลกราฟระบุทิศทาง อาจใช้[[เมทริกซ์ตกกระทบ]]ก็ได้
 
== อ้างอิง ==