5 ms·

Neat Introductory Graph Theory Solutions

40 points by Locke1689 16y ago

dnautics 16y ago
Challenge problem: Prove or disprove (with counterexample) that it is still impossible for the fairy to end in the center if she starts in the middle unit on the southern side of the first floor.
- jules 16y ago
  Do you mean ground floor? If you mean the middle floor then the answer is the same as the answer in the article?
anorwell 16y ago
The chessboard-domino problem isn't related to hamiltonian paths in bipartite graphs. For a minimal counter-example, the path of length 2 is bipartite and has a hamiltonian path, but has an odd number of vertices so there is clearly no way to cover it with dominoes. You can also find counter-examples in the other direction (bipartite, domino-coverable, not hamiltonian), but they take a bit more effort to describe. The generalized chessboard problem is to find a perfect matching (http://en.wikipedia.org/wiki/Perfect_matching http://en.wikipedia.org/wiki/Perfect_matching) in a graph: that is, a set of edges that cover each vertex, but don't touch any other edge in the set. This problem is a lot easier than finding a hamiltonian path, which is NP-complete.
- Locke1689 16y ago
  Well, they're not related in that they are not the same problem, but they are related in that you can solve both using the properties of bipartite graphs. I think I was correct in the post—I never actually stated that domino-covering is equivalent to the Hamiltonian path problem. The entire point of the post was really that we can use graph theory to generalize certain properties and solve a number of different unrelated problems, not to equate all problems. I did mistakenly imply that the domino covering was a path (which you're right, it's not) at one point. I have edited the post for clarity.
zackattack 16y ago
i can't for the life of me figure out why the 3x3 apartment building was divided into two bipartite graphs. can someone please explain? i thought each room is connected to any adjacent building.. since "Passing only through walls, ceilings, and ﬂoors" is an option??
- Locke1689 16y ago
  Sorry if I gave that impression. The apartment building is a single graph which I labeled G. The three separate diagrams symbolize each floor. As I said: I have built the graph for the apartment below. Each vertex in the graph represents a room, while each edge represents a path the fairy can travel. The graph is split into three separate floors for easy visualization, but simply imagine that each vertex is connected to the nodes above and below them.
  - zackattack 16y ago
    right, so why are some of the vertices black and why are some of them red?
    - Locke1689 16y ago
      It's a single bipartite graph -- the requirement for a bipartite graph is that every vertex can be separated into two non-adjacent disjoint sets. Since the names of the sets are arbitrary I just named them "red" and "black." The color of the vertex represents the membership of its set.
      - zackattack 16y ago
        Right... so why are the sets disjoint? Why are some vertices in the red set and others in the black set?
        zackattack 16y ago
        like is the bipartite graph a natural translation or is it something arbitrary you invented? because if it's arbitrary it's confusing because in the written description you mentioned you could from one edge to another so it doesn't seem like it would be a bipartite graph but simply a regular connected graph?

40 points by Locke1689 16y ago

Challenge problem: Prove or disprove (with counterexample) that it is still impossible for the fairy to end in the center if she starts in the middle unit on the southern side of the first floor.

jules 16y ago
Do you mean ground floor? If you mean the middle floor then the answer is the same as the answer in the article?

anorwell 16y ago

The chessboard-domino problem isn't related to hamiltonian paths in bipartite graphs. For a minimal counter-example, the path of length 2 is bipartite and has a hamiltonian path, but has an odd number of vertices so there is clearly no way to cover it with dominoes. You can also find counter-examples in the other direction (bipartite, domino-coverable, not hamiltonian), but they take a bit more effort to describe. The generalized chessboard problem is to find a perfect matching (http://en.wikipedia.org/wiki/Perfect_matching http://en.wikipedia.org/wiki/Perfect_matching) in a graph: that is, a set of edges that cover each vertex, but don't touch any other edge in the set. This problem is a lot easier than finding a hamiltonian path, which is NP-complete.

Locke1689 16y ago
Well, they're not related in that they are not the same problem, but they are related in that you can solve both using the properties of bipartite graphs. I think I was correct in the post—I never actually stated that domino-covering is equivalent to the Hamiltonian path problem. The entire point of the post was really that we can use graph theory to generalize certain properties and solve a number of different unrelated problems, not to equate all problems. I did mistakenly imply that the domino covering was a path (which you're right, it's not) at one point. I have edited the post for clarity.

zackattack 16y ago

i can't for the life of me figure out why the 3x3 apartment building was divided into two bipartite graphs. can someone please explain? i thought each room is connected to any adjacent building.. since "Passing only through walls, ceilings, and ﬂoors" is an option??

Locke1689 16y ago
Sorry if I gave that impression. The apartment building is a single graph which I labeled G. The three separate diagrams symbolize each floor. As I said: I have built the graph for the apartment below. Each vertex in the graph represents a room, while each edge represents a path the fairy can travel. The graph is split into three separate floors for easy visualization, but simply imagine that each vertex is connected to the nodes above and below them.
- zackattack 16y ago
  right, so why are some of the vertices black and why are some of them red?
  - Locke1689 16y ago
    It's a single bipartite graph -- the requirement for a bipartite graph is that every vertex can be separated into two non-adjacent disjoint sets. Since the names of the sets are arbitrary I just named them "red" and "black." The color of the vertex represents the membership of its set.
    - zackattack 16y ago
      Right... so why are the sets disjoint? Why are some vertices in the red set and others in the black set?
      - zackattack 16y ago
        like is the bipartite graph a natural translation or is it something arbitrary you invented? because if it's arbitrary it's confusing because in the written description you mentioned you could from one edge to another so it doesn't seem like it would be a bipartite graph but simply a regular connected graph?