Report

ROUND ROBIN SCHEDULING BY NAGA SAI HANUMAN.POTTI OUTLINE • What is Round Robin. • Complete graph. • Real time Example. • Relation to graph problem. • Depicting graph solution. • Graph colouring. WHAT IS ROUND ROBIN? A round-robin story is one that is started by one person and then continued successively by others .It is an arrangement of choosing all elements in a group equally in some rational order in turn. A round robin format is problematic when the number of entries is high. For example, a tournament with 32 entries would take 496 games to complete using a round robin. ROUND ROBIN SINGLE DOUBLE A round-robin tournament is one in which every player plays against everyone else once. For example, with 3 players, we will have 3 matches: A-B, B-C, C-A. How many matches are needed for 4 players? 5 players? N players? If we can schedule two matches in the same time slot (round), how many rounds will it take for a 3player round-robin tournament? 4player tournament? 5-player tournament? Complete graph: complete graph is a graph in which every pair of distinct vertices connected by an edge. 1 K7::COMPLETE GRAPH WITH 7 VERTICES 7 2 6 3 5 4 Real time example: Lets take an indian premier league(IPL)cricket tournament and let it consists of 4 teams . Team 0-----Deccan chargers. Team 1-----chennai super kings. Team 2-----kolkata knight riders. Team 3-----Mumbai indians. Problem relating to graph: let us take a tournament with 4 teams (0,1,2,3).By using round robin we will depict the number of matches ,number of rounds and the teams involved in each round. Round Robin Graph Matches between teams 1 0,1 0 2 0,3 2,3 1,3 3 0,2 1,2 NUMBER OF ROUNDS We have n teams, and all teams play all others m times in m(n – 1) rounds. For single round robin: m=1 if n=4,i.e. 4 teams 3 rounds. For double round robin: m=2 if n=4,i.e. 4 teams 6 rounds. Calculate number of matches Matches between teams Case 1:Single Round Robin For n teams =n(n-1)/2 Case 2:Double Round Robin For n teams=2*(n(n-1)/2)=n(n-1) 0,1 0,2 0,3 2,3 1,3 1,2 Graph colouring: • graph colouring problem or vertex colouring problem involves assigning colours to each vertex v Ɛ V such that no pair of adjacent vertices is assigned the same colour and the number of colours used is minimal . • The minimum number of colours required to colour a particular graph is called the chromatic number". Assigning matches in each round : 0,1 0,1 0,2 0,3 2,3 1,3 1,2 0,2 0,3 2,3 1,3 1,2 0,1 0,2 0,3 2,3 1,3 1,2 ROUND 1st match 2nd match 1 (0,1) (2,3) ROUND 1st match 2nd match 2 (0,2) (1,3) ROUND 1st match 2nd match 3 (0,3) (1,2) ROUND 1st match 2nd match 1 (0,1) (2,3) 2 (0,2) (1,3) 3 (0,3) (1,2) Round robin schedule: For 10 teams: References http://en.wikipedia.org/wiki/Roundrobin_tournament. www.rhydlewis.eu/talks/sportsRRTalk.pdf. www.splendidcity.net www.tutorialspoint.com/...system/os_process _scheduling_algorithms.htm.