Teori Grafik - Isomorfisme
Sebuah grafik bisa ada dalam berbagai bentuk yang memiliki jumlah simpul, tepi, dan juga konektivitas tepi yang sama. Grafik semacam itu disebut grafik isomorfik. Perhatikan bahwa kami memberi label pada grafik dalam bab ini terutama untuk tujuan merujuk dan mengenalinya satu sama lain.
Grafik Isomorfik
Dua graf G 1 dan G 2 dikatakan isomorfik jika -
Jumlah komponennya (simpul dan tepi) sama.
Konektivitas edge mereka dipertahankan.
Note- Singkatnya, dari dua grafik isomorfik, yang satu adalah versi tweak dari yang lain. Grafik yang tidak berlabel juga dapat dianggap sebagai grafik isomorfik.
There exists a function ‘f’ from vertices of G1 to vertices of G2
[f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the
edge {f(U), f(V)} ∈ G2, then G1 ≡ G2.Note
Jika G 1 ≡ G 2 maka -
| V (G 1 ) | = | V (G 2 ) |
| E (G 1 ) | = | E (G 2 ) |
Urutan derajat G 1 dan G 2 sama.
Jika simpul {V 1 , V 2 , .. Vk} membentuk siklus dengan panjang K dalam G 1 , maka simpul {f (V 1 ), f (V 2 ),… f (Vk)} harus membentuk sebuah siklus dengan panjang K di G 2 .
Semua kondisi di atas diperlukan agar grafik G 1 dan G 2 menjadi isomorfik, tetapi tidak cukup untuk membuktikan bahwa grafik tersebut isomorfik.
(G 1 ≡ G 2 ) jika dan hanya jika (G 1 - ≡ G 2 -) dimana G 1 dan G 2 adalah grafik sederhana.
(G 1 ≡ G 2 ) jika matriks ketetanggaan G 1 dan G 2 sama.
(G 1 ≡ G 2 ) jika dan hanya jika subgrafik yang sesuai dari G 1 dan G 2 (diperoleh dengan menghapus beberapa simpul di G1 dan citranya di grafik G 2 ) bersifat isomorfik.
Example
Manakah dari grafik berikut yang isomorfik?
Pada graf G 3 , simpul 'w' hanya berderajat 3, sedangkan semua simpul graf lainnya berderajat 2. Jadi G3 tidak isomorfik terhadap G 1 atau G 2 .
Mengambil pelengkap G 1 dan G 2 , Anda memiliki -
Di sini, (G 1 - ≡ G 2 -), maka (G 1 ≡ G 2 ).
Grafik Planar
Sebuah graf 'G' dikatakan planar jika dapat digambar pada sebuah bidang atau bulatan sehingga tidak ada dua sisi yang saling bersilangan pada titik non-simpul.
Example
Wilayah
Setiap grafik planar membagi bidang menjadi area terhubung yang disebut region.
Example
Derajat wilayah yang dibatasi r = deg(r) = Jumlah tepi yang menutupi daerah r.
deg(1) = 3
deg(2) = 4
deg(3) = 4
deg(4) = 3
deg(5) = 8
Derajat wilayah tak terbatas r = deg(r) = Jumlah tepi yang menutupi daerah r.
deg(R1) = 4
deg(R2) = 6Dalam grafik planar, properti berikut berlaku -
Dalam grafik planar dengan simpul 'n', jumlah derajat dari semua simpul adalah -
Berdasarkan Sum of Degrees of Regions/ Teorema, dalam grafik planar dengan daerah 'n', Jumlah derajat daerah adalah -
Berdasarkan teorema di atas, Anda dapat menarik kesimpulan berikut -
Dalam grafik planar,
Jika derajat tiap daerah adalah K, maka jumlah derajat daerah adalah -
Jika derajat setiap daerah minimal K (≥ K), maka
Jika derajat tiap daerah paling banyak K (≤ K), maka
Note - Diasumsikan bahwa semua daerah memiliki derajat yang sama.
Berdasarkan Euler’s Formulae pada grafik planar,
Jika graf 'G' adalah planar yang terhubung, maka
Jika grafik planar dengan komponen 'K', maka
Dimana, | V | adalah jumlah simpul, | E | adalah jumlah sisi, dan | R | adalah jumlah wilayah.
Ketimpangan Edge Vertex
Jika 'G' adalah grafik planar yang terhubung dengan derajat tiap daerah minimal 'K' maka,
| E | ≤ k / (k-2) {| v | - 2}
Anda tahu, | V | + | R | = | E | + 2
K. | R | ≤ 2 | E |
K (| E | - | V | + 2) ≤ 2 | E |
(K - 2) | E | ≤ K (| V | - 2)
| E | ≤ k / (k-2) {| v | - 2}
Jika 'G' adalah grafik planar terhubung sederhana, maka
|E| ≤ 3|V| − 6
|R| ≤ 2|V| − 4Ada setidaknya satu simpul V • ∈ G, sehingga derajat (V) ≤ 5.
Jika 'G' adalah grafik planar terhubung sederhana (dengan setidaknya 2 sisi) dan tanpa segitiga, maka
|E| ≤ {2|V| – 4}Teorema Kuratowski
Grafik 'G' adalah non-planar jika dan hanya jika 'G' memiliki subgraf yang bersifat homeomorfik terhadap K 5 atau K 3,3 .
Homomorfisme
Dua graf G 1 dan G 2 dikatakan homomorfik, jika masing-masing graf tersebut dapat diperoleh dari graf yang sama 'G' dengan membagi beberapa sisi G dengan lebih banyak simpul. Lihat contoh berikut -
Bagilah tepi 'rs' menjadi dua sisi dengan menambahkan satu simpul.
Grafik yang ditunjukkan di bawah ini homomorfik dengan grafik pertama.
Jika G 1 isomorfik terhadap G 2 , maka G adalah homeomorfik bagi G2 tetapi kebalikannya tidak harus benar.
Grafik apa pun dengan 4 simpul atau kurang adalah planar.
Grafik apa pun dengan 8 tepi atau kurang adalah planar.
Grafik lengkap K n adalah planar jika dan hanya jika n ≤ 4.
Graf bipartit lengkap K m, n adalah planar jika dan hanya jika m ≤ 2 atau n ≤ 2.
Grafik non-planar sederhana dengan jumlah simpul minimum adalah graf lengkap K 5 .
Grafik non-planar sederhana dengan jumlah sisi minimum adalah K 3, 3 .
Grafik polihedral
Graf planar terhubung sederhana disebut graf polihedral jika derajat tiap simpul ≥ 3, yaitu derajat (V) ≥ 3 ∀ V ∈ G.
3 | V | ≤ 2 | E |
3 | R | ≤ 2 | E |