Graph Dual

Definisi 4.5.1. Graph Dual:

Misalkan G graph bidang konstruksi graph sebuah graph G* sedemikian hingga:

(i) Setiap titik G* berkorespondensi dengan sebuah muka dari G.

(ii) Jika sebuah sisi c membatasi muka f₁ dan f₂ di G maka titik-titik G* yang berkorespondensi dengan f₁ dan f₂ dihubungkan dengan sebuah susu.

Graph G* yang dikonstruksi seperti ini disebut graph dual dari G (graph sejodoh) dari G.

Contoh 1:

Graph G pada gambar tersebut yang digambar "tebal", sedangkan dual dari G(G*) adalah graph yang digambar dengan garis putus-putus.

Berdasarkan uraain di atas, terdapat korespondensi satu-satu antara unsur-unsur graph G dan G* sebagai berikut:

• Sebuah muka G berkorespondensi dengan sebuah titik G* akibatnya |F(G)| = |F(G*)|
• Sebuah muka G berkorespondensi dengan sebuah sisi G* akibatnya |E(G)| = |E(G*)|
• Sebuah muka berderajat k di G berkorespondensi dengan sebuah titik berderajat k di G* sehingga   (dengan catatan G tidak memuat loop dan titik berderajat satu)
• Sebuah sisi yang terkait dengan sebuah titik yang berderajat satu di G, berkorespondensi dengan sebuah gelung (loop) di G*
• Sebuah titik berderajat dua di G, berkorespondensi dengan sepasang sisi rangkap di G

Jika G dan H adalah dua graph planar yang isomordik, maka belum tentu graph G* dan graph H* isomorfik.

Contoh 2:

Perhatikan bahwa G* memuat sebuah titik berderajat 5, sedangkan H* tidak memuat titik berderajat 5. Jadi G* dan H* tidak isomorfik.

Definisi 4.5.2 : Sebuah graph planar yang isomorfik dengan dualnya disebut graph dual diri (self deal graph).

Contoh 3:

Hubungan antara banyaknya sisi dan banyaknya titik dari sebuah graph dual diri dapat dilihat pada teorema berikut:

Teorema 4.5.1 Jika G* adalah dual diri graph planar G dan G ≡ G* maka:

Bukti:

Karena G ≡ G* maka G terhubung, karena G graph planar dan terhubung maka menurut teorema Euler berlaku:

Karena G* adalah dual diri graph G, maka :

Karena G isomorfik dengan G* (G ≡ G*) maka:

Persamaan (3) dan (2) disubstitusikan ke persamaan (1) maka diperoleh:

Cara membuat Dual Graf:

1. Pada setiap wilayah atau muka (face) f di G, dibuat sebuah simpul v* yang merupakan simpul untuk G.
2.  Untuk setiap sisi e di G, ditarik sisi e* (yang menjadi sisi untuk G*) yang memotong sisi e tersebut. Sisi e* menghubungkan dua buah simpul v₁* dan v₂* (simpul-simpul di G*) yang berada di dalam muka f₁ dan f₂  yang dipisahkan oleh sisi e di G. untuk sisi e yang salah satu simpulnya merupakan simpul berderajat 1 (jadi, sisi e seluruhnya terdapat di dalam sebuah muka), maka sisi e* adalah berupa sisi gelung.

Misalkan kita mempunyai sebuah graf planar G yang direpresentasikan sebagai graf bidang. Kita dapat membuat suatu graf bidang G*yang secara geometri merupakan dual dari graf tersebut dengan cara:

• Pada setiap wilayah atau muka (face) f di G, buatlah sebuah simpul v* yang merupakan simpul untuk G*
• Untuk setiap sisi e di G, tariklah sisi e* yang memotong sisi e tersebut

Graf yang terbentuk dengan cara penggambaran demikian disebut graf dual (dual geometri) dari graf G.