• Source: Graph (topology)

In topology, a branch of mathematics, a graph is a topological space which arises from a usual graph



G
=
(
E
,
V
)


{\displaystyle G=(E,V)}

by replacing vertices by points and each edge



e
=
x
y
∈
E


{\displaystyle e=xy\in E}

by a copy of the unit interval



I
=
[
0
,
1
]


{\displaystyle I=[0,1]}

, where



0


{\displaystyle 0}

is identified with the point associated to



x


{\displaystyle x}

and



1


{\displaystyle 1}

with the point associated to



y


{\displaystyle y}

. That is, as topological spaces, graphs are exactly the simplicial 1-complexes and also exactly the one-dimensional CW complexes.
Thus, in particular, it bears the quotient topology of the set





X

0


⊔

⨆

e
∈
E



I

e




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


under the quotient map used for gluing. Here




X

0




{\displaystyle X_{0}}

is the 0-skeleton (consisting of one point for each vertex



x
∈
V


{\displaystyle x\in V}

),




I

e




{\displaystyle I_{e}}

are the closed intervals glued to it, one for each edge



e
∈
E


{\displaystyle e\in E}

, and



⊔


{\displaystyle \sqcup }

is the disjoint union.
The topology on this space is called the graph topology.




Subgraphs and trees


A subgraph of a graph



X


{\displaystyle X}

is a subspace



Y
⊆
X


{\displaystyle Y\subseteq X}

which is also a graph and whose nodes are all contained in the 0-skeleton of



X


{\displaystyle X}

.



Y


{\displaystyle Y}

is a subgraph if and only if it consists of vertices and edges from



X


{\displaystyle X}

and is closed.
A subgraph



T
⊆
X


{\displaystyle T\subseteq X}

is called a tree if it is contractible as a topological space. This can be shown equivalent to the usual definition of a tree in graph theory, namely a connected graph without cycles.




Properties


The associated topological space of a graph is connected (with respect to the graph topology) if and only if the original graph is connected.
Every connected graph



X


{\displaystyle X}

contains at least one maximal tree



T
⊆
X


{\displaystyle T\subseteq X}

, that is, a tree that is maximal with respect to the order induced by set inclusion on the subgraphs of



X


{\displaystyle X}

which are trees.
If



X


{\displaystyle X}

is a graph and



T
⊆
X


{\displaystyle T\subseteq X}

a maximal tree, then the fundamental group




π

1


(
X
)


{\displaystyle \pi _{1}(X)}

equals the free group generated by elements



(

f

α



)

α
∈
A




{\displaystyle (f_{\alpha })_{\alpha \in A}}

, where the



{

f

α


}


{\displaystyle \{f_{\alpha }\}}

correspond bijectively to the edges of



X
∖
T


{\displaystyle X\setminus T}

; in fact,



X


{\displaystyle X}

is homotopy equivalent to a wedge sum of circles.
Forming the topological space associated to a graph as above amounts to a functor from the category of graphs to the category of topological spaces.
Every covering space projecting to a graph is also a graph.




See also


Graph homology
Topological graph theory
Nielsen–Schreier theorem, whose standard proof makes use of this concept.




References

Kata Kunci Pencarian:

• Teori graf
• Tujuh Jembatan Königsberg
• Contoh penyangkal
• Grup dasar
• Daftar masalah matematika yang belum terpecahkan
• Kartogram
• Graph (topology)
• Circuit topology (electrical)
• Graph
• Closed graph property
• Topological graph theory
• Network topology
• Graph neural network
• Graph manifold
• Knowledge graph
• Graph theory