Python: Graph Colouring A simple method to find a colouring of a graph, with vertices {0,1,…,?−1}, is the following greedy algorithm: For ? in 0, 1, 2, ..., n - 1: Find the smallest colour (positive integer) ? which is not a colour of any neighbour of ?. Assign ? as the colour of ?. i) Implement the method above as a function greedy_colouring which takes a networkx Graph G (with vertices {0,1,…,?−1}) and returns a list C of the colours of G, where C[i] is the colour of vertex ?. ii) As a test, the Hoffman-Singleton graph (nx.hoffman_singleton_graph()) should require 6 colours using this method. If you have a graph G, you can draw it with coloured vertices using the code below: ten_colours = ['#CC6677', '#332288', '#DDCC77', '#117733', '#88CCEE', '#882255', '#44AA99', '#999933', '#AA4499', '#DDDDDD'] nx.draw_networkx(G, node_color=[ten_colours[i - 1] for i in greedy_colouring(G)], with_labels=False) iii) One way of refining the greedy algorithm is to sort the vertices in descending order of degre
Python: Graph Colouring A simple method to find a colouring of a graph, with vertices {0,1,…,?−1}, is the following greedy algorithm: For ? in 0, 1, 2, ..., n - 1: Find the smallest colour (positive integer) ? which is not a colour of any neighbour of ?. Assign ? as the colour of ?. i) Implement the method above as a function greedy_colouring which takes a networkx Graph G (with vertices {0,1,…,?−1}) and returns a list C of the colours of G, where C[i] is the colour of vertex ?. ii) As a test, the Hoffman-Singleton graph (nx.hoffman_singleton_graph()) should require 6 colours using this method. If you have a graph G, you can draw it with coloured vertices using the code below: ten_colours = ['#CC6677', '#332288', '#DDCC77', '#117733', '#88CCEE', '#882255', '#44AA99', '#999933', '#AA4499', '#DDDDDD'] nx.draw_networkx(G, node_color=[ten_colours[i - 1] for i in greedy_colouring(G)], with_labels=False) iii) One way of refining the greedy algorithm is to sort the vertices in descending order of degre
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
Python: Graph Colouring
A simple method to find a colouring of a graph, with vertices {0,1,…,?−1}, is the following greedy algorithm :
For ? in 0, 1, 2, ..., n - 1:
Find the smallest colour (positive integer) ? which is not a colour of any neighbour of ?.
Assign ? as the colour of ?.
i) Implement the method above as a function greedy_colouring which takes a networkx Graph G (with vertices {0,1,…,?−1}) and returns a list C of the colours of G, where C[i] is the colour of vertex ?.
ii) As a test, the Hoffman-Singleton graph (nx.hoffman_singleton_graph()) should require 6 colours using this method. If you have a graph G, you can draw it with coloured vertices using the code below:
ten_colours = ['#CC6677', '#332288', '#DDCC77', '#117733', '#88CCEE',
'#882255', '#44AA99', '#999933', '#AA4499', '#DDDDDD']
nx.draw_networkx(G,
node_color=[ten_colours[i - 1] for i in greedy_colouring(G)],
with_labels=False)
iii) One way of refining the greedy algorithm is to sort the vertices in descending order of degree before colouring them. This is a heuristic which may reduce the number of colours required; the idea is that high-degree vertices will be the most difficult ones to colour if you leave them until the end.
(a) Update your function greedy_colouring above so that it has an additional optional keyword argument use_heuristic with default value False, which determines whether it uses the heuristic (edit the function above, rather than copying it, arguments should be defined like so: def greedy_colouring(G, use_heuristic = False), extra argument must be optional; your function should work if you only provide G, do not have to sort vertices with the same degree in any particular order.)
(b) Generate 1000 random Erdős–Rényi graphs with 100100 vertices and edge-probability 0.20.2. For each one, calculate the difference in the number of colours used with and without the heuristic. Make a good histogram of these differences, and comment briefly on it. (if it takes more than 30 seconds, improve the efficiency of the code.)
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education