Matematika Diskrit : Graf Dual

Graf Dual

Untuk setiap graf bidang G, kita dapat membuat graf dual G* dengan cara sebagai berikut:

  1. Setiap wilayah atau muka f dinyatakan sebagai sebuah simpul v*, termasuk wilayah luar.
  2. Tariklah sebuah sisi e* dari sebuah simpul v1* ke simpul v2* melewati sisi e pada graf asal.
  3. Jika sisi e pada salah satu simpulnya berderajat satu, maka sisi e* adalah berupa sisi gelang.

Sebuah graf mempunyai dual hanya jika graf tersebut planar. Sebuah graf planar G mempunyai dual yang unik hanya jika representasi bidangnya unik. Salah satu aplikasi graf dual yang penting adalah untuk merepresentasikan peta (map). Setiap peta pada bidang datar terdiri dari sejumlah wilayah (region). Wilayah pada peta dapat menyatakan suatu negara, provinsi, atau kabupaten. Tiap wilayah pada peta dinyatakan sebagai sebuah simpul, sedangkan sisi menyatakan bahwa dua wilayah berbatasan langsung (bertetangga).

sumber: Matematika Diskrit Edisi 3 (Rinaldi Munir)


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Graf, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up