Homeomorfismus (teorie grafů) - Homeomorphism (graph theory) - Wikipedia

v teorie grafů, dva grafy ${ displaystyle G}$ a ${ displaystyle G '}$ jsou homeomorfní pokud existuje izomorfismus grafu od některých pododdělení z ${ displaystyle G}$ některým pododdělení z ${ displaystyle G '}$ . Pokud jsou okraje grafu považovány za čáry nakreslené z jednoho vrcholu do druhého (jak jsou obvykle znázorněny na ilustracích), pak jsou dva grafy navzájem homeomorfní v graficko-teoretickém smyslu, pokud jsou homeomorfní ve smyslu, ve kterém je tento výraz používán topologie.^[1]

Rozdělení a vyhlazení

Obecně platí, že pododdělení grafu G (někdy známý jako expanze^[2]) je graf vyplývající z dělení hran v G. Rozdělení nějaké hrany E s koncovými body {u,proti} získá graf obsahující jeden nový vrchol was výměnou sady okrajů E o dva nové okraje, {u,w} a {w,proti}.

Například hrana E, s koncovými body {u,proti}:

lze rozdělit na dva okraje, E₁ a E₂, připojení k novému vrcholu w:

Zpětná operace, vyhlazení nebo vyhlazení vrchol w s ohledem na dvojici hran (E₁, E₂) incident na w, odstraní oba okraje obsahující w a nahradí (E₁, E₂) s novou hranou, která spojuje ostatní koncové body páru. Zde je zdůrazněno, že lze vyhladit pouze 2mocné vrcholy.

Například jednoduché připojeno graf se dvěma hranami, E₁ {u,w} a E₂ {w,proti}:

má vrchol (jmenovitě w) které lze vyhladit, což má za následek:

Určení, zda pro grafy G a H, H je homeomorfní k podgrafu G, je NP-kompletní problém.^[3]

Barycentrické členění

The barycentrické dělení rozděluje každou hranu grafu. Toto je speciální dělení, protože vždy vede k bipartitní graf. Tento postup lze opakovat, takže n^th barycentrické dělení je barycentrické dělení n−1^th barycentrické členění grafu. Druhé takové dělení je vždy a jednoduchý graf.

Vkládání na povrch

Je zřejmé, že rozdělení grafu zachovává rovinnost. Kuratowského věta tvrdí, že

A konečný graf je rovinný kdyby a jen kdyby obsahuje č podgraf homeomorfní na K.₅ (kompletní graf na pět vrcholy ) nebo K._3,3 (kompletní bipartitní graf na šesti vrcholech, z nichž tři se připojují ke každému z ostatních tří).

Ve skutečnosti je to graf homeomorfní K.₅ nebo K._3,3 se nazývá a Kuratowského podgraf.

Zobecnění vyplývající z Věta Robertson – Seymour, tvrdí, že pro každé celé číslo G, existuje konečný překážková sada grafů ${ displaystyle L (g) = vlevo {G_ {i} ^ {(g)} vpravo }}$ takový, že graf H je vložitelné na povrch rod G kdyby a jen kdyby H neobsahuje žádnou homeomorfní kopii žádného z ${ displaystyle G_ {i} ^ {(g)}}$ . Například, ${ displaystyle L (0) = vlevo {K_ {5}, K_ {3,3} vpravo }}$ sestává z Kuratowských podgrafů.

Příklad

V následujícím příkladu je graf G a graf H jsou homeomorfní.

Graf G

Graf H

Li G' je graf vytvořený rozdělením vnějších okrajů G a H ' je graf vytvořený rozdělením vnitřní hrany H, pak G' a H ' mít podobnou kresbu grafu:

Graf G', H '

Proto mezi nimi existuje izomorfismus G' a H ', význam G a H jsou homeomorfní.

Viz také

Reference

