3

As we can always hear that topology is related to graph theory. But I can only read some conceptual relations between them. Technically, is it possible to write down a topology $\mathscr{T}_V$ (collection of open sets) of any given graph $V$ to consider the graph as a topological space?

Upc
  • 1,213

3 Answers3

4

The response is affirmative. One way to assign a topology to a graph is to study the graph as a CW-complex (or even a $\Delta$-complex). You can look at definitions of these spaces in Hatcher's book, freely available online (here). But, roughly speaking, both CW-complexes and $\Delta$-complex are topological spaces made of attached cells (''balls'', spaces homeomorphic to $\mathbb{B}^n$) in several dimensions. I insert a picture of a CW-complex, a ''torus'' in this case:

You can find a good explanation of the picture here.

Coming back to graphs, see the picture of a CW-complex taken from here and available in the book Topology and Groupoids:

For more information on this approach I would reccommend you have a look at the following references:

  • Lee, Introduction to Topological Manifolds, 2nd ed (Chapter 5).
  • Prasolov, Elements of Combinatorial and Differential Topology.
  • Longueville, A Course in Topological Combinatorics.

For example, in the third reference you can read about a combinatorial problem stated in 1955 in terms of set theory (Kneser conjeture), translated to graph theory in 1978 (here) and solved assigning a simplicial complex to some kinds of graphs (here the original paper).

Another approach to construct a topology from a given graph is to define a metric on the graph (for example some kind of distance between vertices), but I am afraid I don't remember right now any reference where this is elaborated.

I have found some material which you could find interesting:

D1811994
  • 2,260
3

Sure, there are many ways. The following might be particularly useful: Let the underlying set be $V\cup E$, and let $U\subseteq V\cup E$ be open iff for all $v\in U\cap V$, all edges incident with $v$ are also $\in U$.

Hagen von Eitzen
  • 374,180
0

Sure

This is the first thing that comes to my mind since I have seen this definition many times. And it is rather natural.

You can always define on a graph the path metric, which assign to every two vertexes the length of minimal path between them. If they are not on the same connected component then define their distance as infinity.

i.e Let $G=(V,E)$ be a graph (could be wighted, directed , labeled and so on) Then define $$d(v,u)=\min\{\ l(\gamma)\mid\gamma\text{ is a path between }v\text{ and }u \}$$And $l(\gamma)$ is the length function of paths. i.e it counts how many edges we are passing though (could count one edge twice) and if $\{\ l(\gamma)\mid\gamma\text{ is a path between }v\text{ and }u \}$ is empty then define $d(v,u)=\infty$

Now this metric induces a topology on $V$, But you could easily expand it to $V\cup E$ and get the same topology that was presented in the answer by Hagen von Eitzen.

And indeed you use this metric in a lot of fields.

sha
  • 1,688
  • Thank, but if I define the $d(v,u)=\infty$, then would it be against the axiom of metric space - the distance must a positive real number? – Upc Apr 19 '17 at 20:42
  • @XavierYang In some formalism you allow infinite value for the metric. It does satisfy the 3 important axioms. If your graph is connected (in the sense that there is a finite path between every two vertexes) then it does not take the value infinity. Any way, with infinity or without, It still induces a topology! and it is the same topology as in the answer of Hagen von Eitzen. You can see this definition on most basic books on graph theory or in my favourite form the Cayley Graph of a group – sha Apr 19 '17 at 20:54
  • Won't this induce the discrete topology for most graphs, or am I missing something? – Charles Hudgins Nov 16 '22 at 03:09
  • No, you haven't. It seems I have missed mentioning that edges are replaced with an interval. But indeed, it is not equivalent to the topology in the answer above. 5 years later I see it :) – sha Nov 17 '22 at 09:34