ทฤษฎีกราฟ 3
Bipartite graph คือ กราฟที่สามารถแบ่งออกเป็นสองส่วน
โดยทั้งสองส่วนนั้นจะมีเส้นเชื่อมเชื่อมกันแต่จะไม่มีเส้นเชื่อมภายในส่วนเดียวกัน
จากภาพจะพบว่าสามารถแบ่งกราฟออกเป็นสองส่วน
โดยแต่ละจุดยอดของกลุ่ม 1จะมีเส้นเชื่อมไปยังกลุ่ม
2 ทุกเส้นแต่ไม่มีเส้นใดเลยที่เชื่อมกันเองภายในกลุ่ม
การแทนที่กราฟและการสมสัณฐานของกราฟ (Representing graph and graph Isomorphism)
การแทนที่กราฟด้วย Adjacency matrix แบ่งเป็น
แบบไม่มีทิศทางและแบบมีทิศทาง
จากภาพเป็นการแทนที่กราฟด้วย
Adjacency Matrix กราฟเป็นแบบไม่มีทิศทาง
จุดยอดที่มีเส้นเชื่อมไปยังอีกจุดยอดหนึ่งจะแทนด้วย เลข 1 แต่ถ้าไม่มีจะแทนด้วย
เลข 0 ในกรณีที่กราฟนั้นเป็นกราฟเชิงเดียวหรือ simple
graph โดยอันดับแรกจะเขียนจุดยอดที่หลักและแถว จากนั้นให้สังเกตแต่ละจุดยอดว่ามีเส้นเชื่อมไปยังจุดใดบ้างให้ทำแบบนี้ไปเรื่อยๆจนถึงจุดยอดสุดท้าย
ภาพถัดมาเป็นการแทนที่กราฟด้วย
Adjacency matrix กราฟเป็นกราฟแบบมีทิศทาง
มีหลักการเดียวกันกับการแทนที่กราฟด้วย Adjacency matrix แบบไม่มีทิศทางแต่ผลลัพธ์จะแตกต่างกัน
โดยบริเวณที่วงกลมสีฟ้าจะเป็นบริเวณที่แตกต่างกันระหว่างทั้งสองกราฟ
Incident Matrix คือ การแทนที่กราฟด้วยเมทริกซ์โดยมีแถวเป็นจุดยอด
และหลักเป็นเส้นเชื่อม
ภาพประกอบจาก
https://www.skedsoft.com/books/discrete-mathematics/incidence-matrices
มีหลักการเช่นเดียวกับ
Adjacency matrix แตกต่างกันที่ incident matrix
หลักจะเป็นเส้นเชื่อม แต่ Adjacency matrix เป็น
จุดยอด
Graph Isomorphism
หรือการสมสัณฐานของกราฟ
คือ
เมื่อกราฟอย่างง่าย G1 = (V1,E1) และ G2
= (V2,E2) เป็นฟังก์ชัน 1-1 และทั่วถึง จาก V1
ไป V2 และจุด a ประชิด
จุด b บน G1 และมีจุด f(a) ประชิดจุด f(b) บน
G2 จะเรียก function นั้นว่าเป็น Isomorphism
function หากกราฟทั้งสองไม่มีคุณสมบัติข้างต้นจะเป็น Non
isomorphism Graph
จากตารางพบว่าจุด a จากกราฟ G ตรงกับจุด 1 จากกราฟ H เราสามารถตรวจสอบกราฟดังกล่าวได้โดยการเทียบกราฟ
G และ H ว่ามีจำนวนเส้นเชื่อมเท่ากัน จำนวนจุดยอดเท่ากัน
แล้วเชื่อมกับจุดยอดเดียวกันหรือไม่ หรือสามารถใช้ Adjacency matrix เข้ามาช่วยในการพิสูจน์ได้
พบว่ากราฟ G และ กราฟ H เป็นกราฟสมสัณฐานกัน
เนื่องจาก เมทริกซ์ของ G และ H เท่ากัน
ความคิดเห็น
แสดงความคิดเห็น