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.