Question

Draw a graph that models the connecting relationships in the floorplan below. The vertices represent the rooms and the edges represent doorways connecting the rooms. Vertex D represents the outdoors.Is it possible to find a path through the house that uses each doorway once? If so, enter the sequence of rooms(vertices) visited, for example ABCDA. If it is not possible, enter DNE.

Answer 1

A path that goes through the house

There are edges completed, another are incomplete

Vertices are points where lines intersect

Edges are doorways

A way to pass only once for each doorway

Only once passing, means there is no go back. Always goes in one direction.

In every vertice it have 2 options, go left or right

There are 4 vertices

Its not possible , DNE , because in every direction it cannot go through all 4 vertices , and also pass through all the edges.