This problem is referring to the graph edge coloring, so suppose we have a graph, we have a connected
graph and we want to paint the edges in a way that no two edges that have some mutual nodes have the
same color.
So look at here.
Look at the node nine.
There are four edges connected to this node.
None of these edges should have the same color.
So we want to find out what is the minimum number of required, um, colors to, um, paint this graph.
OK, so let's write down the codes.
So here you can see that, um, for every, um, for every node, we should have some, um, limits.
So let's for every eye and see for every eye and see we have to write down this constraint.
So it is saying that summation of X I.
J.C., and the summation is over, Jay, whatever is connected to I and it should be less than one,
it means that the summation of all the edges, um, that are connected to one specific node, um, should
be less than one.
And this is valid for every I and I see.
So it no.
Two edges have the same color if they are connected to one node.
OK, and the other one is that like the previous one, like the not coloring one.
So why is bigger than C, C and C.
And also we should say that every edge should take only one color.
This is the last equation.
OK, so if I run this simulation, this is what you get.
So you can see here, that's how the graph is colored and the number of required colors are determined.
OK, so, um, let's have a look at the Python code for this problem.
Um, here you can see that, uh, first of all, we need to import the required.
Packages like matplotlib that works here is not needed to reach important.
I can remove this one and so because we already have it here, so I create a random regular graph and
with the degree of four or four and they are 30.
Nodes and I plot it and then I import the required kind of packages, construct a model, so that model
is an abstract model and is the number of nodes, as you can see, it is initialized with a number of
nodes and the number of edges and.
I and J are the set of notes L. is the connection matrix colour is the colour and also, um, X and
Y are two variables.
X is the fight over IJA and colour.
So it means that the colour of new edge which is connected between A..
I know J.
And why is the object objective function.
OK, so in order to solve that we should create a constraint saying the first constraint actually.
So if I show you that again.
So here I am.
I right on this one.
OK, so in order to um, write it down, I write this expression.
So initially the M expression is.
Equal to zero, OK, and for every DJ in the model J, if J is connected to so excited and C is added
to the EXI or if LG is one, then I will be added to the model and that expression should be less than
equal to one.
Hmm.
OK, and that constraint is defined over model, eye and color.
And this guy and instead of writing down why bigger than C X I j c and I wrote it this way, I did the
summation over and all color and I and J if they are connected to each other and this is why the reason
that I'm doing this is that if I define it, why bigger than C, X, I, J and C, this means that um
for every combination of J and C, I have to create a constraint, OK.
And that will hugely increase the size of the model.
OK, but that's kind of modeling gives you the same kind of result.
And finally, every edge should have only one color.
OK, and um, finally the objective function is why.
And the model is we can specify the gap for the in the programming which I did it here so I can run
these tabs and show you the results.
OK, so first of all, we have to create a graph.
Hmm.
OK.
And this one.
OK, so here I have to create the and L part and also and this is one way of creating the data and feeding
it into the promo.
So I create a dictionary and feel every um required parameter in a model.
OK, so I run it again.
So it is run and I uh here just the model is being fed with the input data.
OK, and the model is solved.
Um uh you can see the results here.
So the result is telling me that it's showing that IGCC and the value of it.
So see the value of it.
Is that so it means at the end the node between zero and seventeen is colored with the color number
three node between one and six is called the number two and so on and so on.
OK, um, and you can, uh, graphically see what's happening here.
OK, so here you can see that, for example, I know thirteen four colors are used and so on.
OK, and that's it for this example.
Thank you very much.