1
00:00:00,380 --> 00:00:04,156
Well, I'm really happy to see you because 
if you made it that far, it basically 

2
00:00:04,156 --> 00:00:07,932
means that you have successfully, you 
know, done the knapsack, you know, 

3
00:00:07,932 --> 00:00:13,440
assignments and you are still willing to 
continue in the class. 

4
00:00:13,440 --> 00:00:17,920
So, this is about coloring, and this is 
when things get more difficult. 

5
00:00:17,920 --> 00:00:21,830
This is a very fantastic, amazingly 
beautiful assignment. 

6
00:00:21,830 --> 00:00:24,406
You'll see that, okay. 
Conceptually, it's amazingly simple, 

7
00:00:24,406 --> 00:00:26,076
right? 
So, we saw in the lecture, you have 

8
00:00:26,076 --> 00:00:29,784
notes, you have edges between the notes. 
You want to color these things with as 

9
00:00:29,784 --> 00:00:33,976
few colors as possible, okay. 
Such that two adjacent vertices are given 

10
00:00:33,976 --> 00:00:37,980
a different color, okay. 
So, this is a beautiful graph. 

11
00:00:37,980 --> 00:00:40,762
We've actually four nodes. 
It's a tree, so we could so optimal 

12
00:00:40,762 --> 00:00:44,600
solutions very quickly, okay. 
And this is a particular solution. 

13
00:00:44,600 --> 00:00:47,090
We've one node which is blue, another 
node red. 

14
00:00:47,090 --> 00:00:50,626
Two green nodes, okay. 
And so we are using three colors, okay. 

15
00:00:50,626 --> 00:00:52,960
So, this is what we will have to solve, 
okay. 

16
00:00:52,960 --> 00:00:55,404
So this is the formalization of the 
problem, okay. 

17
00:00:55,404 --> 00:00:58,420
You can look at it, okay. 
But, essentially the important things 

18
00:00:58,420 --> 00:01:01,592
here is that we have a certain number of 
node and we have a certain number of 

19
00:01:01,592 --> 00:01:05,168
edges, you know E. 
And that's what's going to drive the 

20
00:01:05,168 --> 00:01:08,765
input of this assignment, okay. 
And we'll have a long, long, long list of 

21
00:01:08,765 --> 00:01:12,233
edges because some of the problems we'll 
solve here are going to be pretty, pretty 

22
00:01:12,233 --> 00:01:16,809
interesting in some societies, okay. 
So, we have a decision variable for 

23
00:01:16,809 --> 00:01:20,500
everyone of the nodes and that's going to 
be the color of that node. 

24
00:01:20,500 --> 00:01:22,670
That's going to be the output of this 
assignment, okay. 

25
00:01:22,670 --> 00:01:25,886
So the assignment itself is basically 
minimizing the largest color that you are 

26
00:01:25,886 --> 00:01:28,420
using. 
We are using numbers here, okay. 

27
00:01:28,420 --> 00:01:33,900
So, you know, mini-, max, minimizing the 
maximum color that we are using, okay. 

28
00:01:33,900 --> 00:01:36,602
And then we have only a single constraint 
which is reasonably easy. 

29
00:01:36,602 --> 00:01:40,193
You know, two different, two adjacent 
vertices have to be given a different 

30
00:01:40,193 --> 00:01:43,080
color, okay. 
So, when you look at this, you have to 

31
00:01:43,080 --> 00:01:46,470
know what the input and the output are 
going to be, okay. 

32
00:01:46,470 --> 00:01:49,535
So, the input here is going to have 
basically two ints, okay. 

33
00:01:49,535 --> 00:01:53,423
The beginning that will tell you the size 
of the number of vertices, and then the 

34
00:01:53,423 --> 00:01:58,150
number of edges, that's the two things 
that you will see there, okay. 

35
00:01:58,150 --> 00:02:01,140
Number of vertices, number of number of 
edges. 

36
00:02:01,140 --> 00:02:05,770
And then what you will have is a long 
list of edges, okay. 

