ในทฤษฎีกราฟ กราฟสองกราฟ${\displaystyle G}$และ${\displaystyle G'}$กราฟจะเป็นโฮมีโอเมอร์ฟิกกันหากมีไอโซมอร์ฟิซึมของกราฟจากการแบ่งย่อย บางส่วน ของ${\displaystyle G}$ไปยังส่วนย่อยบางส่วนของ${\displaystyle G'}$หากขอบของกราฟถูกมองว่าเป็นเส้นที่ลากจากจุดยอด หนึ่ง ไปยังอีกจุดยอดหนึ่ง (ดังที่มักแสดงในแผนภาพ) แล้วกราฟสองกราฟจะสมมูลกันในความหมายเชิงทฤษฎีกราฟก็ต่อเมื่อแผนภาพของกราฟทั้งสองสมมูลกันในความหมายเชิงโทโพโลยี^{[ 1 ]}

โดยทั่วไปการแบ่งย่อยกราฟG (บางครั้งเรียกว่าการขยาย^{[ 2 ]} ) คือกราฟที่ได้จากการแบ่งย่อยขอบในG การแบ่งย่อยขอบ eบางขอบที่มีจุดปลาย { u , v } จะได้กราฟที่มีจุดยอดใหม่w หนึ่งจุด และมีเซตขอบที่แทนที่eด้วยขอบใหม่สองขอบคือ { u , w } และ { w , v } สำหรับขอบที่มีทิศทาง การดำเนินการนี้จะต้องรักษาทิศทางการแพร่กระจายของขอบนั้นไว้

ตัวอย่างเช่น ขอบeที่มีจุดปลาย { u , v }:

สามารถแบ่งย่อยออกเป็นสองขอบ คือe และe ซึ่งเชื่อมต่อกับจุดยอดใหม่wที่มีดีกรี -2 หรือดีกรีขาเข้า -1 และดีกรีขาออก -1 สำหรับขอบแบบมีทิศทาง:

การพิจารณาว่ากราฟGและHนั้น เป็น โฮมีโอเมอร์ฟิกกับกราฟย่อยของGหรือไม่นั้น เป็นปัญหาNP-complete ^{[ 3 ]}

เป็นที่ชัดเจนว่าการแบ่งกราฟออกเป็นส่วนย่อยๆ จะช่วยรักษาสภาพระนาบไว้ได้ ทฤษฎีบทของคุราตอฟสกีกล่าวว่า

กราฟจำกัดจะเป็นกราฟระนาบก็ต่อเมื่อไม่มีกราฟย่อย ใดที่เป็น โฮโมมอร์ฟิกกับK ( กราฟสมบูรณ์บนห้าจุดยอด) หรือK ( กราฟสองส่วนสมบูรณ์บนหกจุดยอด ซึ่งสามจุดเชื่อมต่อกับอีกสามจุดที่เหลือ)

อันที่จริง กราฟที่มีลักษณะสมมาตรกับK หรือK เรียกว่า กราฟย่อยคุราทอฟสกี้ (Kuratowski subgraph )

ข้อสรุปทั่วไปที่ได้จากทฤษฎีบทโรเบิร์ตสัน-เซย์มัวร์ระบุว่า สำหรับจำนวนเต็มg แต่ละตัว จะมีเซตของกราฟ ที่ขัดขวางอยู่จำนวนจำกัด${\displaystyle L(g)=\left\{G_{i}^{(g)}\right\}}$โดยที่กราฟHสามารถฝังลงบนพื้นผิวที่มีจีนัสg ได้ ก็ต่อเมื่อHไม่มีสำเนาโฮมีโอเมอร์ฟิกของกราฟใดๆ เลย${\displaystyle G_{i}^{(g)\!}}$. ตัวอย่างเช่น,${\displaystyle L(0)=\left\{K_{5},K_{3,3}\right\}}$ประกอบด้วยซับกราฟของ Kuratowski

ในตัวอย่างต่อไปนี้ กราฟGและกราฟHเป็นกราฟโฮมีโอเมอร์ฟิกกัน

กราฟG

กราฟH

ถ้าG′คือกราฟที่เกิดจากการแบ่งขอบด้านนอกของGและH′คือกราฟที่เกิดจากการแบ่งขอบด้านในของHแล้วG′และH′จะมีวิธีการวาดกราฟที่คล้ายคลึงกัน:

กราฟG′ , H′

ดังนั้น จึงมีความสมมาตรกันระหว่างG'และH'ซึ่งหมายความว่าGและHเป็นโฮมีโอเมอร์ฟิกกัน

กราฟผสม

กราฟผสมต่อไปนี้เป็นกราฟโฮมีโอเมอร์ฟิกกัน โดยแสดงให้เห็นว่าขอบที่มีทิศทางจะมีหัวลูกศรอยู่ตรงกลาง

กราฟG

กราฟH

• วิชาโท (ทฤษฎีกราฟ)
• การหดตัวของขอบ

• เยลเลน, เจย์; กรอสส์, โจนาธาน แอล. (2005), ทฤษฎีกราฟและการประยุกต์ใช้ , คณิตศาสตร์เชิงดิสครีตและการประยุกต์ใช้ (  ฉบับที่ 2), แชปแมน แอนด์ ฮอลล์/ซีอาร์ซี, ISBN 978-1-58488-505-4