BAB 2 BEBERAPA ISTILAH DARI GRAPH
Pada bab ini akan dibahas beberapa konsep dan terminologi dalam graph yang akan dipergunakan sebagai landasan berpikir dalam melakukan penelitian ini. Juga akan dibahas beberapa jenis graph yang akan dipergunakan sebagai objek penelitian ini. Semua konsep, terminologi dan jenis graph tersebut akan dipergunakan pada bab pembahasan.
2.1 Graph Berdasarkan teori graph (Robin dan John, 1990) suatu graph G adalah suatu himpunan berhingga tak kosong dari objek-objek yang disebut verteks (minimal tunggal) bersama-sama dengan suatu himpunan yang anggotanya adalah pasangan yang tak berurut dan verteks yang berbeda pada G yang disebut edge (mungkin kosong), dan dinotasikan dengan G{V (G), E(G)}. Himpunan verteks dari G dinotasikan dengan V (G) dan himpunan edge dinotasikan dengan E(G). Banyaknya anggota dari himpunan verteks pada G disebut order G dan dinotasikan dengan p(G), atau dengan singkat ditulis p. Edge e = {u, v} atau juga dapat ditulis e = uv adalah sebuah edge dalam G, yaitu u dan v adalah titik-titik ujung dari e, maka u dan v dikatakan adjacent (berelasi) dimana u dan e adalah incedent (terhubung), begitu juga dengan v dan e. Banyaknya edge yang incedent dengan verteks u disebut degree/valensi/derajat dari u, dengan kata lain degree u adalah banyaknya edge yang memuat u sebagai titik ujung. Degree u dinotasikan dengan deg(u). Berikut ini diberikan beberapa terminologi pada graph, yaitu: 1. Suatu walk adalah barisan berhingga dan verteks dan edge secara bergantian, yang diawali dari verteks dan diakhiri dengan verteks. Bentuk umum dari walk v0 , e1, v1, e2, v2, . . . , vn−1 , en , vn 4 Universitas Sumatera Utara
5 dalam hal ini v0 merupakan verteks awal dan vn merupakan verteks akhir. Jika verteks awal dan verteks akhir dari suatu walk adalah sama, maka walk disebut close walk (walk tertutup). 2. Suatu trail adalah suatu walk dengan setiap edgenya berlainan. 3. Suatu path adalah suatu walk dengan setiap verteksnya berbeda. 4. Suatu cycle adalah suatu path yang memiliki verteks awal sama dengan verteks akhir. 5. Length (panjang) adalah bilangan yang menyatakan banyaknya edge yang muncul dalam suatu walk. 6. Edge e adalah sebuah jembatan untuk G jika G − e tidak terhubung. Secara umum, edge e adalah jembatan untuk suatu graph G jika G − e mempunyai komponen terhubung lebih dari G. Suatu graph biasanya dipresentasikan secara grafis, dengan setiap verteks dipresentasikan sebagai titik atau lingkaran kecil, dan setiap edge e = uv dipresentasikan dengan sebuah garis atau kurva yang menghubungkan titik-titik yang bersesuaian dengan u dan v.
Gambar 2.1 Presentasi grafis dari G(6, 9)
Universitas Sumatera Utara
6 Berdasarkan gambar 2.1 maka dapat ditentukan : 1. Order graph G adalah 6. 2. Degree verteks v1 , v2, v3, v4, v5, dan v6 masing-masing adalah 2, 4, 3, 2, 4, dan 3. 3. Barisan v1, e1, v2 , e7, v6, e5, v5, e8, v2 , e2, v3 adalah suatu walk dengan panjang 5. 4. Barisan v3 , e9, v5, e8, v2, e7, v6 adalah suatu path dengan panjang 3. 5. Barisan v2 , e7, v6, e5, v6, e9, v3 , e2, v2 adalah suatu cycle dengan panjang 4.
2.2 Jenis Graph Dibawah ini akan dibahas beberapa jenis graph yaitu: 1. Nullgraph adalah suatu graph yang memiliki degree 0 (nol) dan dinotasikan dengan N , dengan p adalah order N . Contoh 2.2.1 v4
v3
•
•
•
•
v1
v2
Gambar 2.2 Nullgraph berorder 4
2. Graph komplit adalah suatu graph yang lengkap dengan setiap dua verteks yang berbeda harus adjacent. Graph komplit dinotasikan dengan Kp , dengan p adalah order K. Teorema 2.2.1 Banyaknya edge pada snatu graph komplit dengan n verteks adalah 12 n(n − 1) buah. Universitas Sumatera Utara
7 Bukti : Untuk membuat sebuah edge memerlukan dua verteks. Karena banyaknya cara untuk rnemilih dua verteks dari n verteks adalah C(n, 2). Maka banyaknya edge adalah C(n, 2) = 12 (n − 1) buah. Contoh 2.2.2
Gambar 2.3 Komplit graph berorder 3
3. Graph bipartisi (bipartite) adalah suatu graph yang memiliki himpunan verteks yang dapat dipartisi menjadi dua himpunan bagian yang saling asing (disjoint), yaitu : V1 (G) = {v1 , v2 . . . , vi} V2 (G) = {vi+1, vi+2 , . . . , vn } sedemikian sehingga setiap edge dari G menghubungkan sebuah verteks dari V1 (G) kesebuah verteks dan V2 (G). Sebuah graph bipartisi lengkap, diartikan bahwa setiap verteks V1 (G) dihubungkan ke setiap verteks di V2 (G). Graph bipartisi dinotasikan dengan Km, n dengan m adalah jumlah verteks di V1 (G) dan n adalah jumlah verteks di V2 (G), dan standardisasi, diasumsikan m ≤ n. Contoh 2.2.3
Gambar 2.4 Komplit bigraph berorder 5
Universitas Sumatera Utara
8 4. Pohon (Tree) adalah suatu graph yang tidak memuat loop dan edge paralel (simple Graph) juga tidak memuat cycle, dan dinotasikan dengan T . Menurut Narsingh Deo (1986) misalkan G adalah suatu graph sederhana, G disebut tree apabila G suatu graph terhubung dan tidak memuat sirkuit. Daun (leaf / terminal verteks) adalah verteks dalam tree yang berderejat 1. Verteks dalam tree yang berderejat > 1 disebut verteks cabang. Contoh 2.2.4
Gambar 2.5 Pohon berorder 9
5. Graph path (path graph) Graph path dengan t verteks dinotasikan dengan P t, yaitu graph yang terdiri dari path tunggal. P t memiliki t − 1 edge. Contoh 2.2.5
Gambar 2.6 Graph path
6. Graph sikel (Cycle graph) Graph sikel adalah graph sederhana yang setiap verteksnya berderajat dua. Graph sikel dengan t verteks dilambangkan dengan Ct, t ≥ 3 adalah graph dengan t verteks yaitu v1 , v2, . . . , vt dan edge-edge (v1 , v2), (v2, v3), . . . , (vt−1 , vt), (vt, v1).
Universitas Sumatera Utara
9 Contoh 2.2.6
Gambar 2.7 Graph sikel
2.3 Beberapa Notasi dan Defenisi Untuk suatu graph G, bilangan ukuran-Ramsey rˆ(G) adalah bilangan minimum m untuk mana terdapat suatu graph F atas m edge sedemikian sehingga setiap dua-pewarnaan edge-edge dari F memenuhi copy monokhromatik dari G (Erdoset.al. 1978). Beck (1983) memperkenalkan invariant tree β (T ) yang didefinisikan sebagai berikut. Misalkan V (T ) = V0 (T ) ∪ V1 (T ) merupakan partisi yang ditentukan oleh dua-pewarnaan unik yang tepat dari himpunan vertex dari T . Tetapkan ∆i = ∆i (T ) = max{dT (v) : v ∈ Vi (T )} dan ni = ni (T ) = |Vi (T )| untuk i = 0, 1 dan misalkan β (T ) = n0∆0 + n1 ∆1. Dengan meningkatkan hasil yang dicapainya sebelumnya, Beck (1983) membuktikan bahwa untuk setiap tree T , β (T ) /4ˆ r (T ) O β (T ) (log |T |)12
dan memperkirakan bahwa rˆ (T ) = O (β (T )). Haxell dan Kohayakawa (1995) meningkatkan secara signifikan batas atas untuk rˆ (T ) = O (β (T ) log ∆ (T )). Embedding T ke dalam G dilakukan dengan alagoritma. Diyakini bahwa metode algoritma ini memang menarik dan bisa berguna dalam konteks serupa lainnya. Ternyata, dalam penelitian bersama dengan Kohayakawa, Rodl dan Rucinski (2008), digunakan teknik analog dalam algoritma yang menanamkan graph berdegree terbatas ke dalam graph acak yang tidak padat. Suatu graph tertentu G = (V, E) dan himpunan-himpunan yang saling lepas S, T ⊆ V , dinotasikan dengan EG (S, T ) himpunan semua edge dengan satu titik ujung di S dan titik ujung lainnya di T dan misalnya eG (S, T ) = |EG (S, T )|.
Universitas Sumatera Utara
10 Neighborhood dari suatu vertex v ∈ V dinotasikan dengan ΓG (v)dn neighborhood dari himpunan S ⊆ V dinotasikan dengan ΓG (S) = ∪v∈S ΓG (v). Definisi 2.3. Diberikan suatu graph G = (V, E), untuk setiap himpunan S ⊂ V , didefinisikan ΓG ∗ (S) = {v ∈ V : eG ({v}, S) = 1} sebagai himpunan neigbor unik dari S. Jika x, t ∈ R, ε > 0 adalah sedemikian sehingga x ∈ [(1 − ε)t, (1 + ε)t] maka ditulis x ∼t . Juga akan digunakan notasi standar Ωγ (f (n)), Oγ (f (n)) untuk kelas semua fungsi dengan batas bawah/atas c(γ)f (n), di mana c = c(γ)adalah konstanta yang hanya tergantung pada γ. Dalam banyak perhitungan digunakan secara implisit ketaksamaan yang sudah diketahui dengan jelas seperti a b a ea b 6 1 + x 6 exdan 6 b b b
(2.1)
Ketaksamaan Chernoff juga digunakan secara ekstensif: untuk ε > 0 dan setiap variabel acak Binomial X dengan parameter n dan p diperoleh P [|X − np| > εep] 6 ex {−Ωε (np)}
(2.2)
Definisi 2.4 (Himpunan LE). Dikatakan bahwa suatu himpunan vertex-vertex S dalam suatu graph G adalah ε -lossles expanding jika |Γ (S) \S| ∼ε e (S, V (G) \S), yaitu, hampir setiap edge dalam S-cut bersesuaian dengan suatu neighbor unik dari S. S disebut dengan singkatan himpunan LE. Ciri yang berguna dari himpunan LE adalah kekuatannya: sekalipun sebagian besar edge yang incident pada himpunan LE dihapus, sifat LE tetap bertahan. Ini dinyatakan secara formal dalam lemma sederhana berikut. Lemma 2.5. Misalkan G adalah suatu graph dan S ⊆ V = V (G). Untuk setiap G0 ⊆ G diperoleh |ΓG (S) \S| > eG (S, V \S) + 2 {|ΓG (S) \S| − eG (S, V \S)} Bukti. Misalkan N menotasikan jumlah edge e = uv dalam eG (S, V \S) sedemikian sehingga vertex-ujung v ∈ V \S memenuhi eG (v, S) ≥ 2. Catat bahwa
Universitas Sumatera Utara
11 |ΓG (S) \S| 6 {eG (S, V \S) − N } + n/2 karena setiap edge yang tidak dihitung oleh N bersesuaian tepat dengan satu neighbor unik dari S dan semua edge yang dihitung N bisa memberi kontribusi dengan paling banyak n/2 neighbor. Diperoleh −N > 2 {|ΓG (S) \S| − eG (S, V \S)}. Pernyataan terbukti karena |ΓG (S) \S| > eG (S, V \S) − N . Definisi 2.6. Misalkan T adalah suatu pohon (tree) dan V (T ) = V0 (T ) ∪ V1 (T ) adalah bi-partisi kanonik dari T . Tetapkan ni = |Vi (T )| dan ∆i = max{dT (v) : v ∈ Vi (T )}, untuk i = 0, 1. Parameter β (T ) didefinisikan sebagai β (T ) = n0 ∆0 +n1 ∆1. Pohon (tree) dengan parameter-parameter ini disebut dengan (n0 , ∆0, n1 , ∆1)-tree.
Universitas Sumatera Utara