37
00:02:05,770 --> 00:02:09,910
Now an edge is basically defined by what? 
By essentially two vertices, okay. 

38
00:02:09,910 --> 00:02:13,150
So, every line here that you see, the 
input is going to be basically telling 

39
00:02:13,150 --> 00:02:16,498
you that there is an edge between, you 
know, the first vertex and the second 

40
00:02:16,498 --> 00:02:20,122
vertex, okay. 
And, so that's basically going to be the 

41
00:02:20,122 --> 00:02:22,062
input. 
So, the input is basically how many 

42
00:02:22,062 --> 00:02:24,942
nodes, you know, how many, how many 
vertex, how many edges between these 

43
00:02:24,942 --> 00:02:28,136
vertices. 
And then a long list of what these edges 

44
00:02:28,136 --> 00:02:30,715
are. 
And that's just basically two, two 

45
00:02:30,715 --> 00:02:33,569
vertices, okay. 
Now the output is going to be as usual, 

46
00:02:33,569 --> 00:02:35,338
okay. 
So, what is the optimal solutions that 

47
00:02:35,338 --> 00:02:37,245
you, or the best solutions that you have 
found? 

48
00:02:37,245 --> 00:02:41,484
And whether it's optimal or not, okay. 
And then you will have also the colors of 

49
00:02:41,484 --> 00:02:45,333
all these vertices, okay. 
So, for everyone of the vertex, you know, 

50
00:02:45,333 --> 00:02:48,861
you will basically specify its color in 
the optimal well or the best form 

51
00:02:48,861 --> 00:02:53,156
solution, okay. 
So, that's the basic idea, okay. 

52
00:02:53,156 --> 00:02:58,262
This is a particular example, okay. 
So, you see that we have basically three 

53
00:02:58,262 --> 00:03:02,700
vertices we have four vertices and three 
edges, okay. 

54
00:03:02,700 --> 00:03:06,150
Those what you see there. 
And these are the various edges. 

55
00:03:06,150 --> 00:03:11,420
We have an edge between node zero and 
node one, vertex zero, vertex one. 

56
00:03:11,420 --> 00:03:14,940
We have another edge between vertex one 
and vertex two, and so on and so forth, 

57
00:03:14,940 --> 00:03:18,605
that's what you see, okay. 
And then you see a particular of 

58
00:03:18,605 --> 00:03:21,600
solutions there, which has basically 
three colors. 

59
00:03:21,600 --> 00:03:25,285
And it's not proven optimal, and you see 
the various colors of these things 0122, 

60
00:03:25,285 --> 00:03:28,880
okay. 
So, that's basically input. 

61
00:03:28,880 --> 00:03:32,357
Very simple, long list essentially of 
edges and then the output, which is 

62
00:03:32,357 --> 00:03:36,350
basically the color of every one of these 
vertices, okay. 

63
00:03:36,350 --> 00:03:39,098
So, input output is very simple in this 
problem, okay. 

64
00:03:39,098 --> 00:03:42,915
It's conceptually a very simple problem. 
But graph coloring is this beautiful 

65
00:03:42,915 --> 00:03:46,770
property that is very very difficult to 
solve, okay. 

66
00:03:46,770 --> 00:03:49,898
yeah, and this is an illustration of 
actually the two solution, the solutions 

67
00:03:49,898 --> 00:03:54,440
that we just produce here. 
so let me give you some assignment tips 

68
00:03:54,440 --> 00:03:57,600
here, okay. 
So, one other thing which is important 

69
00:03:57,600 --> 00:04:02,310
whatever the, whatever the approach that 
you're actually using. 

70
00:04:02,310 --> 00:04:06,350
Is that, you know, the degree of a node 
is important. 

71
00:04:06,350 --> 00:04:09,202
The higher the degree of a node, you 
know, the more difficult it is, the more 

72
00:04:09,202 --> 00:04:13,443
constrained that node is in a sense. 
You know, what the color that node can 

73
00:04:13,443 --> 00:04:16,170
take is basically limited by all it's 
neighbors, okay. 

74
00:04:16,170 --> 00:04:19,990
So, think about how that information can 
be exploited, okay. 

