I am in my first year of Computer Science and we have an exam coming up. One of our tasks will be to find properties of a graph just by looking at a distance table for the graph. I could do these easily, if there was a picture of the graph but I am not sure I'll have time to draw it, plus I guess it's much more efficient not having to draw a graph. So, we are given the following table:
Our task is to find four properties of the following which are true for this graph:
A graph with two components.
A graph that is not connected.
A connected graph.
An undirected graph.
A mixed graph.
A graph with an Euler cycle.
A complete graph.
A weighted graph.
A graph with a Hamilton cycle.
A directed graph.
I think the following three are true:
- An undirected graph.
- A connected graph.
- A weighted graph.
However, I am pretty stuck on how should I determine if there is an Euler or Hamilton cycle present in the graph just by looking at the matrix. Is there any good ways to do this? Am I missing something?
Thanks!
Most of the properties can be found easily by drawing it.
A graph has a eulerian cycle if and only if for every vertex indegree==outdegree and the graph is connected. If the graph is not directed this translates to the degree of each vertex is even.
The idea of the proof is that you can just start walking from a vertex and since the degree of each vertex is even you will always have an edge to leave the vertex until you come to back to your original vertex. If you have unvisited edges, then there must be a vertex with even unvisited edges. You apply the same strategy for the this vertex and the unvisited nodes and get another cycle which you can insert in the first one. repeat until no edges left. https://en.wikipedia.org/wiki/Eulerian_path
Deciding if a graph has a hamiltonian cycle is NP-complete, so thats quite hard but you can just try to find one by looking at it or maybe you can show that there is non for cases like there is a vertex with degree 1 ( there cannot be a cycle through that vertex if this is a deadend) or if its not connected. https://en.wikipedia.org/wiki/Hamiltonian_path
In your example: A has degree 2 (B and D) so one of them must be before A in the cycle and the other one after A. Since we can walk the cycle forward or backwards, we only have to check one: w.l.o.g DAB is in the cycle. Now we look at the endpoints of DAB and take the one with the lesser degree (D). Now we do a case distinction on the vertices that could be before D (C or E). Assume E: so EDAB now we spot that CFGEDAB is a hamiltonian cycle.