Beranda > perguruan tinggi > Rumus Euler pada Teori Graph (Graph Planar)

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.

 

Tulisan Terbaru :

Kategori:perguruan tinggi
  1. irfan bachtiar
    9 Mei 2012 pukul 12:45 PM

    makasih buat yang bilangan prima, sangat membantu..

    • 30 Mei 2012 pukul 8:37 AM

      software untuk bilangan prima sudah masuk pada versi 2.0.. . Silahkan didownload.. . gratis.. mungkin nanti bisa mencari bilangan prima sampai jutaan

  2. Hanis Joko Marsono
    25 Maret 2012 pukul 4:43 PM

    mumet tenan

  1. No trackbacks yet.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: