DMS U5 Scheduling Problems

[00:00:01]Hello everyone. Today let's see some applications of graph coloring scheduleuling problem. Graph coloring is a mathematical method used to solve conflicts and scheduleuling problems.

[00:00:14]Suppose multiple different events occur at any given time but some events have conflicts. The minimum number of time required so that all the events can occur. Such type of problems can be modeled using graph coloring. So here vertx represents job to be scheduled.

[00:00:33]Color represents available time slots.

[00:00:36]Chromatic number gives the minimum number of time slots required to complete all the jobs. There are uh two types of coloring. One is vertx coloring. The other one is edge coloring. Vertx coloring applied when the objects are assigned to the time slots. The vertex represents the item to be assigned or scheduled. In edge coloring, uh here the edge represents the activities to be scheduled.

[00:01:05]Here are some applications of vertx coloring, exam timetabling, map coloring, frequency assignment, traffic signal optimization, and so on. Fridge coloring, tournament scheduuling, employee shift scheduuling, flight scheduuling, network communication scheduuling and so on.

[00:01:23]Let us discuss some questions. First question. There are eight people say A B C D E F G H.

[00:01:34]There are seven teams. Team one consist of member A B and C. T2 member C D E.

[00:01:44]T3 DF T4 A G T5 E H T6 B E G T7 C F H.

[00:01:53]So by using graph theory we need to model the graph where vertex to be considered as the team and the edge will be when the two teams have the same I mean common member. Apply vertx coloring to determine the minimum number of time slots required to conduct all team meetings without any employee attending two meetings simultaneously. So let us draw the graph based on the given data.

[00:02:28]Considering the vertex as the teams t1 to t7 and the edges going to be when the teams have common element.

[00:02:40]So T1 let us compare with the uh other teams. T1 can be compared with the T7 T6. So T7 and T6 have common element C and B. So there will be an edge between uh T1 to T7 and T1 to T6.

[00:03:01]And uh T5 does not have any common element. T4 and T2 has common elements C and A that exist in edge. Similarly, we'll plot for other vertices T2, T3, T4, T5, T6 and T7. So now T2 is connected with T1, T7, T6, T5 and T3.

[00:03:30]T3 is connected with T2 and T7. T4 is connected with T1 T6. T5 is connected with T7.

[00:03:41]T6 is connected with T1, T2, T uh 4. T7 is connected with the T1, T2, T3 and T5. So now we are going to give the color for the vertices and uh the condition is no two adjacent vertx vertices should have same color.

[00:04:08]So here t_1 t3 and t5 are non-adjacent vertices. Let me consider red color for this.

[00:04:16]T2 and t4 are nonadjacent vertices. So black T7 and T6 are nonadjacent vertices green.

[00:04:26]So the minimum number required minimum number of colors required to color the graph is three.

[00:04:36]That is the minimum three meeting time slots is required to conduct all 17 meetings without anyuling conflicts.

[00:04:47]Here's the second question.

[00:04:52]The following graph shows the traffic line at the intersection of two streets and the traffic light is located at this intersection.

[00:05:02]So during a certain phase of the traffic light, vehicles in the lane for which the light is green may proceed safely through the intersection. Determine the minimum number of phases needed for the traffic light so that all the vehicles may proceed through the intersection. So this is going to be done by graph coloring.

[00:05:24]That is if two traffic movement intersects or interfere with each other.

[00:05:30]The corresponding vertex are connected by an edge. [clears throat] To ensure safe traffic flow, the adjacent vertices must receive different colors. So we are going to uh plot a graph according to the condition.

[00:05:48]Each color represent separate traffic signal phase allowing non-conlicting traffic movement to proceed simultaneously. So let us so now let us consider the graph with the the vertices considering the traffic lines L1 to L8 from the given figure.

[00:06:14]So there are seven eight vertices L1 L2 L3 L4 L5 L6 L7 and L8.

[00:06:21]So based on the intersection, let us introduce the edges between these vertices.

[00:06:30]So L1 is intersecting with L3, L5, L7 and L8. Then L2 is intersecting with L3, L4, L5, L6, L8.

[00:06:44]L3 is intersecting with L1, L2, L8, L6.

[00:06:50]L4 is intersecting with L8, L7, L6, L5, L2.

[00:06:57]L5 is intersecting with L1, L2, L8, and L7. L6 is with L2, L3, L4, L7.

[00:07:10]And uh L7 is with L1, L4, L5, L6. L8 is intersecting with L5, L4, L3, L2 and L1.

[00:07:22]So the degree of uh the vertices will be like for L1 it is 4, L2 is 5, L3 is 4, L4 is 5, L5 is 5, L6 is 4, L7 is 4, L8 is 5.

[00:07:46]So now we have to color the vertices based on the condition that no two adjacent vertices will get same color.

[00:07:56]So L1 and L2 are nonadjacent vertices.

[00:08:00]We are coloring it with orange.