^ Archdeacon, Dan (1996), „Topologická teorie grafů: průzkum“, Průzkumy v teorii grafů (San Francisco, CA, 1995), Congressus Numerantium, 115, str. 5–54, PAN 1411236, Název vzniká, protože ${ displaystyle G}$ a ${ displaystyle H}$ jsou homeomorfní jako grafy právě tehdy, pokud jsou homeomorfní jako topologické prostory
^ Trudeau, Richard J. (1993). Úvod do teorie grafů (Opravené, rozšířené publikování. Ed.). New York: Dover Pub. p. 76. ISBN 978-0-486-67870-2. Citováno 8. srpna 2012. Definice 20. Pokud jsou k některým okrajům grafu přidány nové vrcholy stupně 2 G, výsledný graf H se nazývá expanze z G.
^ Častěji studovaným problémem v literatuře, pod názvem problému subomorfního homeomorfismu, je to, zda se jedná o dělení H je izomorfní s podgrafem G. Případ, kdy H je n-vertexový cyklus je ekvivalentní k Hamiltonovský cyklus problém, a proto je NP-úplný. Tato formulace je však ekvivalentní pouze otázce, zda H je homeomorfní k podgrafu G když H nemá žádné vrcholy stupně dva, protože neumožňuje vyhlazení dovnitř H. Uvedený problém lze ukázat jako NP-úplný malou úpravou redukce hamiltonovského cyklu: ke každému z nich přidejte jeden vrchol H a G, sousedící se všemi ostatními vrcholy. To znamená zvětšení grafu o jeden vrchol G obsahuje podgraf homeomorfní k (n + 1) -vertex graf kola, právě když G je Hamiltonian. Pro tvrdost problému podgrafu homeomorfismus viz např. LaPaugh, Andrea S .; Rivest, Ronald L. (1980), „Problém subomorfního homeomorfismu“, Journal of Computer and System Sciences, 20 (2): 133–149, doi:10.1016/0022-0000(80)90057-4, PAN 0574589.

Yellen, Jay; Gross, Jonathan L. (2005), Teorie grafů a její aplikace, Diskrétní matematika a její aplikace (2. vydání), Boca Raton: Chapman & Hall / CRC, ISBN 978-1-58488-505-4

[1] Archdeacon, Dan (1996), „Topologická teorie grafů: průzkum“, Průzkumy v teorii grafů (San Francisco, CA, 1995), Congressus Numerantium, 115, str. 5–54, PAN 1411236, Název vzniká, protože ${ displaystyle G}$ a ${ displaystyle H}$ jsou homeomorfní jako grafy právě tehdy, pokud jsou homeomorfní jako topologické prostory

[2] Trudeau, Richard J. (1993). Úvod do teorie grafů (Opravené, rozšířené publikování. Ed.). New York: Dover Pub. p. 76. ISBN 978-0-486-67870-2. Citováno 8. srpna 2012. Definice 20. Pokud jsou k některým okrajům grafu přidány nové vrcholy stupně 2 G, výsledný graf H se nazývá expanze z G.

[3] Častěji studovaným problémem v literatuře, pod názvem problému subomorfního homeomorfismu, je to, zda se jedná o dělení H je izomorfní s podgrafem G. Případ, kdy H je n-vertexový cyklus je ekvivalentní k Hamiltonovský cyklus problém, a proto je NP-úplný. Tato formulace je však ekvivalentní pouze otázce, zda H je homeomorfní k podgrafu G když H nemá žádné vrcholy stupně dva, protože neumožňuje vyhlazení dovnitř H. Uvedený problém lze ukázat jako NP-úplný malou úpravou redukce hamiltonovského cyklu: ke každému z nich přidejte jeden vrchol H a G, sousedící se všemi ostatními vrcholy. To znamená zvětšení grafu o jeden vrchol G obsahuje podgraf homeomorfní k (n + 1) -vertex graf kola, právě když G je Hamiltonian. Pro tvrdost problému podgrafu homeomorfismus viz např. LaPaugh, Andrea S .; Rivest, Ronald L. (1980), „Problém subomorfního homeomorfismu“, Journal of Computer and System Sciences, 20 (2): 133–149, doi:10.1016/0022-0000(80)90057-4, PAN 0574589.

[1]

[2]

[3]