Struktur Diskrit : Latihan Graf Planar
1. Can five houses be connected to two utilities without connections crossing ?
2. Can five houses be connected to three utilities without connections crossing ?
3. Draw the given planar graphs without any crossings !
4. For each given graph, determine whether it is planar. If so, draw it so that no edges cross !
5.
- Suppose that a connected planar graph has eight vertices, each of degree three. Into how many regions is the plane divided by a planar representation of this graph?
- Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph?
- Suppose that a connected planar graph has 30 edges. If a planar representation of this graph divides the plane into 20 regions, how many vertices does this graph have?
6. For each given graph, determine whether it is homeomorphic to K3,3!
7. For each given graph, use Kuratowski’s theorem to determine whether it is planar.