[00:08:02]L3 and L4 are nonadjacent with a different color.

[00:08:10]L8 and L7 are nonadjacent. plotting with the green color.

[00:08:15]L6 and L5 are nonadjacent. Plotting with blue color.

[00:08:20]So there are minimum four colors required for the vertx coloring for this graph.

[00:08:30]So the minimum number of phase required for traffic light so that the vehicle can proceed through the same lane is four.

[00:08:41]So from this graph coloring we can conclude that L1 and L2 can proceed at same time. Similarly L3 and L4 can proceed at same time.

[00:08:57]L5 and L6 can proceed simultaneously.

[00:09:01]L7 and L8 can proceed simultaneously.

[00:09:06]So this is how we are modeling the given uh data through vertx coloring.

[00:09:17]The next example, an electric power network consists of six substations A B C D E F. The power lines connecting the substations are given as A B A C B C B D C E D E E F and DF. Each power line requires periodic inspection. For safety reasons, two power lines sharing a common substation cannot be inspected simultaneously.

[00:09:47]Represent the substations as vertices and the power lines as edges. Construct the graph and determine the minimum number of colors required for edge coloring. So from the given question, let us consider the vertices as substations and the edges as par lines.

[00:10:09]So we can construct a graph of par network considering these uh substations as vertices A, B, C, D, E, and F. And from the given data we'll construct the edges between the vertices A B A C B C B D C E D E E F and D F.

[00:10:37]Now let us color the edges.

[00:10:43]So here A B uh C E D F or non-adjacent. So we are coloring it with red and uh A C B D E F or non-adjacent let us color with green and D E is colored with black.

[00:11:10]As before the chromatic number is three.

[00:11:15]Hence all power lines can be inspected in three time slots without any conflict ensuring that no two power lines connected to same substations are inspected simultaneously.

[00:11:32]Just do one more question.

[00:11:36]Example number four. Seven volleyball teams from cities C1 to C7 have been invited to participate in tournaments where each team is scheduled to play a certain number of other teams.

[00:11:51]No team is to play more than one game each day. Using graph theory, set up a schedule of games over the smallest number of days. So finding the edge coloring number and minimum number of days we are going to construct based on the given data.

[00:12:10]So here are the uh data here C1, C2, C3, C4, C5, C6 and C7.

[00:12:18]So based on this we have constructed the graph.

[00:12:25]C1 is connected with the C2, C3, C6 and C7. C2 is connected with C1, C3 and C7.

[00:12:37]C3 is connected with C1, C2, C4, C5. C4 is connected with C3, C5, C6, C7. C5 is connected with C3, C4 and C6. C6 is connected with C1, C5, C4, C7. C7 connected with the C1, C2, C4, C6. So based on this given data we have constructed a graph. Now the coloring so that based on the same condition.

[00:13:15]So the non-adjacent edges we are going to choose to give the same color. There are totally 13 edges and the maximum degree is four.

[00:13:28]Now C1 C2 the edges C1 C2 C3 C4 or nonadjacent C1 C6 C4 C7 C3 C5 green C2 C7 C C4 C6 So this is how we are giving different colors which satisfies uh no two adjacent edges as same color.

[00:14:09]So here there are uh four colors sorry five colors red, orange, green, blue and black.

[00:14:21]Five colors for the these is the these are all the minimum number of colors required.

[00:14:28]The edge chromatic number is five.

[00:14:30]Minimum days required is five. The conclusion will be like all the 13 matches can be successfully scheduled over 5 days with every team playing at most one match per day.

[00:14:45]So from the given data we are concluding with the statement where five days required for every team to play at most one uh one day.

[00:15:01]The last one fifth question.

[00:15:06]There are seven railway stations S1 to S7 are connected by direct train service. Each train service operates between two stations assuming that each station has only one platform so that it handle only one train during a given time slot.

[00:15:26]Consequently, two train services shares common station and cannot be scheduled simultaneously.

[00:15:35]The train service are as follows.

[00:15:40]The train service are given here.

[00:15:43]S_ub_1, S_UB_2, S3, S4, S5 to S7.

[00:15:48]Using graph theory, the train schedule with the minimum number of time slots we are going to do. So let us consider uh the vertices with the stations S1 to S7.

[00:16:04]Now let us plot uh the edges between the vertices based on the given data.

[00:16:19]Now let us do the coloring for the uh edges.

[00:16:29]There are seven vertices.

[00:16:32]So let us color nonadjacent edges.

[00:16:44]So the minimum color required for edge coloring here is five.

[00:16:57]So the railway network is [clears throat] represented by a graph in which the stations are vertices and the train services are edges. Since a station can handle only one train during a given time slot, adjacent edge [clears throat] must receive different color. The minimum time slots required to schedule all train service is five.

[00:17:22]Also the coloring shown uh in the previous questions this is these are all valid but it can be in different assignment also assign different assignment is also possible.

[00:17:38]Thank you.