Graph theory cycle problems

162 Views Asked by At

Question background: In each of the pictures below; there are line segments connecting black dots (7 line segments in the left picture and 12 line segments in the right picture).

TwoGraphsTwoPotentialEulerCycles

Question asks to find out of "it's possible to draw a closed (cycle) continuous line that crosses each of these line segments exactly once; whilst staying inside the dashed rectangle".

My understanding of this question...

My understanding is that it's asking to treat each "region" as a vertex & then try to go through / over each existing line segment (once) until I return to the same region / vertex (if possible).

1

There are 1 best solutions below

1
On BEST ANSWER

Guide:

After you construct the graph by treating each region as a vertex and construct an edge between them for each line they share as boundary, the question is asking if there is an eulerian cycle.

An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component.