BAB I PENDAHULUAN 1.1 Latar Belakang Masalah
Seiring perkembangan zaman, maka perkembangan ilmu pengetahuan berkembang pesat, begitu pula dengan ilmu matematika. Salah satu cabang ilmu matematika yang memiliki banyak terapan sampai saat ini adalah teori graf. Teori graf dikenalkan sejak tahun 1736 dan berkembang pesat pada tahun 1920-an. Teori graf memiliki banyak terapan dalam bidang ilmu komputer, kimia, riset operasi dan tehnik kelistrikan (Johnsonbaugh, 2001). Suatu graf menyatakan himpunan titik yang disebut vertex yang dihubungkan dengan garis yang disebut edge. Banyak sistem dapat dipandang sebagai graf dimana obyek dapat diangap sebagai vertex dan hubungan diantara obyek dinyatakan dengan edge. Oleh karena itu graf dapat digunakan untuk menyatakan jaringan komplek yang terdiri dari komponen-komponan yang berhubungan. Contoh sederhana dari graf adalah peta jalan raya. Kota-kota dalam peta tersebut digambarkan sebagai vertex dan jalan yang menghubungkan kotakota adalah edge (Chartrand dan Oellerman, 1993). Teori extremal graph merupakan cabang dari teori graf. Dalam teori extremal graph yang menarik adalah relasi antara invariant graf, seperti order, size, connectivity, degree minimum, degree maksimum, chromatic number dan diameter, dan juga nilai dari invariant yang memastikan bahwa graf pasti mempunyai sifat (property) yang ditentukan. Permasalahan dalam teori extremal graph meliputi, jika diberikan sifat P dan invariant µ pada kelas graf H, ditentukan paling sedikit nilai m untuk setiap graf G di H dengan µ (G) > m memiliki sifat P. Graf G dalam H tanpa sifat P dengan µ (G) = m disebut extremal graph. Contoh sederhana extremal graph adalah setiap graf dengan order n dan size paling sedikit n memuat suatu cycle, maka extremal graphnya adalah tree dengan order n (Bollobás, 1978).
1
Pada skripsi ini dibahas mengenai pembentukan extremal graph pada graf G dan struktur extremal graph pada subgraf lengkap.
1.2 Perumusan Masalah
Berdasarkan latar belakang penulisan skripsi ini, penulis merumuskan beberapa masalah sebagai berikut 1. bagaimana membentuk extremal graph pada graf G ? 2. bagaimana struktur extremal graph pada subgraf lengkap?
1.3 Batasan Masalah
Batasan-batasan masalah dalam penulisaan skripsi ini adalah 1. kajian secara teori, 2. pada graf sederhana dan tak berarah dengan invariant graf adalah size.
1.4 Tujuan Penulisan
Tujuan dari penulisan skripsi ini adalah 1. memperkenalkan pembentukan extremal graph pada suatu graf G, 2. memperkenalkan struktur extremal graph pada subgraf lengkap.
1.5 Manfaaat Penulisan
Manfaat dari penulisan skripsi ini adalah 1. menambah wawasan tentang teori graf khususnya teori extremal graph, 2. mengembangkan ilmu yang berhubungan dengan graf dan extremal graph, 3. mengetahui struktur extremal graph pada subgraf lengkap.
2
BAB II LANDASAN TEORI
2.1 Tinjauan Pustaka
Untuk dapat menyelesaikan masalah yang telah dirumuskan, maka diperlukan teori-teori yang mendasari penulisan skripsi ini. Pada bab ini memuat beberapa definisi teori graf dan konsep dasar mengenai extremal graph.
2.1.1 Graf
Definisi 2.1.1 (Johnsonbaugh, 2001) Suatu graf G (atau graf tak berarah) terdiri dari himpunan vertex tidak kosong V(G) = {v1, v2, …, vn} dan himpunan edge (boleh kosong) E(G) = {e1, e2, …, en} sedemikian sehingga setiap edge e∈ E(G) menghubungkan pasangan vertex tak terurut dari anggota-anggota V(G). Jika edge e menghubungkan vertex vi dan vj , maka ditulis e = (vi, vj) atau e = (vj, vi). Gambar 2.1 adalah contoh graf G dengan 4 vertex dan 5 edge. Graf G terdiri dari himpunan vertex V(G) = {v1, v2 , v3, v4} dan himpunan edge E(G) = {e1, e2, e3, e4, e5}.
v2 e1
e2 e5
v1 e4
v3 e3
v4 Gambar 2.1 Graf G
3
Definisi 2.1.2 (Johnsonbaugh, 2001) Sebuah edge e = (vi, vj) dalam sebuah graf G yang menghubungkan pasangan vertex vi dan vj dikatakan incident terhadap vi dan vj. Vertex vi dan vj juga dikatakan incident terhadap e, sedangkan vi, vj merupakan vertex-vertex yang adjacent.
Gambar 2.2 merupakan contoh incident edge dan adjacent vertex dari graf G. Pada Gambar 2.2 edge e incident terhadap vertex v1 dan v2, sedangkan vertex v1 adjacent dengan v2.
v1
e
v2
Gambar 2.2 Contoh incident edge dan adjacent vertex dari graf G.
Definisi 2.1.3 (Chartrand dan Oellerman, 1993) Degree suatu vertex vi dari graf G atau deg Gv adalah banyaknya vertex yang adjacent pada vi atau banyaknya edge-edge yang incident dengan vi, jika G mempunyai order n maka 0 ≤ degGv ≤ n – 1. Degree terbesar dari suatu vertex dalam suatu graf G disebut degree maksimum ∆(G) dan degree terkecil suatu vertex dalam suatu graf G disebut degree minimum δ(G). Gambar 2.3 adalah contoh degree suatu vertex dari graf G dengan himpunan vertex V(G) = {v1, v2, v3, v4, v5}. degGv1 = 1 v1
v3
degGv2 = 3 degGv3 = 2 v5
degGv4 = 2 degGv5 = 0
v2
v4
∆(G) = 3 δ(G) = 0
Gambar 2.3 Degree vertex dari graf G
4
Definisi 2.1.4 (Johnsonbaugh, 2001) Suatu graf dikatakan sebagai graf sederhana (simple graph) jika tidak terdapat loop atau parallel edge. Loop adalah edge yang incident ke vertex tunggal. Dua edge atau lebih yang terhubung dengan pasangan vertex yang sama disebut parallel edge (edge ganda).
Pada Gambar 2.4 di bawah ini graf G1 merupakan contoh dari graf yang memuat parallel edge dan loop sedangkan graf G2 merupakan graf sederhana. e3
v2
G1 :
v2
v3
v1
v4
G2 :
e1 e2
v3
v1
Gambar 2.4 Graf sederhana dan graf tidak sederhana
Gambar 2.4 memperlihatkan graf G1 bukan graf sederhana karena memuat loop seperti edge e3 = (v2, v2) dan parallel edge yaitu edge e1 dan e2 keduanya menghubungkan pasangan vertex v1, v2. Graf G2 merupakan graf sederhana, karena tidak memuat parallel edge atau loop.
Definisi 2.1.5 (Bollobás, 1978) Banyaknya vertex dalam graf G disebut order G, sedangkan banyaknya edge dalam graf G disebut size G. Dalam suatu graf G, order dinotasikan dengan |V(G)|, υ(G) atau |G| dan size dinotasikan dengan |E(G)|, ε(G) atau e(G). Gambar 2.5 menunjukkan graf G dengan himpunan vertex V(G) = {v1, v2 , v3, v4} dan himpunan edge E(G) = {e1, e2, e3, e4} mempunyai order 4 dan size 4.
5
v1 e1 v2
e4
e2
e3
|V(G)| = 4 v4
|E(G)| = 4
v3 Gambar 2.5 Order dan size dari graf G
Definisi 2.1.6 (Chartrand dan Oellerman, 1993) Walk dalam graf G adalah deret bergantian vertex dan edge, v0, e1, v1, e2, . . ., vn
– 1,
en, vn (n ≥ 0), yang
dimulai dan diakhiri dengan vertex, dimana ei = (vi – 1, vi) untuk i = 1, 2, . . . , n. Walk dalam graf G dapat dinotasikan dengan v0, v1, . . ., vn – 1, vn, karena setiap vertex yang muncul dalam walk menentukan edge dalam walk. Trail adalah walk yang edgenya tidak diulang. Path adalah walk dimana tidak ada vertex yang diulang.
Gambar
2.6
merupakan
contoh
G
graf
dengan
himpunan
vertex
V(G) = {v1, v2, v3, v4, v5} dan himpunan edge E(G) = {e1, e2, e3, e4, e5, e6, e7} yang memuat walk, trail dan path. Salah satu contoh walk, trail dan path dari Gambar 2.6 adalah walk
: v1, v2, v5, v3, v1, v2,, v4,
trail
: v3, v5, v2, v1, v5, v4,
path
: v1, v3, v5, v2, v4.
v1
e1 e2
e4
v2 e3
v5
e5
e6
e7
v3
v4
Gambar 2.6 Graf G yang memuat walk, trail dan path
6
Definisi 2.1.7 (Chartrand dan Oellerman, 1993) Graf G disebut graf terhubung (connected graph) jika terdapat paling tidak satu path antara sembarang vertex vi dan vj. Jika tidak demikian, maka graf G dikatakan tidak terhubung (disconnected graph).
Gambar 2.7 graf G1 merupakan contoh graf terhubung sedangkan graf G2 adalah graf tidak terhubung.
G1 :
G2 :
Gambar 2.7 Contoh graf terhubung dan graf tak terhubung
Definisi 2.1.8 (Chartrand dan Oellerman, 1993) Sebuah cycle adalah walk v0, v1, . . . , vn dengan n ≥ 3, v0 = vn dan vertex v1, v2, . . . , vn berbeda.
Cycle dengan order n dinotasikan dengan Cn. Cycle dengan order 3 atau C3 disebut dengan triangle. Gambar 2.8 merupakan contoh cycle dengan 3 ≤ n ≤ 5.
Gambar 2.8 Cycle Cn, 3 ≤ n ≤ 5
Definisi 2.1.9 (Bollobás, 1978) Tree adalah graf terhubung yang tidak memuat cycle.
7
Tree dinotasikan dengan T. Gambar 2.9 merupakan dua contoh tree yaitu T1 dengan himpunan vartex V(T1) = {v1, v2, v3, v4} dan T2 dengan himpunan vertex V(T2) = {v1, v2, v3, v4, v5, v6}. v1
v2
T1 :
v2 T2 :
v5 v1
v4 v6
v3
v4
v3
Gambar 2.9 Tree
Definisi 2.1.10 (Bollobás, 1978) Graf lengkap (complete graph) adalah graf G dengan order r yang setiap vertexnya adjacent dengan vertex yang lain. Dengan r kata lain graf lengkap adalah graf dengan order r dan size . 2 Graf lengkap dengan order r dinotasikan dengan Kr. Gambar 2.10 merupakan contoh graf lengkap dengan 1 ≤ r ≤ 5.
K1
K2
K3
K4
Gambar 2.10 Graf lengkap Kr, 1 ≤ r ≤ 5
8
K5
Defnisi 2.1.11 (Chartrand dan Lesniak, 1979) Dua buah graf G1 dan G2 adalah isomorfik jika terdapat pemetaan satu-satu φ dari V(G1) dipetakan ke V(G2) sedemikian sehingga (vi,vj)∈ E(G1) jika dan hanya jika (φ(vi),φ(vj))∈ E(G2). Jika graf G1 dan G2 adalah isomorfik, maka ditulis G1 ≅ G2. Gambar 2.11 merupakan contoh graf isomorfik dan graf yang tidak isomorfik. Graf G1 dan G2 pada Gambar 2.11 adalah isomorfik ketika fungsi
φ :V(G1)→V(G2) didefinisikan dengan φ(v1) = v5, φ(v2) = v6, φ(v3) = v7, φ(v4) = v8 adalah isomorphism. Graf G1 dan G3 tidak isomorfik, karena vertex-vertex di G3 mempunyai degree dua, sedangkan vertex-vertex di G1 mempunyai degree tiga.
v3
v8
G1 :
v7
G2 :
v12
v11
v9
v10
G3 :
v4
v1
v2
v5
v6
Gambar 2.11 Contoh graf isomorfik dan graf tidak isomorfik
Definisi 2.1.12 (Chartrand dan Oellerman, 1993) Graf H adalah subgraf dari graf G jikaV(H) ⊆ V(G) dan E(H) ⊆ E(G). Gambar 2.12 adalah contoh subgraf G. Graf H adalah subgraf dari graf G karena V(H) ⊆ V (G) dan E(H) ⊆ E(G).
v2
e2
G:
v1
e3 e1
e9
v5 e7
v3
v1
e8
v4
e10
v8
H:
e11
e6
e10
e11
e4 v6
e5
v7
Gambar 2.12 Contoh subgraf dari graf G
9
v6
e5
v7
Definisi 2.1.13 (Chartrand dan Oellerman, 1993) Jika V′ adalah himpunan tidak kosong dari vertex G, maka subgraph induced by V′ adalah maksimal subgraph dari G dengan himpunan vertex V′. Subgraph induced by V′ terdiri dari semua edge dari graf G yang terhubung dengan vertex di V′. Jika V′ adalah himpunan tidak kosong dari vertex G, subgraph induced by V′ dinotaskan dengan
atau G[V′]. Gambar 2.13 merupakan contoh induced subgraph dari graf G. Graf G1 dan G2 pada Gambar 2.13 adalah subgraf dari graf G. Graf G1 adalah induced subgraph dari graf G tetapi G2 bukan induced subgraph dari graf G karena edge (v1, v4)∈E(G) tetapi (v1, v4)∉E(G2). Jadi G1 = G[{v1, v2, v3, v5}].
v1
v2
v3
G:
v1
v2
G1 :
v4
v5
v6
v3
v1
v2
v3
G2 :
v5
v4
v5
Gambar 2.13 Contoh induced subgraph dan bukan induced subgraph dari graf G
Definisi 2.1.14 (Stechkin dan Baranov, 1995) Selisih dari dua himpunan X dan Y adalah himpunan dari semua anggota X yang bukan anggota Y. Dinotasikan X\Y, berarti X\Y = {x: x∈ X dan x∉ Y}. Misal V adalah himpunan vertex dari graf G dengan V = {v1, v2, v3, v4, v5} dan V′ = {v1, v2}, maka V\V′ = {v3, v4, v5}.
10
Definisi 2.1.15 (Chartrand dan Oellerman, 1993) Graf G adalah r – partite graph jika graf G dengan r ≥ 2 dan himpunan vertex V(G) dapat dipartisi ke r subhimpunan tak kosong V1, V2, . . . ,Vr sedemikian sehingga tidak ada edge dalam graf G yang menghubungkan vertex di dalam himpunan yang sama. Himpuan V1, V2, . . . ,Vr disebut himpunan partisi dari G.
Gambar 2.14 adalah 3 – partite graph dengan himpunan partisi V1 = {v1, v2}, V2 = {v3}, V3 = {v4, v5, v6}. v1
v2
v3
v4
v5
v6
Gambar 2.14 3 – partite graph
Definisi 2.1.16 (Chartrand dan Oellerman, 1993) Complete r – partite graph adalah r – partite graph dengan himpunan partisi V1, V2, . . . ,Vr, sedemikian sehingga setiap vertex dari Vi terhubung ke setiap vertex Vj, dengan 1≤ i< j≤ r. Jika |Vi| = ni, untuk i = 1, 2, . . . , r, maka G dinotasikan dengan K(n 1, n2, . . ., nr). Gambar 2.15 merupakan contoh complete r – partite graph dengan r = 3 dan r = 4.
11
v1
v2
K1,2,3 :
v1 v3
v4
v5
v2
K1,1,1,1 :
v6
v4
v3
Gambar 2.15 Contoh complete r – partite graph, r = 3, 4
Pada Gambar 2.15 K1, 2, 3 adalah complete 3 – partite graph dengan kelas vertex V1 = {v1}, V2 = {v2, v3} dan V3 = {v4, v5, v6}. K1,
1,
1,
1
adalah
complete 4 – partite graph dengan kelas vertex V1 = {v1}, V2 = {v2}, V3 = {v3}, V4 = {v4}.
Definisi 2.1.17 (Bollobás, 1978) Jarak antara dua vertex vi dan vj yang dinotasikan dengan d(vi, vj) adalah minimum panjang path antara vi dan vj. Diameter dari graf G adalah maksimum jarak antara dua vertex vi dan vj dalam graf G. Diameter dari graf G dinotasikan dengan diam G, berarti diam G = maks{d(vi, vj): vi, vj∈ G}. Gambar 2.16 adalah graf G dengan himpunan vertex V(G)= {v1, v2, v3} dan diameter dari graf G adalah satu.
v1 d(v1, v2) = 1 d(v1, v3) = 1 d(v2, v3) = 1 diam G = 1 v2
v3
Gambar 2.16 Contoh graf G dengan diameter satu
12
Definisi 2.1.18 (Bollobás, 1978) Pewarnaan vertex pada graf G adalah pemberian warna pada vertex sedemikian sehingga vertex yang adjacent diberi warna yang berbeda. Jika warna yang digunakan sebanyak k maka pewarnaannya disebut k-coloring. Jika terdapat k-coloring pada graf G maka graf G adalalah k-colorable. Chromatic number dari G adalah
χ(G) = min{k : G adalah k-colorable}. Gambar 2.17 adalah gambar graf G dengan himpunan vertex V(G)={v1, v2, v3, v4}. Chromatic number dari graf G adalah tiga, karena minimal warna yang digunakan pada graf G adalah 3 yaitu vertex v1 diwarnai merah, vertex v2, v3 diwarnai biru dan v4 diwarnai hijau. v1
v2
v3
v4
Gambar 2.17 Contoh graf G dengan chromatic number tiga
Definisi 2.1.19 (Harary, 1969) Invariant dari suatu graf adalah nilai yang berhubungan dengan graf G yang mempunyai nilai yang sama untuk graf apapun yang isomorfik dengan graf G. Invariant dari graf G dinotasikan dengan µ (G).
Contoh invariant graf G adalah order, size, degree maksimum, degree minimum, chromatic number dan diameter.
13
Teorema 2.1 (Chartrand dan Oellerman, 1993) Jika G adalah graf dengan order n dan size p dengan V(G) = {v1, v2, . . . , vn}, maka n
∑ deg i =1
G
vi = 2 p
Teorema 2.2 (Chartrand dan Oellerman, 1993) Tree dengan order n mempunyai size n – 1.
2.1.2 Extremal Graph Definisi 2.1.20 (Bollobás, 1978) jika diberikan sifat P dan invariant µ pada kelas graf H, ditentukan paling sedikit nilai m untuk setiap graf G dalam H dengan µ (G) > m memiliki sifat P. Graf G dalam H tanpa sifat P dengan
µ (G) = m disebut extremal graph. Setiap graf dengan order 4 dan size paling tidak 5 harus memuat K3. Extremal graphnya adalah graf dengan order 4 vertex dan size 4 dan tidak memuat K3. Jadi extremal graphnya adalah C4. Gambar 2.18 merupakan extremal graph pada graf yang memuat subgraf K3 . v1
v2
v4
v3
Gambar 2.18 Extremal graph (4, K3)
14
Definisi 2.1.21 (Bollobás, 1978) Turán graph Tr(n) adalah complete r – partite graph order n dengan size maksimal, dinotasikan size maksimal dengan tr(n). Kelas vertex dan size dari Turán graph adalah n n + 1 n + r − 1 n1 = , n 2 = , ..., n r = vertex, r r r n r n n + i n + j t r (n ) = − ∑ i = ∑ . 2 1 2 0≤ i < j < r r r Gambar 2.19 adalah contoh Turán graph T3(7) dengan n = 7 dan r = 3. Kelas vertex T3(7) adalah V1 = {v1, v2}, V2 = {v3, v4} dan V3 = {v5, v6, v7}dan t3(7) = 16.
v1
v3
v2
v4
v5
v6
v7
Gambar 2.19 Turán graph T3(7)
2.2 Kerangka Pemikiran
Berdasarkan tinjauan pustaka di atas dapat disusun suatu kerangka pemikiran untuk mengenalkan extremal graph. Dikenalkan extremal graph pada subgraf lengkap yaitu membentuk extremal graph tanpa memuat subgraf lengkap Kr, dengan menunjukkan bahwa setiap graf dengan n vertex dan size lebih besar dari tr – 1(n) harus memuat Kr subgraf lengkap dengan order r dan graf dengan n vertex dan size tr – 1(n) tidak memuat Kr adalah graf Tr – 1(n). Dalam penulisan skripsi ini, penulis memperkenalkan extremal graph pada subgraf lengkap dengan menggunakan pengertian yang dikenalkan oleh Bollobás [1978].
15
BAB III METODE PENELITIAN Metode yang digunakan dalam penulisan skripsi ini adalah studi literatur, yaitu metode penulisan dengan semua bahan diambil dari buku referensi, jurnal dan artikel. Definisi dan teorema yang terdapat di referensi dikaji ulang, kemudian digunakan dalam pembahasan yang telah dirumuskan. Langkah-langkah penulisan ini dimulai dengan mengenalkan extremal graph pada graf G, kemudian menggunakan pengertian extremal graph untuk membahas extremal graph pada subgraf lengkap. Untuk lebih jelasnya disajikan dalam bagan di bawah ini.
Buku referensi, jurnal dan artikel dikaji
Konsep dasar dan pengertian extremal graph
Pengertian Turán graph
Extremal graph pada subgraf lengkap
Gambar 3.1 Langkah-langkah penulisan
16
BAB IV PEMBAHASAN
Dalam pembahasan ini dikenalkan mengenai pembentukan extremal graph pada graf G dengan invariant graf adalah size. Selanjutnya dikenalkan juga struktur extremal graph pada graf lengkap.
4.1. Extremal Graph
Dalam bagian ini dibahas mengenai extremal graph yang dibatasi pada graf sederhana G yang memuat subgraf G1, dan invariant graf adalah size. Permasalahan extremal merupakan satu pokok bahasan dalam teori extremal graph. Permasalahan extremal dalam masalah ini dimulai dengan permasalahan extremal klasik yang telah dikenalkan oleh Turán. Permasalahan extremal tersebut adalah jika diberikan graf G1, ditentukan size maksimum ex(n; G1) pada graf G dengan order n yang tidak memuat G1 sebagai subgrafnya. Extremal graph pada graf G adalah suatu graf dengan order n dan size maksimum ex(n; G1) yang tidak memuat G1 sebagai subgrafnya. Setiap graf dengan order n dan size paling sedikit n memuat cycle, maka extremal graphnya adalah tree dengan order n. Gambar 4.1 merupakan extremal graph pada graf dengan order 5 yang memuat sebuah cycle.
Gambar 4.1 Extremal Graph (5, C)
17
Setiap graf G dengan order n yang memuat triangle (K3) sebagai subgrafnya, maka extremal graphnya adalah complete bipartite graph
K (n2 , n2 ).
Complete bipartite graph merupakan bipartite graph yang memiliki size maksimum, dimana setiap vertex dalam kelas vertex yang berbeda terhubung. Gambar 4.2 berikut ini merupakan ilustrasi dari extremal graph pada graf G dengan order n = 8 dan size ex(8; K3) = 12.
Gambar 4.2 Extremal graph (8, K3) Teorema 4.1. berikut menunjukan bahwa size maksimum dari graf tanpa memuat triangle (K3) adalah . Toerema 4.1. Size maksimum dari semua graf dengan n vertex tanpa memuat n2 triangle (K3) adalah . 4
Bukti : Dibuktikan dengan induksi pada n. 1. Untuk n genap. Untuk n = 2, Teorema 4.1 benar. Diasumsikan benar untuk graf G dengan n ≤ 2p vertex, berarti size maksimum dari graf G mempunyai paling banyak p2 edge. Akan dibuktikan benar untuk graf G dengan n = 2p + 2 vertex dan tidak memuat triangle.
18
Ketika G tidak memuat K3, maka ada vertex vi dan vj yang adjacent dan tidak memuat vertex v yang adjacent ke vi dan vj. Misalkan G′ = G – {vi, vj}, maka G′ mempunyai 2p vertex dan tidak memuat triangle. Dengan hipotesa induksi, G′ mempunyai paling banyak p2 edge. Sehingga tidak ada vertex v sedemikian sehingga vi dan vj keduanya adjacent ke v yang mengakibatkan vi, vj, v membentuk triangle pada graf G. Jika vi adjacent ke k vertex di G′, vj adjacent ke paling banyak 2p – k vertex, maka graf G mempunyai paling banyak
p 2 + k + (2 p − k ) + 1 = p 2 + 2 p + 1 = ( p + 1) = 2
n2 4
2. Untuk n ganjil. Untuk n = 3, Teorema 4.1 benar. Diasumsikan benar untuk graf G dengan n ≤ 2p – 1 vertex, berarti jumlah edge maksimum dari graf G mempunyai paling banyak
(4 p 2 − 4 p + 1) edge. 4
Akan dibuktikan benar untuk graf G dengan n = 2p + 1 vertex dan tidak memuat triangle. Ketika graf G tidak memuat K3, maka ada vertex vi dan vj yang adjacent dan tidak memuat vertex v yang adjacent ke vi dan vj. Misalkan G′ = G – {vi, vj}, maka G′ mempunyai (2p – 1) vertex dan tidak memuat triangle. Dengan hipotesa induksi, G′ mempunyai paling banyak
(4 p 2 − 4 p + 1) edge. 4 Sehingga tidak ada vertex v sedemikian sehingga vi dan vj keduanya adjacent ke v yang mengakibatkan vi, vj, v membentuk triangle pada graf G. Jadi jika vi adjacent ke k vertex G′, vj adjacent ke paling banyak (2p – 1) – k vertex. Oleh karena itu, graf G mempunyai paling banyak
(4 p
2
)
− 4p +1 (2 p + 1) + k + (2 p − 1 − k ) + 1 = 4 4 2 n = 4
2
19
Jadi size maksimum dari semua graf dengan n vertex tanpa memuat triangle (K3) n2 adalah . 4
Graf G adalah graf dengan order 5 yang memuat triangle sebagai subgrafnya, maka extremal graph pada graf G adalah complete bipartite graph K2, 3 dengan size ex(5; K3) = 6. Gambar 4.3 adalah extremal graph dengan order 5 dan size ex(5; K3).
v1
v3
v2
v3
v4
Gambar 4.3 Extremal graph dengan ex(3, K3)
20
4.2. Extremal Graph pada Subgraf Lengkap
Extremal graph pada subgraf lengkap adalah suatu graf dengan order n dan size maksimum ex(n; Kr) yang tidak memuat Kr sebagai subgrafnya. Graf yang tidak memuat Kr adalah (r – 1) – partite graph, sedangkan (r – 1) – partite graph yang mempunyai size maksimum adalah complete (r – 1) – partite graph (Michaelmas, 2003). Dari definisi, Turàn graph Tr(n) adalah complete r – partite graph dengan order n dan size maksimum tr(n) dengan kelas vertex adalah. n n + 1 n + r − 1 n1 = , n 2 = , ..., n r = vertex, r r r n r n n + i n + j t r (n ) = − ∑ i = ∑ . 2 1 2 0≤ i < j < r r r Teorema 4.2. berikut dikaji oleh Turán yang menunjukkan bahwa graf G dengan n vertex dan size maksimum yang tidak memuat Kr sebagai subgrafnya adalah Tr – 1(n). Dengan kata lain, extremal graph pada subgraf lengkap adalah Tr – 1(n). Teorema 4.2. Misal r dan n bilangan asli r ≥ 2, maka setiap graf dengan order n dan size lebih besar dari tr Tr
– 1(n)
– 1(n)
memuat Kr sebagai subgrafnya. Selanjutnya
adalah satu-satunya graf dengan order n dan size tr
– 1(n)
yang tidak
memuat Kr sebagai subgrafnya.
Bukti : Dibuktikan dengan induksi pada n. Untuk n ≤ r (r = 2), maka t1(2) = 0. Setiap graf dengan order 2 dan size 1 memuat K2. Jadi T1(2) adalah graf dengan order 2 dan size t1(2) tidak memuat K2. Jadi Teorema 4.2 benar untuk n ≤ r. Diasumsikan benar untuk 3 ≤ r < n, bahwa setiap graf dengan order m lebih kecil dari n dan size lebih besar dari tr – 1(m) memuat Kr, Tr – 1(m) adalah satu-satunya graf dengan order m dan size tr – 1(m) yang tidak memuat Kr sebagai subgrafnya.
21
Misal graf G adalah graf dengan order n dan size maksimum tanpa memuat Kr. Oleh karena itu graf G memuat Kr – 1 . Misal H = Kr - 1⊆ G. Dengan hipotesis induksi diperoleh r − 1 , q1 = |E(H)| = 2 q2 = size antara graf H dan V – H ≤ (n – r + 1)(r – 2), q3 = |E(V – H)| ≤ tr – 1(n – r+1). Oleh karena itu, |E(G)| = q1 + q 2 + q3 r − 1 + (n – r + 1)(r – 2)+ tr – 1(n – r + 1) |E(G)| ≤ 2 ≤ tr – 1(n) Karena G mempunyai size maksimum, maka q 2 = (n – r + 1)(r – 2). Dengan demikian himpunan vertex V(G) dapat dipartisi menjadi (r – 1) kelas vertex V1, V2, . . . , Vr – 1 dengan setiap vertexnya adjacent ke (r – 2) vertex di H. Jadi G adalah complete (r – 1) – partite graph dengan kelas vertex V1, V2, . . . , Vr – 1. Oleh karena itu, graf G adalah Tr –1(n).
Graf yang mengilustrasikan Teorema 4.2 diperlihatkan pada Gambar 4.4. Pada Gambar 4.4 graf T3(6) tidak memuat K4 sebagai subgrafnya dengan size t3(6) = 12. v1
v2
v3
v6
v4
v5 Gambar 4.4 T3(6)
22
Bardasarkan Teorema 4.2. jelas bahwa extremal graph pada subgraf lengkap adalah Tr – 1(n) dan juga setiap graf G dengan n vertex dan size lebih besar dari tr – 1(n) memuat Kr. Selanjutnya, Teorema 4.3 barikut menunjukkan bahwa setiap graf G dengan n vertex dan size tr – 1(n) + 1 memuat Kr
+1
dengan menghilangkan satu
edge. Teorema 4.3. Jika n ≥ r + 1, maka setiap G = (n, tr – 1(n)+1) memuat Kr+1 – e.
Bukti : Untuk n = r + 1, maka graf G = (r + 1, t r – 1 (r + 1) + 1). Size graf G adalah tr – 1(r + 1) + 1, dengan
r + 1 r −1 ni − ∑ + 1 t r −1 (r + 1) + 1 = 2 1 2 r + 1 − 2 + 1 = 2 r + 1 − 1. = 2 Karena graf G mempunyai size tersebut, maka graf G = Kr +1 – e. Jadi benar untuk n = r + 1 maka setiap G = (n, tr – 1(n) + 1) memuat Kr+1 – e. Diasumsikan benar untuk setiap graf dengan order lebih kecil n dengan mengingat graf G = (n, tr – 1(n)+1). Dibuktikan benar untuk setiap graf G = (n, tr – 1(n)+1) dengan n > r+1. Vertex v di Tr – 1(n) dengan degree minimum berada di kelas vertex dengan order terbesar, dengan mengambil vertex tersebut maka diperoleh Tr – 1(n – 1), berarti tr – 1(n) – δ(Tr – 1(n)) = tr – 1(n – 1)
(4.1)
∆( Tr – 1(n)) – δ(Tr – 1(n)) ≤ 1
(4.2)
Misal jumlah vertex dengan degree minimum di Tr – 1(n) adalah k. Karena n > r + 1, maka k > 2.
23
Sehingga, nδ(G) ≤ 2 e(G) = 2 tr – 1(n) + 2 2 tr – 1(n) = kδ(Tr – 1(n)) + (n – k)∆(Tr – 1(n)), k > 2 Dengan persamaan (4.2), maka diperoleh 2 tr – 1(n) ≤ n δ(Tr – 1(n)) + n – k nδ(G) ≤ nδ(Tr – 1(n)) + n – k + 2
(4.3)
Akan ditunjukan bahwa δ(G) ≤ δ(Tr – 1(n)). Diandaikan δ(G) > δ(Tr – 1(n)). Misal δ(Tr – 1(n)) = x, berarti δ(G) ≥ x + 1. Menurut persamaan (4.3), maka nδ(G) ≤ nδ(Tr – 1(n)) + n – k + 2, k > 2 < n(δ(Tr – 1(n)) + 1) < n(x + 1)
δ(G) < x + 1. Karena kontradiksi dengan pengandaian, maka δ(G) ≤ δ(Tr – 1(n). Ambil vertex v ∈ G adalah vertex dengan degree minimum, maka degG(v) = δ(G) |E(G – v)| = e(G) – δ(G) = tr – 1(n) + 1 – δ (G) ≥ tr – 1(n ) – δ (Tr – 1(n)) + 1 ≥ tr – 1(n – 1) + 1. Jadi
|E(G – v)| ≥ tr – 1(n – 1) + 1.
Dengan hipotesis induksi di atas, maka G – v memuat Kr + 1 – e. Jadi jika n ≥ r + 1 maka setiap graf G = (n, tr – 1(n)+1) memuat Kr +1 – e.
Bukti dari Teorema 4.3 di atas dapat diilustrasikan dengan contoh graf G pada Gambar 4.5. Graf G dengan himpunan vertex V(G) = {v1, v2, v3, v4, v5, v6, v7, v8} dan size t3(8) + 1= 22 memuat K5 – e.
24
v1
v2
v6 v3 v4
v7
v5
v8
Gambar 4.5 graf G = (n, tr – 1(n)+1)
v1
v2
v4 v6 v7
Gambar 4.6 Graf K5 – e Teorema 4.4. berikut menyatakan karakteristik barisan degree maksimal dari graf G tanpa memuat Kr.
25
Terema 4.4. Misal G adalah graf dengan himpunan vertex V = {v1, v2, . . ., vn}. Jika G tidak memuat Kr maka terdapat (r – 1) – partite graph H dengan himpunan vertex V sedemikian sehingga: degH(v) ≥ degG(v) untuk ∀ν∈V.
Bukti : Dibuktikan dengan induksi pada r. Untuk r = 2 berarti terdapat 1 – partite graph H yaitu graf dengan n vertex dengan degree nya nol, sehingga Teorema 4.4 benar. Diasumsikan benar untuk r – 2. Berarti Graf G adalah graf dengan himpunan vertex V yang tidak memuat Kr – 1, maka terdapat (r – 2) – partite graph H dengan himpunan vertex V sedemikian sehingga degH(v) ≥ deg G(v) ,∀ν∈V. Akan dibuktikan benar untuk r – 1. Diambil vertex x∈V(G) dengan degG(x) = ∆(G). Misal G′ = G[Γ(x)] maka G′ adalah graf yang tidak memuat Kr – 1. Misal V′ = Γ(x). Dengan hipotesa induksi maka terdapat (r – 2) – partite graph H′ dengan himpunan vertex V′ sedemikian sehingga degH′ (v) ≥ degG′ (v) ∀ν∈V′. Dibentuk H dengan menghubungkan setiap vertex di V\V′ ke H′. Dikontruksikan H dengan menghubungkan setiap vertex di V\V′ ke H′, maka H adalah (r – 1) – partite graph dengan himpunan vertex V. Selanjutnya ditunjukkan bahwa deg H (v) ≥ degG (v), ∀ν ∈V. Jika v∈V\V′, maka degH(v) = |V′ | = degG (x). Karena deg G (x) ≥ degG (v),∀ν ∈V, maka deg H(v) ≥ deg G (v) untuk v∈V\V′. Jika tidak, ν ∈V′ maka degH (v) = |V\V′ | + degH′ (v). Karena deg H’ (v) ≥ degG’ (v), ∀ν ∈V, maka degG (v) ≤ deg G’ (v) + |V\V′ | ≤ degH’ (v) + |V\V′ | = degH (v) Jadi deg H (v) ≥ degG (v), untuk ∀ν ∈V
26
Gambar 4.7 berikut mengilustrasikan Teorema 4.4 di atas adalah graf G ≅ C5 dimana tidak memuat K3 sebagai subgrafnya.
v1
v2
v5
v3
v4 Gambar 4.7 G ≅ C5 tidak memuat K3 sebagai subgrafnya Pada Gambar 4.6 graf G ≅ C5 tidak memuat K3, menurut Teorema 4.4. maka terdapat 2 – partite graph H dengan himpunan vertex V sedemikian sehingga degH(v) ≥ degG(v),untuk ∀ν∈V.
v2
v1 v5
v3
v4 Gambar 4.8 Graf H
27
4.3. Contoh – Contoh Penyelesaian Soal
Dari pembahasan tentang extremal graph pada subgraf lengkap, untuk lebih jelasnya diberikan contoh dan penyelesaian soal sebagai berikut.
Contoh 1 Temukan extemal graph pada subgraf lengkap K4 ! Penyelesaian : Telah dibahas bahwa extremal graph pada subgraf lengkap Kr adalah complete (r – 1) – partite graph, maka extremal graph pada subgraf lengkap K4 adalah complete 3 – partite graph dengan size maksimum ex(n;K4)= t3(n).
Contoh 2 Untuk 3 ≤ r < n dan n = t(r – 1) + k, 0 ≤ k< r – 1. Tunjukkan bahwa size graf K(n1, n2, . . . ,nr – 1) dengan kelas vertex V1, V2, . . . , Vr – 1 dimana kelas vertex V1, V2, . . . , Vk mempunyai n i = t + 1, dan kelas vertex Vk+1, Vk+2, . . . , Vr – 1 n t (n − r + 1 + k ) mempunyai ni = t adalah − ! 2 2 Penyelesaian : K(n1, n2, . . . ,nr – 1) adalah complete (r – 1) – partite graph dimana memiliki size tr – 1(n) maka n r −1 n tr −1 (n ) = − ∑ i 2 1 2 n k n r −1 n = − ∑ i + ∑ i 2 1 2 k +1 2
n t + 1 t + (r − 1 − k ) = − k 2 2 2 n n − r +1+ k = − t . 2 2
28
BAB V PENUTUP
5.1 Kesimpulan
Berdasarkan pembahasan maka dapat diambil kesimpulan sebagai berikut : 1. Extremal graph adalah graf dengan order n dengan size maksimum ex(n; G1) dan tidak memuat graf G1 sebagai subgrafnya. 2. Extremal graph pada graf lengkap adalah complete (r – 1) partite graph dengan extremal graph ≅ Tr – 1(n) dan ex(n; Kn) = tr – 1(n). 3. Jika n ≥ r + 1, maka setiap graf G = G(n, tr – 1(n) + 1) memuat Kr+1 – e. 4. Graf G dengan himpunan vertex V tidak memuat Kr sebagai subgrafnya, maka terdapat (r – 1) – partite graph H dengan himpunan vertex V(G) sedemikan sehingga dH (v) ≥ dG (v) untuk ∀v ∈V.
5.2 Saran
Saran yang dapat diberikan penulis mengenai extremal graph adalah dapat dikembangkan secara khusus tentang extremal graph misalnya extremal graph pada cycle, mengenai connectivitynya atau degree minimum.
29
