1 00:00:00,210 --> 00:00:06,390 This problem is referring to the graph edge coloring, so suppose we have a graph, we have a connected 2 00:00:06,390 --> 00:00:16,620 graph and we want to paint the edges in a way that no two edges that have some mutual nodes have the 3 00:00:16,620 --> 00:00:17,280 same color. 4 00:00:17,520 --> 00:00:19,790 So look at here. 5 00:00:19,800 --> 00:00:20,910 Look at the node nine. 6 00:00:20,940 --> 00:00:23,250 There are four edges connected to this node. 7 00:00:23,580 --> 00:00:25,990 None of these edges should have the same color. 8 00:00:26,010 --> 00:00:34,860 So we want to find out what is the minimum number of required, um, colors to, um, paint this graph. 9 00:00:35,040 --> 00:00:39,260 OK, so let's write down the codes. 10 00:00:39,450 --> 00:00:49,820 So here you can see that, um, for every, um, for every node, we should have some, um, limits. 11 00:00:50,310 --> 00:00:56,480 So let's for every eye and see for every eye and see we have to write down this constraint. 12 00:00:56,910 --> 00:01:00,030 So it is saying that summation of X I. 13 00:01:00,910 --> 00:01:08,680 J.C., and the summation is over, Jay, whatever is connected to I and it should be less than one, 14 00:01:08,680 --> 00:01:17,470 it means that the summation of all the edges, um, that are connected to one specific node, um, should 15 00:01:17,470 --> 00:01:18,420 be less than one. 16 00:01:18,790 --> 00:01:21,820 And this is valid for every I and I see. 17 00:01:21,820 --> 00:01:22,990 So it no. 18 00:01:22,990 --> 00:01:27,970 Two edges have the same color if they are connected to one node. 19 00:01:27,970 --> 00:01:33,100 OK, and the other one is that like the previous one, like the not coloring one. 20 00:01:33,110 --> 00:01:37,210 So why is bigger than C, C and C. 21 00:01:37,750 --> 00:01:43,890 And also we should say that every edge should take only one color. 22 00:01:43,900 --> 00:01:46,090 This is the last equation. 23 00:01:46,120 --> 00:01:50,980 OK, so if I run this simulation, this is what you get. 24 00:01:50,980 --> 00:01:58,240 So you can see here, that's how the graph is colored and the number of required colors are determined. 25 00:01:58,300 --> 00:02:05,420 OK, so, um, let's have a look at the Python code for this problem. 26 00:02:06,130 --> 00:02:14,200 Um, here you can see that, uh, first of all, we need to import the required. 27 00:02:16,570 --> 00:02:22,900 Packages like matplotlib that works here is not needed to reach important. 28 00:02:22,930 --> 00:02:32,590 I can remove this one and so because we already have it here, so I create a random regular graph and 29 00:02:32,710 --> 00:02:36,070 with the degree of four or four and they are 30. 30 00:02:37,280 --> 00:02:48,290 Nodes and I plot it and then I import the required kind of packages, construct a model, so that model 31 00:02:48,290 --> 00:02:53,720 is an abstract model and is the number of nodes, as you can see, it is initialized with a number of 32 00:02:53,720 --> 00:02:56,670 nodes and the number of edges and. 33 00:02:57,820 --> 00:03:09,790 I and J are the set of notes L. is the connection matrix colour is the colour and also, um, X and 34 00:03:09,790 --> 00:03:11,680 Y are two variables. 35 00:03:11,680 --> 00:03:14,280 X is the fight over IJA and colour. 36 00:03:14,470 --> 00:03:20,670 So it means that the colour of new edge which is connected between A.. 37 00:03:20,680 --> 00:03:21,860 I know J. 38 00:03:22,240 --> 00:03:23,920 And why is the object objective function. 39 00:03:24,410 --> 00:03:31,620 OK, so in order to solve that we should create a constraint saying the first constraint actually. 40 00:03:31,990 --> 00:03:34,450 So if I show you that again. 41 00:03:34,450 --> 00:03:35,400 So here I am. 42 00:03:35,560 --> 00:03:36,740 I right on this one. 43 00:03:37,250 --> 00:03:43,240 OK, so in order to um, write it down, I write this expression. 44 00:03:43,360 --> 00:03:46,060 So initially the M expression is. 45 00:03:47,340 --> 00:03:57,480 Equal to zero, OK, and for every DJ in the model J, if J is connected to so excited and C is added 46 00:03:57,480 --> 00:04:09,180 to the EXI or if LG is one, then I will be added to the model and that expression should be less than 47 00:04:09,180 --> 00:04:10,020 equal to one. 48 00:04:10,470 --> 00:04:10,710 Hmm. 49 00:04:11,640 --> 00:04:16,080 OK, and that constraint is defined over model, eye and color. 50 00:04:17,550 --> 00:04:26,670 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 51 00:04:26,670 --> 00:04:36,300 summation over and all color and I and J if they are connected to each other and this is why the reason 52 00:04:36,300 --> 00:04:44,880 that I'm doing this is that if I define it, why bigger than C, X, I, J and C, this means that um 53 00:04:45,000 --> 00:04:50,430 for every combination of J and C, I have to create a constraint, OK. 54 00:04:50,580 --> 00:04:54,240 And that will hugely increase the size of the model. 55 00:04:54,450 --> 00:04:58,520 OK, but that's kind of modeling gives you the same kind of result. 56 00:04:58,890 --> 00:05:04,620 And finally, every edge should have only one color. 57 00:05:06,270 --> 00:05:11,490 OK, and um, finally the objective function is why. 58 00:05:11,490 --> 00:05:22,410 And the model is we can specify the gap for the in the programming which I did it here so I can run 59 00:05:22,410 --> 00:05:25,050 these tabs and show you the results. 60 00:05:25,080 --> 00:05:28,830 OK, so first of all, we have to create a graph. 61 00:05:29,200 --> 00:05:29,440 Hmm. 62 00:05:30,120 --> 00:05:31,020 OK. 63 00:05:31,210 --> 00:05:32,340 And this one. 64 00:05:33,450 --> 00:05:44,160 OK, so here I have to create the and L part and also and this is one way of creating the data and feeding 65 00:05:44,160 --> 00:05:46,110 it into the promo. 66 00:05:46,290 --> 00:05:54,390 So I create a dictionary and feel every um required parameter in a model. 67 00:05:54,780 --> 00:05:56,520 OK, so I run it again. 68 00:05:56,970 --> 00:06:03,700 So it is run and I uh here just the model is being fed with the input data. 69 00:06:03,910 --> 00:06:07,260 OK, and the model is solved. 70 00:06:07,480 --> 00:06:10,320 Um uh you can see the results here. 71 00:06:10,330 --> 00:06:16,500 So the result is telling me that it's showing that IGCC and the value of it. 72 00:06:16,510 --> 00:06:18,170 So see the value of it. 73 00:06:18,180 --> 00:06:25,020 Is that so it means at the end the node between zero and seventeen is colored with the color number 74 00:06:25,030 --> 00:06:29,230 three node between one and six is called the number two and so on and so on. 75 00:06:29,250 --> 00:06:36,100 OK, um, and you can, uh, graphically see what's happening here. 76 00:06:36,730 --> 00:06:43,930 OK, so here you can see that, for example, I know thirteen four colors are used and so on. 77 00:06:44,260 --> 00:06:47,220 OK, and that's it for this example. 78 00:06:47,230 --> 00:06:48,060 Thank you very much.