1

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 kota-

kota 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).

2

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.

3

e5

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

v1 v3

e4 e3

v4

Gambar 2.1 Graf G

4

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 degGv 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

5

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 v3

G1 : v2 G2 :

e1

e2 v3

v1 v1 v4

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.

6

v1

e1

v2 e4 |V(G)| = 4

e2 e3 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 graf G 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 v2

e2 e3

e4 v5 e5

e6 e7

v3 v4

Gambar 2.6 Graf G yang memuat walk, trail dan path

7

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.

8

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 v2

T1 : 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

kata lain graf lengkap adalah graf dengan order r dan size

2

r.

Graf lengkap dengan order r dinotasikan dengan Kr. Gambar 2.10 merupakan

contoh graf lengkap dengan 1 ≤ r ≤ 5.

K1 K2 K3 K4 K5

Gambar 2.10 Graf lengkap Kr, 1 ≤ r ≤ 5

9

e7

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 v7 v12 v11

G1 : G2 : G3 :

v4

v1 v2 v5 v6 v9 v10

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 v1 v1

G : e3 v8 H :

e1 e9 v5 e10 e11 e10 e11

e6 e4

v3 e8 v4 v6 e5 v7 v6 e5 v7

Gambar 2.12 Contoh subgraf dari graf G

10

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 <V′> 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 v1 v2 v3 v1 v2 v3

G : G1 : G2 :

v4 v5 v6 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}.

11

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(n1, n2, . . ., nr).

Gambar 2.15 merupakan contoh complete r – partite graph dengan r = 3 dan

r = 4.

12

v1 v2 v1 v2

K1,2,3 : v3 K1,1,1,1 :

v4 v5 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

13

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.

14

Teorema 2.1 (Chartrand dan Oellerman, 1993) Jika G adalah graf dengan

order n dan size p dengan V(G) = {v1, v2, . . . , vn}, maka

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)

∑=

=n

iiG pvdeg

1

2

15

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

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].

( ) .22

,1

...,,1

,

01

21

+

+=

−

=

−+=

+=

=

∑∑<<≤ r

jn

r

innnnt

vertexr

rnn

r

nn

r

nn

rji

ri

r

r

16

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.

Gambar 3.1 Langkah-langkah penulisan

Konsep dasar dan pengertian extremal graph

Pengertian Turán graph Extremal graph pada subgraf lengkap

Buku referensi, jurnal dan artikel dikaji

17

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)

18

Setiap graf G dengan order n yang memuat triangle (K3) sebagai

subgrafnya, maka extremal graphnya adalah complete bipartite graph ( )22

n,

nK .

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

triangle (K3) adalah

4

2n.

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.

19

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

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

)144( 2 +− pp edge.

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

)144( 2 +− pp 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. 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

112122

222 npppkpkp =+=++=+−++

( ) ( )

4

4

121)12(

4

144

2

22

n

pkpk

pp

=

+=+−−++

+−

20

Jadi size maksimum dari semua graf dengan n vertex tanpa memuat triangle (K3)

adalah

4

2n. �

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 v2

v3 v3 v4

Gambar 4.3 Extremal graph dengan ex(3, K3)

21

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.

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 – 1(n) memuat Kr sebagai subgrafnya. Selanjutnya

Tr – 1(n) 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.

( ) .22

,1

...,,1

,

01

21

+

+=

−

=

−+=

+=

=

∑∑<<≤ r

jn

r

innnnt

vertexr

rnn

r

nn

r

nn

rji

ri

r

r

22

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

q1 = |E(H)| =

−

2

1r,

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 + q2 + q3

|E(G)| ≤

−

2

1r+ (n – r + 1)(r – 2)+ tr – 1(n – r + 1)

≤ tr – 1(n)

Karena G mempunyai size maksimum, maka q2 = (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)

23

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, tr – 1 (r + 1) + 1).

Size graf G adalah tr – 1(r + 1) + 1, dengan

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.

( )

.12

1

122

1

122

111

1

11

−

+=

+−

+=

+

−

+=++ ∑

−

−

r

r

nrrt

ri

r

24

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.

25

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.

26

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) ≥ degG(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 degH (v) ≥ degG (v), ∀ν ∈V.

Jika v∈V\V′, maka degH(v) = |V′ | = degG (x).

Karena degG (x) ≥ degG (v),∀ν ∈V, maka degH(v) ≥ degG (v) untuk v∈V\V′.

Jika tidak, ν ∈V′ maka degH (v) = |V\V′ | + degH′ (v).

Karena degH’ (v) ≥ degG’ (v), ∀ν ∈V, maka

degG (v) ≤ degG’ (v) + |V\V′ |

≤ degH’ (v) + |V\V′ |

= degH (v)

Jadi degH (v) ≥ degG (v), untuk ∀ν ∈V �

27

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.

v1 v2

v5 v3

v4

Gambar 4.8 Graf H

28

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 ni = t + 1, dan kelas vertex Vk+1, Vk+2, . . . , Vr – 1

mempunyai ni = t adalah 2

)1(

2

krntn ++−−

!

Penyelesaian :

K(n1, n2, . . . ,nr – 1) adalah complete (r – 1) – partite graph dimana memiliki size

tr – 1(n) maka

∑−

−

−

=

1

11

22)(

ri

r

nnnt

+

−

= ∑ ∑

−

+

k r

k

ii nnn

1

1

1 222

€

( )

−−+

+−

=

21

2

1

2

tkr

tk

n

.2

1

2

++−

−

=

krnt

n

29

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.