Tugas Matematika Diskrit

TEORI GRAF

Teori graf merupakan pokok bahasan yang banyak penerapannya pada masa kini. Pemakaian teori graf telah banyak dirasakan dalam berbagai ilmu, antara lain : optimisasi jaringan, ekonomi, psikologi, genetika, riset operasi (OR), dan lain-lain. Makalah pertama tentang teori graf ditulis pada tahun 1736 oleh seorang matematikawan Swiss yang bernama Leonard Euler. Ia menggunakan teori graf untuk menyelesaikan masalah jembatan Königsberg (sekarang, bernama Kaliningrad). Berikut adalah ilustrasi masalah tersebut :

Masalah yang dikemukakan Euler : Dapatkah melewati setiap jembatan tepat sekali dan kembali lagi ke tempat semula? Berikut adalah sketsa yang merepresentasikan ilustrasi jembatan Königsberg yang pada gambar diatas. Himpunan titik yaitu {A, B, C, D} merepresentasikan sebagai daratan, dan garis yang menghubungkan titik-titik tersebut adalah sebagai jembatan.

Jawaban pertanyaan Euler adalah tidak mungkin. Agar bisa melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula maka jumlah jembatan yang menghubungkan setiap daratan harus genap.

Definisi Graf

Graf merupakan struktur diskrit yang terdiri himpunan sejumlah berhingga obyek yang disebut simpul (vertices, vertex) dan himpunan sisi (edges) yang menghubungkan simpul-simpul terseut. terdiri dari dari Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.
Notasi sebuah graf adalah G = (V, E), dimana :

-V merupakan himpunan tak kosong dari simpul-simpul (vertices), misalkan V = { v1 , v2 , ... , vn }
-E merupakan himpunan sisi – sisi (edges) yang menghubungkan sepasang simpul,
misalkan E = {e1 , e2 , ... , en }

Contoh :
Graf dari masalah jembatan Königsberg dapat disajikan sebagai berikut :

Misalkan graf tersebut adalah G(V, E) dengan

V = { A, B, C, D }
E = { (A, C), (A, C), (A, B), (A, B), (B, D), (A, D), (C, D)}
= { e1, e2, e3, e4, e5, e6, e7}

Pada graf tersebut sisi e1 = (A, C) dan sisi e2 = (A, C) dinamakan sisi-ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul A dan simpul C. Begitu pun dengan sisi e3 dan sisi e4. Sementara itu, pada graf diatas, tidak terdapat gelang (loop), yaitu sisi yang berawal dan berakhir pada simpul yang sama.
Dari definisi graf, himpunan sisi (E) memungkinkan berupa himpunan kosong. Jika graf tersebut mempunyai himpunan sisi yang merupakan himpunan kosong maka graf tersebut dinamakan graf kosong (null graph atau empty graph).


Derajat (Degree)

Derajat suatu simpul merupakan jumlah sisi yang bersisian dengan simpul tersebut.
Misalkan, suatu simpul v mempunyai 3 buah sisi yang bersisian dengannya maka dapat dikatakan simpul tersebut berderajat 3, atau dinotasikan oleh d(v) = 3.

Contoh :
Perhatikan graf berikut :

Pada graf diatas :

d(P) = d(Q) = d (S)= 5, sedangkan d(R) = 3.
Derajat sebuah simpul pada suatu graf berarah dijelaskan sebagai berikut :

• din(v) merupakan jumlah busur yang masuk ke simpul v
• dout(v) merupakan jumlah busur yang keluar dari simpul v

Dengan demikian derajat pada simpul tersebut, diperoleh : d(v) = din(v) + dout(v)

Lintasan (Path)

Lintasan dari suatu simpul awal v0 ke simpul tujuan vT di dalam suatu graf G merupakan barisan sebuah sisi atau lebih (x0, x1), (x1, x2), (x2, x3), …, (xn-1, xn) pada G, dimana x0 = v0 dan xn = vT. Lintasan ini dinotasikan oleh :
x0, x1, x2, x3, …, xn
Lintasan ini mempunyai panjang n, karena lintasan ini memuat n buah sisi, yang dilewati dari suatu simpul awal v0 ke simpul tujuan vT di dalam suatu graf G. Suatu lintasan yang berawal dan berakhir pada simpul yang sama dinamakan Siklus (Cycle) atau Sirkuit (Circuit).

Contoh :

Perhatikan graf berikut ini :

• Pada graf tersebut lintasan P, Q, R memiliki panjang 2. Sementara itu lintasan P, Q, S, R memiliki panjang 3.
• Lintasan P, Q, R, S, P dinamakan siklus atau sirkuit dengan panjang 4.
• Antara simpul P dan U maupun T tidak dapat ditemukan lintasan.

Cut-Se t

Cut-set dari suatu graf terhubung G adalah himpunan sisi yang jika dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah subgraf . Pada graf di bawah, {(1,4), (1,5), (2, 3), (2,4)} adalah cut-set. Terdapat banyak cut-set pada sebuah graf terhubung. Himpunan {(1,5), (4,5)} juga adalah cut-set, {(1,4), (1,5), (1,2)} adalah cut-set, {(5,6)} juga cut-set,
tetapi {(1,4), (1,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,5), (4,5)} adalah cut-set.