7
$\begingroup$

I would like to know of a method in which if provided say 10 routes with details regarding which route intersects with which another route, we can use the least number of colours to colour the routes, without the intersecting routes having the same colour.

For example, say Route 1 intersects with Route 2,3,6,7,9.

Route 2 intersects with Route 1,3,5,7 and so on...

One can use the same colour again.

How should one go about assigning colours to each route and also minimize the number of colours used?

Improve this question
$\endgroup$
1
  • $\begingroup$ Note that you may end up with an arbitrary number of mutually intersecting routes: i.imgur.com/sz7NZRt.png $\endgroup$
    – BoppreH
    May 15, 2020 at 16:15

1 Answer 1

Reset to default
14
$\begingroup$

Recognize that each route can be viewed as being a node on a graph. Edges connect nodes if the routes the nodes represent intersect. This is the canonical graph coloring problem for which there are a number of exact and approximate algorithms. Specifically, you're trying to find a constructive algorithm for determining the chromatic number.

For 10 routes and low recalculation volume, I'd suggest building a simple brute-force algorithm as the quickest way of getting an answer.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.