76.6k views
5 votes
I'm so confused on this one

I'm so confused on this one-example-1
User Gibatronic
by
8.2k points

1 Answer

6 votes

Answer:

  • Graph: see attached
  • Path: FABFCADFEBDE

Explanation:

Given a floor plan with rooms labeled A to F, you want a graph with edges representing the connections between rooms, and a path through every door once.

Graph

The graph will have a node assigned to each room. Node F represents the outside area. An edge will connect nodes that have a doorway between the corresponding rooms.

A graph is shown in the attachment.

Path

A path through all doors once will exist if there are 0 or 1 nodes of odd degree. (An odd number of edges connect to the node.) Node E is of degree 3, and node F is of degree 5. All the others have an even number of edges connected, so the desired path can exist. It must begin on one of nodes E or F and end on the other one.

The path can be found by starting at node F (or E) and following any edge that hasn't been followed before. The end node must be E (or F). You don't really need to be too concerned about getting stuck somewhere.

One possible path through all the doors is ...

FABFCADFEBDE

<95141404393>

I'm so confused on this one-example-1
User Dag Baardsen
by
8.0k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories