0:00

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.