Internet & Web Application

เรื่องของ Graph Theory #2 : Graph Category

สรุปความจากเอกสารบทเรียนเรื่อง Graph Theory – ชนิดของ Graph

  • บทที่ 8 Graph โดย ดร. อรรจน์ โกญจนาท

สรุป Graph Theory :

Graph นิยามด้วย Tuple ที่ประกอบไปด้วยเซตของ Vertex และเซตของ Edge,
Graph ถูกกำหนดชนิด ด้วยลักษณะการเชื่อมต่อของ Edge

Edge คือเซตของ (Un)Ordered Pair ที่สร้างจากสมาชิกในเซตของ Vertex

ชนิดของ Graph

Simple Graph : เซตของ Edge มีสมาชิกเป็น Unordered Pair ที่ไม่ซ้ำกันเลย .. นั่นคือระหว่าง Vertex ของจุดจะมีได้เพียงหนึ่ง Edge เป็นเส้นเชื่อมเท่านั้น

Multigraph : ในแต่ละ Edge ยังคงมีสมาชิกเป็น Unordered Pair อยู่ .. แต่ เพิ่มเติมขึ้นจาก Simple Graph ที่สามารถมีเส้นเชื่อมระหว่าง Vertex ได้มากกว่าหนึ่งเส้นเชื่อม

เปรียบเทียบกับ Computer Network ที่มี Redundancy Link

Psuedograph : ในแต่ละ Edge ยังคงมีสมาชิกเป็น Unordered Pair อยู่ .. แต่เพิ่มเติมจาก Multigraph ขึ้นมาอีกขั้นคือ Edge สามารถเชื่อม Vertex ตัวหนึ่งตัวใด เข้าหาตัวเองได้ .. และเรียก Edge นั้นว่า Loop

โดยใน Computer Network ก็อาศัย Loop แทนการรับส่งข้อมุลระหว่างตนเอง เพื่อทดสอบ Logic ภายใน Host เอง

… จะเห็นว่าที่ผ่านมา สมาชิกของ Edge เป็น Unordered Pair ทั้งหมด เรียกว่า Undirected Edge ทำให้ Graph ชนิดที่กล่าวข้างต้น เรียกว่า Undirected Graph , ซึ่งต่อไป จะขอแนะนำ Graph ที่มี Directed Edge

Directed Graph : เหมือน Simple Graph แต่เนื่องจาก Edge มีทิศทาง .. ดังนั้น Edge ที่ทิศทางตรงข้างกัน แม้จะเชื่อม Vertex คู่เดียวกัน ก็ถือว่าเป็นคนละ Edge ไม่ซ้ำกัน .. และสามารถมี Loop ได้

Directed Multigraph : ก็คือ Multigraph ที่ Edge มีทิศทาง พร้อมกับสามารถมี Loop ได้

สรุป

การแยกแยะชนืดของ Graph

สามารถนำไปประยุกต์ใช้เพื่อ Model ปัญหาในสภาวะจริงได้ เช่น การจำลองความสัมพันธ์ระหว่างบุคคลในรูปแบบของ Simple Graph

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