Four color theorem: about edges selection


For the decomposition of a graph representing a map, I’m trying to use different algorithms to select the edge to remove.

The question is:

  • When you have multiple valid choices, which is the best edge to select … if any?

Some basic rules are:

  • Avoid new F5 to be created
  • Get rid of F5 whenever is possible, selecting the edge of a face with 2, 3 or 4 edges
  • Consider to remove an edge from an F5 face only if no faces with 2, 3, 4 edges exist

Here are all possibilities. Last 2 groups (removing edges from F5 and F6) don’t have to be taken into account. I just wanted to see how it continued after the cases with faces made of 2, 3, 4 and 5 edges:

edges-selection-possibilities

Advertisements
This entry was posted in math and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s