Well, I'm really happy to see you because if you made it that far, it basically
means that you have successfully, you know, done the knapsack, you know,
assignments and you are still willing to continue in the class.
So, this is about coloring, and this is when things get more difficult.
This is a very fantastic, amazingly beautiful assignment.
You'll see that, okay. Conceptually, it's amazingly simple,
right? So, we saw in the lecture, you have
notes, you have edges between the notes. You want to color these things with as
few colors as possible, okay. Such that two adjacent vertices are given
a different color, okay. So, this is a beautiful graph.
We've actually four nodes. It's a tree, so we could so optimal
solutions very quickly, okay. And this is a particular solution.
We've one node which is blue, another node red.
Two green nodes, okay. And so we are using three colors, okay.
So, this is what we will have to solve, okay.
So this is the formalization of the problem, okay.
You can look at it, okay. But, essentially the important things
here is that we have a certain number of node and we have a certain number of
edges, you know E. And that's what's going to drive the
input of this assignment, okay. And we'll have a long, long, long list of
edges because some of the problems we'll solve here are going to be pretty, pretty
interesting in some societies, okay. So, we have a decision variable for
everyone of the nodes and that's going to be the color of that node.
That's going to be the output of this assignment, okay.
So the assignment itself is basically minimizing the largest color that you are
using. We are using numbers here, okay.
So, you know, mini-, max, minimizing the maximum color that we are using, okay.
And then we have only a single constraint which is reasonably easy.
You know, two different, two adjacent vertices have to be given a different
color, okay. So, when you look at this, you have to
know what the input and the output are going to be, okay.
So, the input here is going to have basically two ints, okay.
The beginning that will tell you the size of the number of vertices, and then the
number of edges, that's the two things that you will see there, okay.
Number of vertices, number of number of edges.
And then what you will have is a long list of edges, okay.
Now an edge is basically defined by what? By essentially two vertices, okay.
So, every line here that you see, the input is going to be basically telling
you that there is an edge between, you know, the first vertex and the second
vertex, okay. And, so that's basically going to be the
input. So, the input is basically how many
nodes, you know, how many, how many vertex, how many edges between these
vertices. And then a long list of what these edges
are. And that's just basically two, two
vertices, okay. Now the output is going to be as usual,
okay. So, what is the optimal solutions that
you, or the best solutions that you have found?
And whether it's optimal or not, okay. And then you will have also the colors of
all these vertices, okay. So, for everyone of the vertex, you know,
you will basically specify its color in the optimal well or the best form
solution, okay. So, that's the basic idea, okay.
This is a particular example, okay. So, you see that we have basically three
vertices we have four vertices and three edges, okay.
Those what you see there. And these are the various edges.
We have an edge between node zero and node one, vertex zero, vertex one.
We have another edge between vertex one and vertex two, and so on and so forth,
that's what you see, okay. And then you see a particular of
solutions there, which has basically three colors.
And it's not proven optimal, and you see the various colors of these things 0122,
okay. So, that's basically input.
Very simple, long list essentially of edges and then the output, which is
basically the color of every one of these vertices, okay.
So, input output is very simple in this problem, okay.
It's conceptually a very simple problem. But graph coloring is this beautiful
property that is very very difficult to solve, okay.
yeah, and this is an illustration of actually the two solution, the solutions
that we just produce here. so let me give you some assignment tips
here, okay. So, one other thing which is important
whatever the, whatever the approach that you're actually using.
Is that, you know, the degree of a node is important.
The higher the degree of a node, you know, the more difficult it is, the more
constrained that node is in a sense. You know, what the color that node can
take is basically limited by all it's neighbors, okay.
So, think about how that information can be exploited, okay.
So, other things that you have to think about is that there are a lot and lot of
symmetries in these problems, okay. So, we had a lot of lectures on
symmetries inside the constrained programming lecture.
Think about them, and think how they can be exploited inside this particular
assignment, okay. So, what you see there is the solution
there, okay. So, this is a solution, this is a
solution which is completely symmetric, okay.
You know, think about why these two things are symmetric.
There is a very simple rule and, you know, this is essentially some of the
techniques that we have seen in constrain programming there, for telling you what
kind of symmetry this is. But, this can be exploited and if want or
find actually, you know, very good solution and improve optimality, you will
have to use things like this, okay. And then, there are other things that you
want to do if, you know, if you want to improve optimality or if you want to
find, you know, to get a, a sense of what your solution is.
Try to find if they are easy lower bound that you can compute.
There is one very simple conceptual lower bound that you can take, and that will
tell you the best you can ever achieve, okay.
So, you know, there are lot of structure here, although the problem is very simp-,
you know it's very simple conceptually but there are lot of things that you can
exploit and that's why I love this problem, okay.
Now this is a beautiful graph here, you know, this is 250 vertices, it's about
3000 edges, okay. Which basically means that the density
here the den, you know, the density of the edges is 0.1% compared to the full
graph, okay. It's a reasonably easy answer.
I mean it's medium difficulty. It's still hard to prove optimality, but
this is not some of the most difficult, this is not one of the most difficult
instance. Now you can imagine a bushy, you know, it
becomes when you have 50% density, okay. So, that's much more complex and much
more difficult to solve, okay. So, so, this is essentially, you know,
what I wanted to tell you about the graph coloring assignment.
You can be really, really creative on this assignment.
It's a fantastic assignment, okay. And I look forward to see you compete in
finding a high-quality solution and proving optimality on some of these
instances. Okay, have fun, it's going to be really
interesting.