Internet & Web Application

เรื่องของ Graph Theory #3 : Graph Terminology

สรุปความจากเอกสารบทเรียนเรื่อง Graph Theory – คำศัพท์เกี่ยวเนื่องในการศึกษา Graph Theory

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

สรุป Graph Theory : คำศัพท์ใน Graph Theory

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

Graph Terminology

ในสมมติฐานว่า เป็น Undirected Graph

Adjacent หรือ Neighbor ใช้กำหนดคุณสมบัติของ Vertex ที่เชิ่อมถึงกันด้วย Edge เพียง Edge เดียว

Incident ใช้กำหนดคุณสมบัติของ Edge ว่าเชื่อมกับ Vertext ใด เช่น ea = (va1 , va2) และเรียก Vertex ทีถูกเชื่อมต่อทั้งสองว่า Endpoint

Degree of Vertext คือจำนวน c, Edge ที่ Incident กับ Vertex นั้น ซึ่งเขียนได้ว่า deg(e) = c เช่น deg(a) = 2 , deg(b) = 4 , เป็นต้น

ถ้ามี Degree เป็นศูนย์ เรียกว่า Isolated , ถ้ามี Degree เป็นหนึ่งเรียกกว่า Pendant

Theorem ที่เกี่ยวข้อง

ถ้าหากเป็น Directed Graph

ให้ Edge, e = (u, v) จะได้ว่า u ->v โดยเรียก Initial Vertex, u ว่าได้ Adjacent to v และ เรียก Terminal Vertex, v ว่าได้ Adjacent from u

สำหรับ Directed Edge ที่เข้า v จะมี In-degree ตามจำนวน Edge ที่มี v เป็น Terminal Vertex เขียนแทนว่า Deg(v)

ส่วน u จะมี Out-degree ตามจำนวน Edge ที่มี v เป็น Initial Vertex เขียนแทนว่า Deg+(v)

jjj

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