Internet & Web Application

เรื่องของ Graph Theory #5 : Data Structure for Graph

สรุปความจากเอกสารบทเรียนเรื่อง Graph Theory – Data Structure for Graph เพื่อสามารถนำ Graph Theory ไปประยุกต์ใช้งานใน Computer ได้

สรุป Graph Theory : Data Structure for Graph

AYK : G = (V, E) ซึ่ง E = { ea , eb , … } = { (va1 , va2) , (vb1 , vb2) , … }

Graph Reresentation

วิธีเก็บ Graph ในหน่วยความจำ

เก็บแบบ Adjacency

ในกรณีที่ Graph ไม่มี Multiple Edge จะสามารถเก็บ Graph โดยอาศัยความสัมพันธ์ ของการเป็น Neighbor ระหว่างกันของ Vertex ได้ : “Vertex ใด ต่อกับ Vertex ใดบ้าง”

สามารถเก็บได้ในแบบ Link List และ Matrix สามารถดูเพิ่มเติมได้จาก “เรื่องของ Graph Theory #1 : Wiki – Overview

เก็บแบบ Incidence

สำหรับกรณีทั่วไป รวมถึง หาก Graph มี Multiple Edge .. จำเป็นต้องเก็บ Graph ตามความสัมพันธ์ระหว่าง Vertex กับ Edge : “Vertex ใด ต่อกับ Edge ใดบ้าง”

สามารถเก็บได้ในแบบ Link List และ Matrix สามารถดูเพิ่มเติมได้จาก “เรื่องของ Graph Theory #1 : Wiki – Overview

ลักษณะปัญหาและการแก้ปัญหา

ปัญหาในชีวิตจริง ถูก Model ในรูปของ Graph จากนั้น สร้างโครงสร้างข้อมูล เก็บ Graph เพื่อคำนวณใน Computer ด้วย Algorithm ที่มีผู้นำเสนอ

ส่วนใหญ่คำถาม และคำสั่งที่มักถูกประมวลผล คือ

  • ถ้า Vertex i เชื่อม Vertex j ให้ …
  • สำหรับทุก Edge ใน Graph ให้ …
  • สำหรับทุก Edge ที่ออกจาก (Directed Edge) Vertex ให้ …
  • สำหรับทุก Edge ที่เข้าไป Vertex ให้ …

ผลที่ได้สรุปได้ว่า Algorithm จะ Take Time แตกต่างกันตาม Data Structure

ต่างต่างกันในแง่ของ Memory ที่ใช้

Graph Isomorphism

พูดเรื่อง Graph สองอันที่ มีรูปแบบเหมือนกัน กล่าวคือ มีความสัมพันธ์ แบบ 1-ต่อ-1 ทั้งเซตของ Vertex และเซตของ Edge .. ปัญหาคือ จะทราบได้อย่างไรว่า Graph ทั้งสองเป็น Isomorphism

Algorithm ที่ใช้ทดสอบว่า Graph สองอัน Isomorphic หรือไม่พบว่าเป็น Exponential Worst Case Time Complexity กับจำนวนของ Vertices

อย่างไรก็ตาม ปัญหาจำพวกนี้สามารถแก้ได้โดย Algorithm ที่เป็น Linear Average-Case Time Complexity และ หวังว่าในอนาคตจะสามารถหา Algorithm ที่เป็น Polynomial Worst-Case Time Complexity

Algorithm ที่ดีที่สุดปัจจุบัน ชื่อ “NAUTY” สามารถคำนวณ Isomorphism ของกราฟ 100 Vertices ได้ภายในหนึ่งวินาที

_

Advertisements
มาตรฐาน

ใส่ความเห็น

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