soal perhitungan graf

1. Diberikan gambar sebuah graf seperti di bawah ini.


a) Tunjukkan dengan ketidaksamaan Euler bahwa graf tersebut tidak planar.

(b) Tunjukkan dengan Teorema Kuratowski bahwa graf tersebut tidak planar.
Jawab :

(a). Dengan ketidaksamaan euler
jika menggunakan rumus ketidaksamaa euler e ≤ 3n – 6 maka akan terlihat bahwa graf memenuhi ketidaksamaan tersebut (padahal graf tidak planar)
e ≤ 3n – 6
15 ≤ 3 * 8 – 6
15 ≤ 24 – 6
15 ≤ 18
untuk menunjukkan bahwa graf tidak planar kita membuat asumsi baru bahwa setiap daerah pada graf planar dibatasi oleh paling sedikit 4 buah sisi . Dengan demikian total banyaknya sisi lebih besar atau sama dengan 4f. Tetapi karena suatu sisi berada pada batas paling banyak 2 wilayah maka total banyaknya sisi lebih kecil atau sama dengan 2e. Jadi :
2e ≤ 4f
dengan rumus euler menjadi ketidaksamaan
e ≤ 2n – 4
15 ≤ 2 * 8 – 4
15 ≤ 16 – 4
15 ≤ 12
terbukti

(b). Dengan teorema kuratowski
dapat dibuktikan bahwa graf tersebut mengandung upagraf yang homeomorfik dengan graf K3,3 atau K5.

G

G1 adalah upagraf
dari G

G2 yang isomorfik dengan G1

G2 homeomorfik dengan K5 (dengan membuang simpul A dan C yang berderajat