Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Geometric Realizations sorry, not convinced.

  1. Aug 13, 2006 #1
    I've read (and I've been told in lectures) that each graph (let's just say a combinatorial graph) corresponds to a topological space called the geometric realization - in this space the vertices are distinct points and the edges are subspaces homeomorphic to [0,1]. My question is this: Is this provable? I mean, lots of book say this but I'm not entirely convinced. This is probably easy to prove but I have not seen it anywhere. If someone could show me, or instruct me, or provide a link, or something, I would be very happy!
  2. jcsd
  3. Aug 13, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It's rather straight-forward. (at least if you know about quotient spaces)

    (1) Choose an orientation for each edge.
    (2) Take a copy of [0, 1] for every edge, and a copy of * (the one-point space) for every vertex.
    (3) Glue vertices to edges where appropriate.
  4. Aug 13, 2006 #3


    User Avatar
    Science Advisor
    Homework Helper

    You can also stick your graph in R^n. If you have n vertices, set them at the points (1,0,...0),(0,1,0,...0),...(0,0,...,0,1) and connect with straight lines the vertices that have edges between them (there will be no intersections). Take the topology inhereted from R^n, the edges will be homeomorphic to [0,1] like you wanted.
  5. Aug 14, 2006 #4
    Thankyou both for replying. It was unexpected as I could not find many references on the internet about this sort of thing. Perhaps you guys might know of some books or websites about Graphs and their actions on Trees.

    ...and this works for every possible graph I can think of? Why must each edge have an orientation? Im trying to justify each of these three steps. Is it true that every graph admits an orientation? What if I don't orient the edges, will this still work?

    At the risk of sounding rude; how do you "stick" a graph in R^n? I guess I need a little more explanation, like how do you know that the edges will be homeomorphic to [0,1]? Is it simply because of the inhereted topology on R^n?
  6. Aug 14, 2006 #5


    User Avatar
    Science Advisor
    Homework Helper

    The only graph theory book I've ever used was West, "Introduction to Graph Theory". It seemed good, but I have no comparison.

    The orientation was just so you could call one end "0" and the other end "1". You choice of which end of an edge to call 0 is arbitrary.

    Just order the vertices any way you like, identify them with the points I gave. The edges will be finite straight line segments, like from (1,0,0,...,0) to (0,1,0,...,0), it's obvious this is homeomorphic to [0,1], no? You can find an explicit homeomorphism without trouble if you like.
  7. Aug 14, 2006 #6
    I need to ask a quick question which is a little off topic:

    I had a graph [itex]\Gamma[/itex] and defined a function [itex]d\,:\,V(\Gamma) \times V(\Gamma) \rightarrow \mathbb{N}[/itex] as being the number [itex]d(P,Q)[/itex] - the minimal path length in the graph with origin P and terminus Q. Then I want to show that this is a metric. So I would have to show

    1. [tex]d(P,Q) \geq 0[/tex]

    2. [tex]d(P,Q) = 0 \Leftrightarrow P=Q[/tex]

    3. [tex]d(P,Q) = d(Q,P)[/tex]

    4. [tex]d(P,Q) \leq d(P,R) + d(R,Q)[/tex].

    For (1.) I said since path length is never negative, the minimum path length is never negative. Is that enough?

    For (2.) I said if P=Q then there is no path between them hence the path length is 0, and conversely if d(P,Q) = 0 then there is no path and hence the vertices are the same, i.e. P=Q.

    For (3.) I said suppose [itex]d(P,Q) \neq d(Q,P)[/itex] then there exists two paths (one from P to Q and one from Q to P) with different path lengths. If d(P,Q) is minimal then there cannot exist a shorter path. Hence [itex]d(P,Q) \neq d(Q,P)[/itex] is contradictory. Therefore d(P,Q) = d(Q,P). Does this sound ok, honestly I dont like it.

    For (4.)...well...I tried treating it like any other Triangle inequality proof but I got stuck. Consider the path from P to Q. Then d(P,Q) is the minimal path length. The way I understand it, there could be many, many different paths between P and Q, but d(P,Q) picks the shortest one and returns a natural number. Now, what if the vertex R is somewhere along this shortest path? Then surely [itex]d(P,Q) = d(P,R) + d(Q,R)[/itex], yes? Well, surely that is ok?
  8. Aug 15, 2006 #7
    What is the one-point space?
  9. Aug 16, 2006 #8
    I have concluded that not every graph can be recovered from its geometric realization. Before I go on, does anyone else agree with me?
  10. Aug 16, 2006 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The topological space with only a single point in it.

    I agree. The realizations of

    . __ . __ .


    . __ .

    would be homeomorphic.

    If we restrict ourselves to graphs that don't have vertices of degree 2, however, we can always recover the graph from its realization.
  11. Aug 16, 2006 #10
    Exactly! So, we can always construct a geometric realization from a graph, but it is not always possible to recover a graph simply from its realization?
  12. Aug 17, 2006 #11


    User Avatar
    Science Advisor
    Homework Helper

    What about a disconnected graph? You might have two points for which d(P,Q) is undefined.
    It's not that there's no path between them, it's that the smallest path consists of no edges.
    In general, 3 only holds if the graph is undirected.

    If 4 were false, then the shortest distance from P to Q would be greater than the shortest distance from P to R plus the shortest dist. from R to Q. But then you could just create a path from P to Q via R which would be shorter than the supposedly shortest path from P to Q, contradiction.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook