This example, we want to talk about the graph node coloring problem, so consider this graph, it has
a number of nodes that are connected to each other.
And from the graph, we just know how the nodes are connected to each other, that this is the input
data of the problem.
OK, so the question is, if we want to color the nodes in a way that no two adjacent nodes are painted
with the same color, how many colors do we need?
What is the minimum number of colors that we need?
So suppose if we have nodes in or graph, then if we have any colors, we can easily solve this problem.
OK, but there is a much smarter way to do this.
For example, if you look at this graph, you can see by only two colors and the nodes are painted in
a way that no two adjacent nodes are colored with the same color.
So if you look at here, these two have different colors, but this yellow and this yellow one have
the same color because they are not directly connected to each other.
That's fine.
So how can we formulated as a as an optimization problem?
So first of all, we need the input data of the graph.
So Elijah is one if I is connected to J and X, I see is telling us node eye is color with the color.
See, so we have a set C it has a range of colors and I is the set of nodes.
So we want to find out an optimal mapping between nodes and the colors.
So we want to know which node should take which color.
OK, so I see is a binary variable.
X is the final variable.
Iyengar aliased with each other so they are from the same sets nodes summation of these two variables
multiplied by Elijah, less than one.
So if Elijah is zero, it means that.
To constraint, uh, can be easily satisfied because there is less than one automatically satisfied,
it's inactive, and if energy is one, then Xixi plus SJC less than one.
So that constraint is defined over the sets are and see for every injury and see if Alija is one, then
the summation of these survival should be one.
It means that if two nodes are connected to each other, they cannot get the same color.
OK, and why is the objective function should be identical to see Xixi for every agency?
And the last constraint is telling us that every node should take only one color so every node and every
color can be assigned to only one node.
OK, so let's have a look at the Python code for this purpose.
So the Python code is here.
I import, uh, required, um, packages.
So first of all, uh, matplotlib networks for drawing the graph kind of, uh, plotts.
And this is a built-In kind of facility in the networks package to plot the graphs that they're given
sizes and also the position of these and those are determined.
And then we'll import pion moments, possibly known by random and also Pande, OK?
And then we construct the model.
We assume that the model is an abstract one and is the number of nodes ie is the set of nodes is the
same color as a set of colors.
The maximum number of colors will be this number of nodes and L is a parameter showing that if I is
connected to G to J, actually an X and Y are some variables.
So X is a binary variable, but why is there no negative results.
So, uh, we can easily solve that.
And let's write down the, um, equation that we need.
So you can see here that L multiplied by X I, C plus X Jaycee less than one.
That constraint is the word I j and color and that's rules should be followed.
And then the objective function should be bigger than a C multiplied by model and X.
I see.
And that's constraint is defined over I and C you can see here.
And finally every node should take only one color that's here and the objective function is model that
way and the sense is minimization.
So we want to find out the minimum number of color required for, uh, paint in that graph.
So since the model is linear, I choose the GOP.
Okay.
And solver and here we have already created the graph can see.
And also here we we have access to the number of nodes in that graph.
So model that N is initialized somehow and then the instance will be created here.
OK, so let's run the code so far to see what's going on.
So I run the whole tabs and I will explain the um results.
So, um, let's begin from the first.
So the first of the required pages are important, the second one as well.
And the model is created here.
And it is um, the instance will be constructed means that the L and other constraints are fed into
the model.
But keep in mind that I have not specified the L yet.
So the connectivity matrix is not specified yet.
So I have initialize that is equal to zero.
So all of them are not connected to each other.
But the model is right and we have to and update the L and feed the right connection matrix to the um
instance.
So for this purpose and what we do is we can easily find out which nodes are connected to which, so
forth, and we create a for loop H in and G dot edges.
If these two are connected to each other then um instance that Elijah is equal to one.
OK, so from nodes and two nodes are uh found using these commands.
OK, and then uh what we should do next is and let me double check it here for instance is updated at
L l in the instance is updated and we have already defined as immutable parameter seed here.
It's a mutual one.
So it means that you can update their quantities and then and we can ask the more to solve it for us.
So it is trying to solve the problem.
Since it has some binary variables inside the model, it may take time to solve that.
And, uh, so the model is solved.
OK, you can see that, El.
And it's printed here, for example, it's not really necessary to print all these, but for checking
purpose, you can do it.
So it means that one is connected to the volumes one and so on and so on.
OK.
And, um, finally, you can see here that, um, the graph is colored, OK, and each X I see has taken
the value.
So let me show you what's happening here.
So here we have we can see easily.
That's the what are the values of X?
I see, for example, node one, color one is one.
It means that no one is.
Colored with color, No one, No.
Two is colored with No.
Two or three color, the number one, not four, is currently number two and so on and so on.
OK, so and already we had a specified and each number means which color.
OK, so, um, we should have a list for the columns and you can choose which color is selected.
OK.
And that's, it's.