ทฤษฏีกราฟ

 โครงสร้างข้อมูลกราฟ

ดูบทความหลักที่ กราฟ (โครงสร้างข้อมูล)

มีหลายวิธีในการจัดเก็บกราฟในระบบคอมพิวเตอร์ โดยโครงสร้างข้อมูลที่ใช้ขึ้นอยู่กับโครงสร้างของกราฟ และอัลกอริทึมสำหรับประมวลผลกราฟนั้น ในทางทฤษฎีเราอาจแยกแยะโครงสร้างที่เป็นแบบรายการกับที่เป็นเมทริกซ์ได้ แต่ในทางปฏิบัติมักพบว่าโครงสร้างที่ดีมักเป็นลูกผสมของโครงสร้างทั้งสองแบบ โครงสร้างแบบรายการนั้นมักใช้ในกรณีของกราฟเบาบาง (sparse graph) เนื่องจากมีการใช้หน่วยความจำที่น้อยกว่า ในทางกลับกันโครงสร้างแบบเมทริกซ์นั้น มีการเข้าถึงที่รวดเร็วกว่า แต่ก็ใช้หน่วยความจำขนาดใหญ่ถ้าจำนวนจุดยอดของกราฟมีมาก

 โครงสร้างแบบรายการ

 โครงสร้างแบบเมทริกซ์

  • เมทริกซ์ตกกระทบ (incidence matrix) – เป็นการจัดเก็บกราฟในเมทริกซ์ขนาด E (จำนวนเส้นเชื่อม) คูณ V (จำนวนจุดยอด) ซึ่ง [เส้นเชื่อม, จุดยอด] จะบรรจุข้อมูลของเส้นเชื่อมนั้น (เช่น 1 คือ เชื่อมต่อกัน, 0 คือ ไม่เชื่อมต่อกัน)
  • เมตริกซ์ประชิด (adjacency matrix) – เป็นการจัดเก็บกราฟในเมทริกซ์ขนาด N คูณ N เมื่อ N คือจำนวนของจุดยอดในกราฟ ถ้ามีเส้นเชื่อมจากจุดยอด x ไปจุดยอด y แล้ว สมาชิก Mx,y จะเป็น 1 ไม่เช่นนั้น จะเป็น 0 ซึ่งทำให้ง่ายต่อการหากราฟย่อย และกราฟย้อนกลับ
  • เมตริกซ์แบบลาปลัส (Laplacian matrix หรือ admittance matrix)

 การจำแนกชนิดของกราฟ

ตามลักษณะข้อมูลที่เก็บ
  • กราฟแบบมีทิศทาง (directed graph) และ กราฟแบบไม่มีทิศทาง (undirected graph)
  • กราฟแบบมีน้ำหนัก (weighted graph) และ กราฟแบบไม่มีน้ำหนัก (unweighted graph)
ตามการเชื่อมโยง
  • กราฟสมบูรณ์ (complete graph)
  • กราฟต่อเนื่อง (connected graph)
  • กราฟไม่ต่อเนื่อง (unconnected graph)
  • ต้นไม้ (โครงสร้างข้อมูล) (tree)

 ทฤษฎีบทและปัญหาบนกราฟ

 การค้นหากราฟย่อย

 การระบายสีกราฟ

ปัญหาเส้นทาง

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s

%d bloggers like this: