HW9. Graphs (11th of Nov, 23.59)
EX1. There are many data types that can be represented as graphs. Study online collection at https://snap.stanford.edu/data/. Select from there 4 graphs that are different in type and size. First, consider them as undirected and characterize them by calculating:
- Nr of nodes
- Nr of edges
- Distribution of node degrees (visualize it using histogram)
EX2. Implement a BFS algorithm for the very same graphs (considering graphs unweighted, undirected).
- Measure or estimate time for 1000 BFS searches from random start vertices; reporting also the "depth of the component" starting from different vertices.
- Estimate the diameter of the graphs (based on 1000 searches). Draw the distribution of lengths of longest shortest paths you encountered.
Hint: if it takes too much time to run 1000 searches opt for less, but explain the reason.
EX3. When doing the BFS in the previous exercise, also test for the bipartiteness of the graph. Most of them aren't clearly. For those that are not bipartite - report how quickly do you detect that based on BFS, e.g. for X2 searches it was already when going to "2 hop" neighbourhood when you discovered it; for X3 searches within 3 hops, etc…
EX4. Take the freedom to remove greedily those edges that make graphs from EX3 non-bipartite. There may be different ways for that - to remove the edge when you first detected a problem; or remove previous that caused the "problem". Characterize the same graphs before and after using the same simple measures like the degree distribution and the diameter (before and after).
EX5. Use directed graph below - the direction is indicated by blue dot at the target of the edge. For this graph calculate the strongly connected components and the topological sort order of the components. Always apply the lexicographic ordering (in outer cycle generating a DFS forest; as well as selecting edges for expansion).
Report obtained strongly connected components and the topological order. Explain the steps you took to calculate them (potentially visualize).
EX6. (Bonus 2p) Use the graph from the lecture - below. From this graph create and visualise a corresponding line graph. Formulate the Euler and Hamilton path tasks on original graph and line graph. How do these relate to the Euler and Hamilton paths in the original graph? Can you find actual Euler and Hamilton paths for this graph?
