We have already learnt the different types of graphs. Now we are going to learn the properties of these graphs. This section, again, will be full of terminologies to be remembered. Some have quite similar meanings, so take note not to confuse them.
- A walk is an alternating sequence of vertices and edges of a graph. A closed walk is defined to be a walk which starts and ends with the same vertex.
- A path is a sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along the edges of the graph. A simple path is then a path which doesn’t contain the same edge more than once. The length of a path is the amount of edges that the path contains.
- A trail is a walk that has no repeated edges. In some cases when the word trail is used, a path could mean a walk that has no repeated vertices. Take note of the double meaning of the word path.
- A circuit is a path that begins and ends at the same vertex in an undirected graph. A simple circuit is then a circuit with not repeated edges.
- A cycle is a path that begins and ends at the same vertex in a directed graph.
- The degree sequence is the listing down of all the vertices not by its name, but by its degree of vertex. It is listed in non-increasing (which means, decreasing lah…) order.
To illustrate these 5 terms, I will show you an example below:
* You can construct many walks in this graph. An example of a walk here is (v1, e1, v2, e6, v3, e7, v4). Remember that a walk starts and ends with a vertex.
* An example of a path is e1, e6, e7 or e2, e5, e7, which both have length 3.
* A trail can be just as the walk above, (v1, e1, v2, e6, v3, e7, v4), as long as there are no repeated edges.
* A circuit here, can be something like e1, e6, e5, e2 or e3, e6,e2. It will be called as a cycle if it were a directed graph. Note that you can only follow the directions of the arrow for a cycle.
* The degree sequence for v1, v2, v3, v4 is 6, 4, 3, 1. Remember that the sum of the degree of vertex should be an even number.
CONNECTEDNESS
A graph is connected when there’s a path between every pair of distinct vertices of the graph. This means that, if I start walking from any vertex, I am able to reach any other vertex by traversing the edges (by the way, you pass through a vertex, but traverse an edge).
In the case of a directed graph, we say that it is strongly connected when there is a path a → b and b → a whenever a and b are vertices of the graph. And then, it is weakly connected when there is at least a path a → b or b → a for any vertex a and b in the graph. Or in other words, a weakly connected graph exists if there is a path between every 2 vertices in the underlying undirected graph.
A connected component is just a connected subgraph. For example, the graph
has 3 connected components. We can further say that a component is a strongly connected component / strong component if a component is the maximal strongly connected subgraph.
Cut vertices (articulation points) are vertices whose removal and all the edges incident with it produces more connected components than the original graph.
Cut edges (articulation bridges) are edges whose removal produces a graph with more connected components than in the original graph.
ISOMORPHIC GRAPHS
We say that 2 graphs are isomorphic if:
1. They have equal vertices and edges, degree sequence and length of simple circuits
(these properties are known as the graph invariants).
2. Follow paths that go through all vertices so that the corresponding vertices of the 2 graphs
have the same degree.
For example, the graphs below:
You notice something? A and R are isomorphic graphs. Also, F and T, K and X, and M, S, V and Z are isomorphic graphs. It is easy to identify isomorphic graphs for small amount of vertices, but remember to use the above rule if the graphs are really complicated.
EULERIAN TRAILS & CIRCUITS
The town of Kӧnigsberg, Prussia was divided into 4 sections by the branches of the Pregel River. These 4 sections included the 2 regions on the banks of the Pregel (A & B), Kneiphof Island (C), and the region between the 2 branches of the Pregel (D). In the 18th century, 7 bridges connected these regions.
On Sundays, the residents take long walks through the town. They wondered whether it was possible to start at some location in the town, travel across every bridge without crossing any bridge twice and return to the starting point. Do you want to try and see whether you can find a simple circuit for them?
We’ll come back later. An Eulerian Trail (or Euler Path) is a simple trail that contains every edge in the graph, while an Eulerian Circuit (or Euler Circuit) is a simple circuit containing every edge in the graph. For example,
An Euler Circuit in the graph is e3, e1, e2, e6, e7, e5, e4, e9, e10, e8. Take note that an Euler path doesn’t necessarily return to the same vertex, but an Euler circuit has to. By the way, the word ‘Euler’ is read as ‘Oil-lerr’, not ‘you-lerr’.
It is found that there is a condition for these Eulerian properties to exist:
An Eulerian trail exists in a graph if there are exactly 2 vertices with odd degrees.
An Eulerian circuit only exists if every vertex in a graph has even degrees.
Take a look at the graph above, you will see that every vertex has degree 4. That explains why an Eulerian circuit exist.
Now, let’s rephrase our previous question. So are we able to find an ‘Eulerian circuit’ for the Kӧnigsberg bridge? First, we draw the bridges as edges, the river banks and islands as vertices. We get a graph like this:
Counting the degree of vertices, we find that these 4 vertices have odd degrees. Therefore, we can conclude that it is impossible to cross all 7 bridges, and come back to the same spot, neither is it possible to cross all the bridge once in any order. Although we didn’t find a solution, we proved that a solution can’t found.
HAMILTONIAN PATHS & CYCLES
Just now we did for edges, now we do the same for vertices. A Hamiltonian path (or Hamilton path) is a simple path in a graph that passes through every vertex exactly once, whereas a Hamiltonian cycle (or Hamilton circuit) is a simple cycle in a graph that passes through every vertex exactly once. Look at the graph below:
The red lines shows a Hamiltonian cycle. Note that the word cycle here might not necessarily mean that it has to be a directed graph. A Hamiltonian path, doesn’t need to start and end at the same vertex.
Surprisingly, there is no known simple necessary and sufficient criteria for the existence of Hamiltonian cycles. However, there are 2 theorems over here which might possibly work. I don’t think this is examinable:
1. Dirac’s Theorem: The graph G has a Hamiltonian cycle if the degree of every vertex is at least half of the number of vertices. n, with n ≥ 3.
Note that this theorem doesn’t say anything about graphs whose degree of every vertex less than half of the number of vertices. It might, and might not have a Hamilton path, and you have to check it through.
2. Ore’s Theorem: The graph G with n vertices has a Hamiltonian cycle if for every non-adjacent pairs of vertices u and v, deg (u) + deg (v) ≥ n.
I believe Hamiltonian cycle questions in STPM won’t be too hard, so don’t worry too much about it for now. Questions on Euler and Hamilton paths and circuits will involve identifying them, or focusing on what you can do to make an Euler or Hamilton circuit exist.
OTHER EXTRA INFORMATION
These are probably out of the syllabus, but I treat it as extra information for you:
1. Planar Graphs
A planar graph is a graph that can be drawn in the plane without any edges crossing. In this case, a region is the area bounded by a circuit in the graph. There are quite a few corollaries for planar graphs, for example,
* If G is a connected planar simple graph, then G has a vertex of degree not exceeding 5.
* If G is a connected planar simple graph with e edges and v vertices, where v ≥ 3, then
3v – 6 ≥ e
* If a connected planar simple graph has e edges and v vertices with v ≥ 3, and has no circuits of length three, then 2v – 4 ≥ e.
* Kuratowski’s Theorem states that a graph is nonplanar iff it contains a subgraph homeomorphic to K3,3 or K5. 2 graphs are homeomorphic if they can be obtained from the same graph by a sequence of elementary subdivision, which is the action of putting a vertex in the middle of an edge.
The crossing number is the minimum number of crossings that can occur when a graph is drawn in plane where no 3 edges are permitted to cross at the same point. The thickness of the graph is the smallest number of planar subgraphs of G than have G as their union.
2. Euler’s Formula
For a connected planar simple graph, The amount of regons can be represented by the equation r = e – v + 2.
3. Chromatic Number
We define the chromatic number χ(G) to be the least number of colours needed for a colouring of a graph. Colouring is defined to be the assignment of a colour to each vertex of the graph so that no 2 adjacent vertices are assigned the same colour. Recall what you learnt about bipartite graphs in the previous section. The Four Colour Theorem states that the chromatic number is always less than 4 for a planar graph. We say that a graph is chromatically k-critical if the chromatic number of G is k, but for every edge e, the chromatic number is k – 1 by deleting this edge from G.
We could modify the definition of colouring to describe edges too. Edge colouring is an assignment of colours to edges so that edges incident with a common vertex are assigned different colours. The edge chromatic number is the smallest number of colours that can be used in an edge colouring in a graph. The edge chromatic number can actually be found by finding the biggest number of degree of vertex in the graph.
4. Vertex Basis
A vertex basis is a set of vertices where there’s a path to every vertex outside this set from vertices of this set, and there’s no path from any vertex in the set to another vertex in the set. In other words, any vertex in a directed graph, which only points outwards but not inwards, is belongs to a vertex basis.
Other than the last part of this section, please put some effort in reading them. Graph Theory is easy, so make sure you score it. ☺
From the notes above is it mean that a hamiltonian cycle is also known as hamilton circuit?
ReplyDeleteYes. Remember the definition cycle is for a directed graph, circuit for undirected. However, the terminologies differ from text books, so as long as you see the word Haimiltonian, you know what it is.
ReplyDelete