Experience Matematika

  KETEBALAN DARI SEBUAH GRAPH Definisi 4.41: Ketebalan (thickness) dari sebuah graph G adalah minimum dari bilangan yang menyatakan banyaknya graph bagian planar dari G yang gabungannya sama dengan G. Ketebalan sebuah graph G dinotasikan dengan  Definisi 4.42 Gabungan dari dua buah graph G dan H, ditulis   adalah graph yang himpunan titiknya   dan hmpunan sisinya  Contoh:  Contoh:  Catatan:   Setiap graph planar G mempunyai ketebalan 1. Menentukan nilai untuk sembarang graph G, sampai dewasa ini belum ada formula eksak untuk  kecuali mungkin untuk graph-graph G tertentu. Tetapi, dengan menggunakan teorema sebelumnya, dengan mudah dapat ditentukan batas bawah dari , untuk sembarang graph sederhana G. Teorema 4.4.1 : jika G sederhana dengan maka : Catatan:

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 1 dan f 2 di G maka titik-titik G* yang berkorespondensi dengan f 1 dan f 2 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) ...

TEOREMA KURATOWSKI (Kashimir Kuratowski, Polandia) untuk menentukan keplanaran suatu graf. 1.        Teorema   Kuratowski :      “ Graf  G bersifat  planar    jika  dan  hanya  jika ia tidak  mengandung  subgraf yang  sama   dengan   salah  satu  graf  kuratowski  atau  homomorfis  dengan   salah  satunya , atau Sebuah Graf G non Planar jika dan hanya jika G memuat sebuah graph bagian G yang hemeomorfik dengan graph K 3,3 atau K 5 “ 2.       Sifat  GRAF Kuratowski adalah : a)       Kedua graf  Kuratowski adalah graf   teratur. b)       K edua graf  kuratowski  graf   non-planar . c)       P enghapusan sisi atau simpul dari graf  kuratowski   menyebabkan  menjadi  graf pl...