1) Which of the following graphs are isomorphic? The following are isomorphic: 1 and 3 2 and 6 4 and 5 Counting the edges in each node is useful for determining whether two graphs are not isomorpic. For example, in Graph 1 each node has 4 edges. In Graph 2, 2 nodes have 2 edges, therefore Graph 1 and 2 cannot be isomorphic. ------------------------------------------------- 2) Create Graph 1 from the examples above. from networkx import * G=Graph() G.add_edges_from([(1,2),(1,3),(1,6),(1,5),(2,4),(2,6),(2,3),(3,4),(3,5),(4,6),(4,5),(5,6)]) ------------------------------------------------- 5) Using the graphs G (from exercise 2) and G1, G2, G3 from exercise 4 determine the following. Only G2 is bi-partite. The complement has the same nodes as the original graph. It has edges between nodes which do not have edges in the original graph. The radius of G3 is 11, the distance is 21. Therefore G3 does not have a small-world effect with "six degrees of separation". The distance can only be at most twice the radius. ------------------------------------------------- 6) Determine the chromatic number Graphs 1/3, 2/6, 4/5 and G1 all have a chromatic number of 3. Because they all contain a complete graph of three nodes, it is not possible to colour them with 2 colours. G2: chromatic number: 2 because a bipartite graph can always be coloured with two colours. G3: chromatic number: 10 because it contains a complete graph with 10 nodes. Eulerian path: 1/3: start and finish in any node 2/6: start and finish in nodes 1 or 3 because these have an odd number of edges 4/5: start and finish in nodes 3 or 5 because these have an odd number of edges G1: this is the graph discussed in the lecture slides G2: there is no Eulerian path because all nodes have an odd number of edges G3: there is no Eulerian path because 10 nodes have an odd number of edges Hamiltonian path: Graphs 1/3, 2/6, 4/5 and G1 have a Hamiltonean path. G2: does not have a Hamiltonian path because a bipartite graph can only have a Hamiltonian path if the size difference between the partitions is at most 1. G3: does have a Hamiltonian path.