-
Looking for HSC notes and resources? Check out our Notes & Resources page
Topology on Graphs (1 Viewer)
- Thread starter §eraphim
- Start date
This is a pretty general question but I've done classes on both graph theory and topology so I'll have some kind of answer although it definitely won't be all you can say on the topic.
Topology is the study of 'rubber sheet' geometry; you don't consider distance (the standard example is that a donut is the same ('homeomorphic to') as a coffee cup since they both only have one hole). Graph theory is the study of vertices with edges connecting them.
Possibly the first problem in both topology and graph theory was the Bridges of Konigsberg. This is topological because you don't consider the distance between islands, just whether they are connected by bridges. It is graph theoretic since you can model it as islands being vertices and bridges being edges.
So this shows that in one sense graph theory is all a special case of topology. But in practice the two are fairly separate fields: you need topology for fundamental theorems like showing the existence of inside and outside of a closed curve (the Jordan Curve Theorem) but you can just accept this as obvious and get on with answering questions about graph colourings and factorisations and so on.
Another connection is considering embeddings in surfaces. Some graphs can't be drawn without crossing over the edges if drawn in the plane but can be if drawn on the surface of a torus (donut). This is called Topological graph theory.
In my experience at least in introductory courses, graph theory is looking at interesting pictures whereas topology is mucking around a lot with definitions and sets. I think though that if you do more algebraic topology you are studying surfaces so you would find more connections.
Topology is the study of 'rubber sheet' geometry; you don't consider distance (the standard example is that a donut is the same ('homeomorphic to') as a coffee cup since they both only have one hole). Graph theory is the study of vertices with edges connecting them.
Possibly the first problem in both topology and graph theory was the Bridges of Konigsberg. This is topological because you don't consider the distance between islands, just whether they are connected by bridges. It is graph theoretic since you can model it as islands being vertices and bridges being edges.
So this shows that in one sense graph theory is all a special case of topology. But in practice the two are fairly separate fields: you need topology for fundamental theorems like showing the existence of inside and outside of a closed curve (the Jordan Curve Theorem) but you can just accept this as obvious and get on with answering questions about graph colourings and factorisations and so on.
Another connection is considering embeddings in surfaces. Some graphs can't be drawn without crossing over the edges if drawn in the plane but can be if drawn on the surface of a torus (donut). This is called Topological graph theory.
In my experience at least in introductory courses, graph theory is looking at interesting pictures whereas topology is mucking around a lot with definitions and sets. I think though that if you do more algebraic topology you are studying surfaces so you would find more connections.
We want to prove that R^n \ B(x_tilde,eps) is path connected for any n>1, x_tilde in R^n and eps>0.
A space X is said to be path-connected if for any two points x and y in X there exists a continuous function f from the unit interval [0,1] to X with f(0) = x and f(1) = y. (This function is called a path from x to y.)
The result seems pretty obvious (just draw some line between the two that doesn't go through the ball) but this is topology so we need to prove it.
Consider R^2 with x_tilde = (x,y). We have points (x1,y1) and (x2,y2) outside the epsilon ball and want to find a path between them. Construct a square of side length 2eps+1 centred at (x,y). Starting at (x1,y1) draw a straight line to the vertex of the square in the same 'quadrant' as (x1,y1). Then travel around this square clockwise to the 'quadrant' containing (x2,y2) and draw a straight line to (x2,y2). Then this path connects the two points and does not go throught the ball.
The path can be considered as a function from [0,1] -> R^2/B((x,y),eps) by constructing functions that describe the straight lines and putting them together piecewise. This is tedious.
This argument extends to arbitrary n dimensions simply with a n-dimensional hypercube instead of a square.
This is a tiresome method, actually constructing the path - I'm sure there's a more elegant, less constructive proof but I can't think of it.
A space X is said to be path-connected if for any two points x and y in X there exists a continuous function f from the unit interval [0,1] to X with f(0) = x and f(1) = y. (This function is called a path from x to y.)
The result seems pretty obvious (just draw some line between the two that doesn't go through the ball) but this is topology so we need to prove it.
Consider R^2 with x_tilde = (x,y). We have points (x1,y1) and (x2,y2) outside the epsilon ball and want to find a path between them. Construct a square of side length 2eps+1 centred at (x,y). Starting at (x1,y1) draw a straight line to the vertex of the square in the same 'quadrant' as (x1,y1). Then travel around this square clockwise to the 'quadrant' containing (x2,y2) and draw a straight line to (x2,y2). Then this path connects the two points and does not go throught the ball.
The path can be considered as a function from [0,1] -> R^2/B((x,y),eps) by constructing functions that describe the straight lines and putting them together piecewise. This is tedious.
This argument extends to arbitrary n dimensions simply with a n-dimensional hypercube instead of a square.
This is a tiresome method, actually constructing the path - I'm sure there's a more elegant, less constructive proof but I can't think of it.
