FANDOM


กราฟถอดแบบ (Isomorphic Graphs)

การพิจารณาว่ากราฟ 2 กราฟ หรือมากกว่านั้น มีการเชื่อมโยงภายในกราฟเหมือนกันหรือไม่ ซึ่งถ้าทั้งสองกราฟมีการเชื่องโยงภายในกราฟเหมือนกัน ทั้งจำนวนจุดยอด และขอบที่เชื่อมโยงแต่ละจุดยอด แสดงว่าทั้งสองกราฟนั้น ถอดแบบกัน ถึงแม้ว่าตำแหน่งของจุดยอดหรือลักษณะของเส้นขอบ อาจจะไม่เหมือนกัน


นิยาม

การถอดแบบของกราฟ G และ H คือการที่จุดยอดของกราฟทั้งสองสมนัยกันแบบหนึ่งต่อหนึ่ง (Bijection)

f : V(G) -> V(H)

  เช่น เมื่อจุดยอด u ประชิดกับจุดยอด v ในกราฟ G แล้วที f(u) ประชิดกับ f(v) ในกราฟ H


จากนิยามด้านบน กราฟ เมื่อ G และ H Isomophic กัน เราเขียนได้ว่า G 11 H และ H จะเป็น Automophism ของ G

ตัวอย่าง กราฟทั้ง 2 ด้านล่าง แสดงให้เห็นการ Isomorphism แม้ว่าจะเขียนในรูปแบบที่ต่างกัน


Gg


ตามกราฟทั้งสองด้านบนนั้น จะเห็นได้ว่า มีรูปร่างที่ต่างกันโดยสิ้นเชิง แต่มีโครงสร้างและความสัมพันธ์เหมือนกันทุกประการ สังเกตุเบื้องต้นได้จากจำนวนจุดเท่ากัน จำนวนเส้นเท่ากัน เส้นและจุดที่เชื่อมกัน เหมือนกันทุกประการ ถ้าเราแทนจุดยอดของกราฟด้วย จำนวนจริงบวก 1,2,...,n จะได้สูตรตามนี้


22


ทฤษฏีของ Whitney


33


จากภาพด้านบนจะเห็นว่า กราฟทั้งสองด้านบนนั้นมีรูปร่างใกล้เคียงกัน แต่ไม่เป็นIsomorphic กัน เพราะความสัมพันธ์ระหว่างจุดแบะเส้นนั้นไม่ตรงกัน แต่ก็มีโครงสร้างตรงกัน คือ มีสามเส้น เหมือนกัน เป็นความสัมพันธ์ที่ต่างไปจากการสมมูลของกราฟ



Algorithmic approach

การสมมูลของกราฟมักจะเรียนในวิชาคณิตศาสตร์ แต่ในปัจจุบันได้มีการบูรณาการ ไปยังวิชาอื่นๆ ตามทฤษฏีของ Whitney ตั้งแต่ วิชาเคมี ฟิสิกส์ รวมถึงสาขาแยกย่อยต่างๆมากมาย ยกตัวอย่างเช่น ใช้ในการออกแบบ และคำนวณความเป็นไปได้ในการจัดวงจร และในปัจจุบันนี้ยังมีการศึกษาวิจัยเกี่ยวกับ อัลกอริทึ่ม อย่างต่อเนื่อง


นาย ชวนัท เจริญพงศ์ 51121017-1 IT

นายฉัตรชัย ก่อกตัญญู

นายธันวา