-->

Rumus Euler pada Teori Graph (Graph Planar)

Apakah pembaca ingat, bagaimana rumus euler yang terdapat pada bangun ruang sisi datar.
S+T-R=2


Dengan S adalah sisi, T adalah titik sudut dan R adalah rusuk.
atau ditulis :
Sisi + Titik Sudut – Rusuk = 2
Rumus tersebut berlaku untuk bangun ruang sisi datar. Tentu saja bukan tabung, kerucut atau bola.


Pada Graph, pada bagian Graph Planar, muncul lagi rumus euler, yaitu
Titik + Daerah – Sisi = 2




Sebelum kembali ke rumus euler, kita singgung sedikit mengenai graph planar.
Apa itu grapah planar? yaitu suatu graph yang bisa digambarkan menjadi suatu graph yang sisinya tidak ada yang bertumpukan.


Perhatikan gambar berikut :
  

 
Perhatikan Gambar. G adalah graph. Perhatikan bahwa sisi eb dan sisi ac pada gambar tersebut bertumpukan/berpotongan (tanda panah biru).
Suatu graph disebut graph planar jika graph tersebut bisa digambarkan dengan tidak ada sisi yang bertumpukan/berpotongan.
Graph G adalah graph planar, karena bisa digambarkan menjadi gambar yang dibawahnya. Tidak ada sisi yang bertumpukan.


Apakah semua graph itu merupakan graph planar? Tidak.
Graph berikut ini bukan merupakan graph planar. Coba saja dibuat gambar graph sehingga tidak ada sisi yang bertumpukan/berpotongan.
  

 
Sudah selesai dengan graph planar. sekarang kita ke daerah dalam graph planar.
Perhatikan gambar :





Gambar tersebut adalah gambar graph planar. Setiap graph planar pasti memiliki faces (saya di sini mengartikan “daerah”). Misalnya daerah Q, dibatasi oleh sisi ec, eb dan bc.
Daerah T dibatasi oleh sisi ae, ed dan da. Dan daerah-daerah yang lain. Dan ada satu daerah yang sangat besar, yaitu daerah terluar, yaitu daerah U. Kita mengatakan bahwa daerah U ini dibatasi oleh sisi ad, dc dan ca.


Rumus Euler pada Graph Planar
Banyak Titik + Banyak Daerah – Banyak Sisi = 2


Pada graph di atas.
Banyak Titik = 5
Banyak Daerah = 6
Banyak Sisi = 9
Hubungannya (Rumus Eulernya pun berlaku), yaitu : 5 + 6 – 9 = 2


Coba saja untuk graph planar yang lainnya. Silahkan mencoba.


Untuk Bukti rumus ini, akan diberikan langkah-langkahnya, yaitu :


Pertama, kita perhatikan Tree (pohon), yabng pasti memiliki 1 daerah, n titik dan n-1 sisi.
Rumus eulernya pun berlaku, yaitu : n + 1-(n-1)=2
Dengan begitu, kita sudah menunjukkan bahwa untuk sebarang tree, maka berlaku rumus euler.


Untuk sebarang graph,
Ambil/Buat Spanning Tree dari sebarang graph tersebut. Tentu saja akan berlaku rumus euler pada sebarang spanning tree tersebut.
Setelah itu tambahkan 1 sisi (sisi yang ditambahkan adalah sisi sehingga nanti terbentuk graph semula).
Penambahan satu sisi, mengakibatkan menambahnya satu daerah. Padahal pada rumus euler, antara sisi dan daerah itu saling mengurangi. Jadi, Rumus Euler pada spanning tree yang ditambahkan satu sisi tersebut itu pun masih berlaku.
Tambahkan sisi selanjutnya, dan seterusnya sampai didapatkan graph sebelumnya (graph awal). Dan tentu saja rumus euler masih berlaku.


‘penambahan satu sisi akan menyebabkan bertambahnya satu daerah, ini tidak akan mengubah rumus eulernya’


Akhirnya, Bapak Euler sangatlah hebat. Ternyata rumus eulernya itu bukan hanya pada bangun ruang sisi datar saja. Tetapi pada graph juga berlaku rumus tersebut.
Angka 2 angkanya euler.

0 Response to "Rumus Euler pada Teori Graph (Graph Planar)"

Posting Komentar

Harap komentar yang bijak!!!

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel