Graf (topologie) - Graph (topology) - Wikipedia

v topologie, předmět v matematika, a graf je topologický prostor který vychází z obvyklého graf ${ displaystyle G = (E, V)}$ nahrazením vrcholů body a každou hranou ${ displaystyle e = xy v E}$ kopií jednotkový interval ${ displaystyle I = [0,1]}$, kde ${ displaystyle 0}$ je identifikován s bodem spojeným s ${ displaystyle x}$ a ${ displaystyle 1}$ s bodem spojeným s ${ displaystyle y}$. To znamená, že jako topologické prostory jsou grafy přesně ty jednoduché 1-komplexy a také přesně jednorozměrný CW komplexy.^[1]

Nese tedy zejména: kvocient topologie z soubor

${ displaystyle X_ {0} sqcup bigsqcup _ {e in E} I_ {e}}$

pod mapou kvocientu použitou pro lepení. Tady ${ displaystyle X_ {0}}$ je 0-kostra (skládající se z jednoho bodu pro každý vrchol ${ displaystyle x ve V}$), ${ displaystyle I_ {e}}$ jsou intervaly ("uzavřené jednorozměrné jednotkové koule") nalepené na něm, jeden pro každý okraj ${ displaystyle e v E}$, a ${ displaystyle sqcup}$ je disjunktní unie.^[1]

The topologie v tomto prostoru se nazývá topologie grafů.^[2]

Podgrafy a stromy

Podgraf grafu ${ displaystyle X}$ je podprostor ${ displaystyle Y subseteq X}$ což je také graf a jehož uzly jsou všechny obsaženy v 0-kostře ${ displaystyle X}$. ${ displaystyle Y}$ je podgraf právě tehdy, pokud se skládá z vrcholů a hran z ${ displaystyle X}$ a je zavřený.^[1]

Podgraf ${ displaystyle T subseteq X}$ se nazývá a strom pokud je to kontraktovatelné jako topologický prostor.^[1]

Vlastnosti

• Každý připojený graf ${ displaystyle X}$ obsahuje alespoň jeden maximální strom ${ displaystyle T subseteq X}$, tj. Strom, který je maximální vzhledem k řádu vyvolanému zahrnutím množiny na podgrafy ${ displaystyle X}$ což jsou stromy.^[1]
• Li ${ displaystyle X}$ je graf a ${ displaystyle T subseteq X}$ maximální strom, pak základní skupina ${ displaystyle pi _ {1} (X)}$ rovná se volná skupina generované prvky ${ displaystyle (f _ { alpha}) _ { alpha v A}}$, Kde ${ displaystyle {f _ { alpha} }}$ korespondovat bijektivně k okrajům ${ displaystyle X setminus T}$; ve skutečnosti, ${ displaystyle X}$ je ekvivalent homotopy do a klínový součet z kruhy.^[1]
• Formování topologického prostoru přidruženého ke grafu výše se rovná a funktor z kategorie grafů do kategorie topologických prostorů.^[2]
• Přidružený topologický prostor grafu je spojen (s ohledem na topologii grafu) právě tehdy, pokud je připojen původní graf.^[2]
• Každý pokrývající prostor promítání do grafu je také graf.^[1]

Aplikace

Pomocí výše uvedených vlastností grafů lze dokázat Nielsen – Schreierova věta.^[1]

Viz také

• Homologie grafů
• Topologická teorie grafů

Reference