Struktur Diskrit : Graf Planar
Planar Graph
Consider the problem of joining three houses to each of three separate utilities, as shown below. Is it possible to join these houses and utilities so that none of the connections cross?
This problem can be modeled using the complete bipartite graph K3,3.
Can K3,3 be drawn in the plane so that no two of its edges cross?
Definition
A graph is called planar if it can be drawn in the plane without any edges crossing. Such drawing is called a planar representation of the graph.
Example:
Regions
A planar representation of a graph splits the plane into regions, including an unbounded region. For instance, the planar representation of the graph shown below splits the plane into six regions.
Euler Formula
Theorema 1. Let G be a connected planar simple graph with e edges and v vertices. Let r be the number of regions in a planar representation of G. Then, r = e – v + 2.
Example:
Suppose that a connected planar simple graph has 20 vertices, each of degree 3. Into how many regions does a representation of this planar graph split the plane?
Solution: This graph has 20 vertices, each of degree 3, so v = 20. Because the sum of the degrees of the vertices, 3v = 3 · 20 = 60, is equal to twice the number of edges, 2e, we have 2e = 60, or e = 30. Consequently, from Euler’s formula, the number of regions is
r = e − v + 2 = 30 − 20 + 2 = 12.
Corollary 1
If G is a connected planar simple graph with e edges and v vertices, where v ≥ 3, then e ≤ 3v – 6. Show that K5 is nonplanar using Corollary 1.
Solution: The graph K5 has five vertices and 10 edges. However, the inequality e ≤ 3v − 6 is not satisfied for this graph because e = 10 and 3v − 6 = 9. Therefore, K5 is not planar.
Corollary 2
If G is a connected planar simple graph, then G has a vertex of degree not exceeding five.
Corollary 3
If a connected planar simple graph has e edges and v vertices, with v ≥ 3 and no circuits of length three, then e ≤ 2v – 4. Show that K3,3 is nonplanar using Corollary 3.
Solution: Because K3,3 has no circuits of length three (this is easy to see because it is bipartite), Corollary 3 can be used. K3,3 has six vertices and nine edges. Because e = 9 and 2v − 4 = 8, Corollary 3 shows that K3,3 is nonplanar.
Homeomorphism (Kuratowski’s Theorem)
We have seen that K3,3 and K5 are not planar.
Clearly, a graph is not planar if it contains either of these two graphs as a subgraph. Surprisingly, all nonplanar graphs must contain a subgraph that can be obtained from K3,3 or K5 using certain permitted operations.
The graphs G1 = (V1, E1) and G2 = (V2, E2) are called homeomorphic if they can obtained from the same graph by a sequence of elementary subdivisions.
An elementary subdivision is an operation of removing an edge {u, v} and adding new vertex w together with edges {u, w} and {w, v}.
Example: Graphs G1,G2, and G3 in the figure shown below are homeomorphic because G2 dan G3 can be obtained from G1 using elementary subdivision.
Theorema 2. A graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,3 or K5.
Example
Determine whether the graph G below is planar.
Homeomorphism & Planar Graph
A graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,3 or K5.
Example
G has a subgraph H homeomorphic to K5. Hence G is nonplanar.
Posting Komentar