Za spodnje grafe ugotovi, ali so ravninski.
graph G1 {
rankdir=LR
a -- b -- c -- d -- h --g -- f
a -- e -- f
e -- b -- f -- c -- g -- d
a -- f
b -- g
c -- h
}
Graf je ravninski.
graph G2 {
rankdir=LR
node [style=filled]
a [color=red]
e [color=red]
d [color=red]
h [color=red]
b [color=green]
c [color=blue]
f [color=yellow]
g [color=magenta]
a -- b -- c -- d
d -- h [color=red]
h -- g -- f
a -- e [color=red]
e -- f
e -- b -- f -- c -- g -- d
a -- f
b -- g
c -- h
a -- d [color=red]
}
Graf ni ravninski, ima minor ${K_5}$:
graph G2kontrakt {
eadh -- b
eadh -- c
eadh -- f
eadh -- g
b -- c
b -- f
b -- g
c -- f
c -- g
f -- g
}
graph G3 {
rankdir=LR
node [style=filled]
a [color=red]
b [color=red]
e [color=green]
f [color=green]
c [color=blue]
d [color=cyan]
g [color=magenta]
h [color=yellow]
a -- b [color=red]
b -- c -- d -- e
e -- f [color=green]
f -- g -- h -- a
a -- e
b -- f
c -- g
d -- h
}
Graf ni ravninski, ima minor ${K_{3, 3}}$:
graph G3kontrkat {
ab -- c
ab -- h
ab -- ef
d -- c
d -- h
d -- ef
g -- c
g -- h
g -- ef
}
Pokaži, da ima povezan kubičen graf v ravnini, pri katerem so vsa lica petkotniki ali šestkotniki, natanko $12$ petkotnikov.
Naj bo $G$ enostaven graf, ki ima $11$ vozlišč. Pokaži, da potem $G$ ni ravninski ali pa njegov komplement ni ravninski.
Naj bo $G$ regularen graf stopnje $p \ge 3$, vložen v ravnino tako, da imajo vsa lica enako število povezav $q \ge 3$ na robu. Kakšna sta lahko $p$ in $q$?
Za grafe na spodnji sliki poišči njihovo barvnost.
graph G1 {
rankdir=LR
node [style=filled]
a [color=red]
b [color=green]
c [color=blue]
d [color=blue]
e [color=green]
a -- b
a -- c
b -- c
b -- d
c -- e
d -- e
}
Barvnost: 3 (imamo lih cikel, našli smo 3-barvanje)
graph G2 {
rankdir=LR
node [style=filled]
a [color=red]
b [color=green]
c [color=green]
d [color=green]
h [color=green]
e [color=red]
f [color=red]
g [color=red]
k [color=red]
i [color=green]
j [color=green]
d -- e
e -- b
e -- i
d -- a
b -- a
b -- f
i -- f
i -- k
d -- k
a -- c
f -- c
f -- j
k -- j
c -- g
j -- g
a -- h
k -- h
g -- h
}
Barvnost: 2 (graf je dvodelen)
graph G3 {
rankdir=LR
node [style=filled]
h -- e -- b -- a
b -- c
b -- d
a -- c
a -- d
c -- d
e -- f
e -- g
c -- f
d -- g
f -- g
h -- i
h -- j
f -- i
g -- j
i -- j
a [color=red]
c [color=green]
d [color=blue]
b [color=magenta]
e [color=red]
f [color=blue]
g [color=green]
h [color=magenta]
i [color=red]
j [color=blue]
}
Barvnost je 4 (ima 4-kliko, našli smo 4-barvanje)
graph G4 {
node [style=filled]
a -- c
a -- d
b -- c
b -- d
a -- e
a -- f
b -- g
e -- g
f -- g
c -- h
g -- h
d -- i
g -- i
c -- j
e -- j
i -- j
d -- k
f -- k
h -- k
j -- k
}