สรุปความจากเอกสารบทเรียนเรื่อง Graph Theory – รู้จัก Simple Graph ให้มากชนิดขึ้น จากนั้นลองดูว่า Simple Graph จะสามารถเป็น Bipartite Graph ได้อย่างไร
การกระทำเพื่อให้ได้ Graph ใหม่จาก Graph เดิม .. ทั้งตัดและต่อ
- บทที่ 8 Graph โดย ดร. อรรจน์ โกญจนาท
- Wikipedia เรื่อง Completed Graph
- Wikipedia เรื่อง Circle Graph
- Wikipedia เรื่อง Wheel Graph
- Wikipedia เรื่อง Bipartite 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 ได้