75
00:04:19,990 --> 00:04:23,392
So, other things that you have to think 
about is that there are a lot and lot of 

76
00:04:23,392 --> 00:04:27,646
symmetries in these problems, okay. 
So, we had a lot of lectures on 

77
00:04:27,646 --> 00:04:31,230
symmetries inside the constrained 
programming lecture. 

78
00:04:31,230 --> 00:04:35,902
Think about them, and think how they can 
be exploited inside this particular 

79
00:04:35,902 --> 00:04:39,422
assignment, okay. 
So, what you see there is the solution 

80
00:04:39,422 --> 00:04:41,590
there, okay. 
So, this is a solution, this is a 

81
00:04:41,590 --> 00:04:44,600
solution which is completely symmetric, 
okay. 

82
00:04:44,600 --> 00:04:47,300
You know, think about why these two 
things are symmetric. 

83
00:04:47,300 --> 00:04:49,640
There is a very simple rule and, you 
know, this is essentially some of the 

84
00:04:49,640 --> 00:04:52,331
techniques that we have seen in constrain 
programming there, for telling you what 

85
00:04:52,331 --> 00:04:56,299
kind of symmetry this is. 
But, this can be exploited and if want or 

86
00:04:56,299 --> 00:04:59,744
find actually, you know, very good 
solution and improve optimality, you will 

87
00:04:59,744 --> 00:05:04,182
have to use things like this, okay. 
And then, there are other things that you 

88
00:05:04,182 --> 00:05:06,719
want to do if, you know, if you want to 
improve optimality or if you want to 

89
00:05:06,719 --> 00:05:10,340
find, you know, to get a, a sense of what 
your solution is. 

90
00:05:10,340 --> 00:05:13,685
Try to find if they are easy lower bound 
that you can compute. 

91
00:05:13,685 --> 00:05:17,249
There is one very simple conceptual lower 
bound that you can take, and that will 

92
00:05:17,249 --> 00:05:20,780
tell you the best you can ever achieve, 
okay. 

93
00:05:20,780 --> 00:05:23,704
So, you know, there are lot of structure 
here, although the problem is very simp-, 

94
00:05:23,704 --> 00:05:26,499
you know it's very simple conceptually 
but there are lot of things that you can 

95
00:05:26,499 --> 00:05:29,990
exploit and that's why I love this 
problem, okay. 

96
00:05:29,990 --> 00:05:33,830
Now this is a beautiful graph here, you 
know, this is 250 vertices, it's about 

97
00:05:33,830 --> 00:05:37,819
3000 edges, okay. 
Which basically means that the density 

98
00:05:37,819 --> 00:05:41,264
here the den, you know, the density of 
the edges is 0.1% compared to the full 

99
00:05:41,264 --> 00:05:45,410
graph, okay. 
It's a reasonably easy answer. 

100
00:05:45,410 --> 00:05:48,340
I mean it's medium difficulty. 
It's still hard to prove optimality, but 

101
00:05:48,340 --> 00:05:51,440
this is not some of the most difficult, 
this is not one of the most difficult 

102
00:05:51,440 --> 00:05:55,184
instance. 
Now you can imagine a bushy, you know, it 

103
00:05:55,184 --> 00:06:00,021
becomes when you have 50% density, okay. 
So, that's much more complex and much 

104
00:06:00,021 --> 00:06:03,888
more difficult to solve, okay. 
So, so, this is essentially, you know, 

105
00:06:03,888 --> 00:06:07,560
what I wanted to tell you about the graph 
coloring assignment. 

106
00:06:07,560 --> 00:06:10,200
You can be really, really creative on 
this assignment. 

107
00:06:10,200 --> 00:06:13,880
It's a fantastic assignment, okay. 
And I look forward to see you compete in 

108
00:06:13,880 --> 00:06:16,930
finding a high-quality solution and 
proving optimality on some of these 

109
00:06:16,930 --> 00:06:20,280
instances. 
Okay, have fun, it's going to be really 

110
00:06:20,280 --> 00:06:21,440
interesting.