Internet & Web Application

เรื่องของ Graph Theory #4 : Simple Graph, Bipartite Graph และการสร้าง Graph ใหม่จาก Graph เดิม

สรุปความจากเอกสารบทเรียนเรื่อง Graph Theory – รู้จัก Simple Graph ให้มากชนิดขึ้น จากนั้นลองดูว่า Simple Graph จะสามารถเป็น Bipartite Graph ได้อย่างไร

การกระทำเพื่อให้ได้ Graph ใหม่จาก Graph เดิม .. ทั้งตัดและต่อ

สรุป Graph Theory : Simple Graph

AYK : G = (V, E) ซึ่ง E = { ea , eb , … } = { (va1 , va2) , (vb1 , vb2) , … } และสามารถทบทวนเรื่องชนิดของ Graph ได้ที่ Graph Category

Simple Graph

Simple Graph คือ Undirected Graph ที่มี Edge ที่ Pair ของ End Point ไม่ซ้ำกัน, ea != eb สำหรับทุกค่า a, b ที่ a != b

Completed Graph

คือ Simple Graph ที่ทุกคู่ Vertex ใน Graph ถูก Connected โดย Edge

Cycle “เริ่มต้น, วนตามลำดับ, กลับมาที่เดิม”

สำหรับ V = {v1 , v2 , … , vn} ให้มี Edge เป็น E = { (v1 , v2) , (v2 , v3) , … , (vn-1 , vn) , (vn , v1) }

ข้อสังเกตอีกอย่างคือ ทุก Vertex ใน Graph : Circle จะต้องมี Degree เท่ากับ 2 เท่ากันทั้งหมด

บางครั้ง อาจเรียก Odd Circle หรือ Even Circle ตามจำนวน Vertex ใน Graph ได้

wheel “มี Cycle ก่อน แล้วเพิ่ม Vertex ที่ Adjacent กับทุก Vertex”

n-Cubes

Vertex ที่อยู่ภายใน Graph ดังกล่าวถูกกำหนดให้มีจำนวนเท่ากับ 2 n ซึ่งลำดับของ Vertex จะเป็นตัวกำหนดว่า Vertex ใดบ้างต้องเชื่อมกัน

กฏการเชื่อมต่อ : เมื่อ “ลำดับ” ถูกแตกออกเป็น Bit , ถ้าระหว่าง Vertex ที่ Bit ใดๆ ณ. ตำแหน่งเดียวกัน มีค่าต่างกันเพียง 1 Bit .. ทั้งสองจะ Adjacent กัน

Bipartite Graph

จาก Simple Graph เราสามารถแบ่งให้ออกเป็น Disjoint Set ของ Vertex ได้ .. กล่าวคือ ภายในแต่ละเซต ที่ถูกแบ่ง จะไม่มี Edge ที่เชื่อมกันระหว่างสมาชิกภายในเซตกันเองเลย

ตัวอย่าง เมื่อแบ่ง V ออกเป็น {a , b , d} และ {c , e , f , g}

  • ทุก Tree และ ทุก Even Circle Graph ต่างก็เป็น Bipartite Graph
  • ใช้เพื่อแก้ปัญหาเรื่อง Matching Problem

Subgraph และ Union ของ Graph

ตัด Edge หรือ End Point (Vertex) ที่ไม่ต้องการออก เพื่อให้ได้ Subgraph โดยมีนิยามดังนี้

Subgraph ของ G = ( V, E ) คือ H = ( W , F ) โดยที่ W V และ F E

ซึ่งในทางกลับกัน เมื่อแยกได้ ก็สามารถ Union ให้ Subgraph กลับเป็น Graph ได้

มาตรฐาน

ใส่ความเห็น