Programming Illustration : Emergence of Connectedness

Summary

This script explores the surprising result that a graph with n nodes becomes connected with just n log n edges when added randomly. It demonstrates through coding in Python using NetworkX how to create a graph, add nodes and random edges, and determine the number of edges needed for connectivity. The script also includes a visual comparison of the actual number of edges required against the theoretical n log n, showing that while not exact, the number of edges needed is approximately of that order, thus validating the claim.

Takeaways

• 📈 The script discusses a surprising result in graph theory, stating that a graph with n nodes can be made connected with just n log n edges.
• 💡 The concept is demonstrated with a practical experiment using a screencast to write code that tests this theory with random graphs of varying sizes.
• 🔍 The code involves creating a graph with a specified number of nodes and then adding random edges one by one until the graph becomes connected.
• 🛠️ The script includes a step-by-step guide on how to write the code in Python using the NetworkX library to handle graph operations.
• 📝 A function named 'add_nodes' is defined to add a specified number of nodes to a graph, initializing the process of making the graph connected.
• 🔗 The 'add_random_edge' function is introduced to add a single random edge to the graph, helping in the gradual connection of the graph.
• 🔄 A loop is used to continuously add random edges to the graph until the 'is_connected' function from NetworkX returns true, indicating the graph is fully connected.
• 📊 The script suggests plotting the relationship between the number of nodes and the number of edges required for connectivity to visualize the results.
• 📈 The plot shows a curve that, with averaging over multiple instances, becomes smoother and more indicative of the theoretical n log n relationship.
• 🔍 The script questions whether the number of edges required is exactly n log n, and adjusts the plot to compare the actual data with the theoretical n log n curve.
• 🧩 Finally, the script concludes that while the exact number of edges may not be n log n, it is of the order of n log n, supporting the initial claim with empirical data.

Q & A

What is the surprising result discussed in the script about graph connectivity?

The surprising result is that on a graph with n nodes, only n log n number of edges are needed to make the graph connected, allowing a path from any node to every other node in the network.

What is the purpose of the 'connectivity.py' file in the script?

The 'connectivity.py' file contains the code necessary for creating a graph, adding nodes, and adding random edges to the graph until it becomes connected.

What is the role of the 'add_nodes' function in the script?

The 'add_nodes' function initializes a graph with a specified number of nodes using the NetworkX library, which is essential for setting up the graph for further operations.

How does the 'add_random_edge' function work in the script?

The 'add_random_edge' function selects two random vertices from the graph and adds an edge between them, provided the vertices are not the same to avoid self-loops.

What is the purpose of the 'add_till_connectivity' function?

The 'add_till_connectivity' function continuously adds random edges to the graph until the graph becomes connected, demonstrating the process of achieving graph connectivity.

How does the script verify if the graph is connected?

The script uses the 'nx.is_connected' function from the NetworkX library to check if the graph is connected after adding edges.

What is the significance of the 'create_instance' function in the script?

The 'create_instance' function encapsulates the process of creating a graph with a certain number of nodes and determining the number of edges required to connect the graph.

What does the 'plot_connectivity' function do in the script?

The 'plot_connectivity' function plots the relationship between the number of nodes and the number of edges required for connectivity, providing a visual representation of the graph connectivity process.

Why are there spikes in the initial plot of the script?

The spikes in the initial plot occur due to the randomness of the experiment. Each execution can yield slightly different results, causing fluctuations in the number of edges required for connectivity.

How does averaging the results over multiple instances affect the plot?

Averaging the results over multiple instances smooths out the plot by reducing the impact of random fluctuations, providing a more consistent and reliable representation of the data.

What does the script conclude about the relationship between the number of nodes and edges required for connectivity?

The script concludes that the number of edges required to connect a graph is of the order of n log n, which aligns with the initial surprising result discussed.