deskrit matematika

Matematika diskret atau diskrit adalah cabang matematika yang membahas segala sesuatu yang bersifat diskret. Diskret disini artinya tidak saling berhubungan (lawan dari kontinyu). Objek yang dibahas dalam Matematika Diskret - seperti bilangan bulat, graf, atau kalimat logika - tidak berubah secara kontinyu, namun memiliki nilai yang tertentu dan terpisah. Beberapa hal yang dibahas dalam matematika ini adalah teori himpunan, teori kombinatorial, permutasi, relasi, fungsi, rekursif, teori graf, dan lain-lain. Matematika diskret merupakan mata kuliah utama dan dasar untuk bidang ilmu komputer atau informatika.


    * Matematika diskrit: cabang matematika yang mengkaji objek-objek diskrit.

    * Apa yang dimaksud dengan kata diskrit (discrete)?

Benda disebut diskrit jika:

-        terdiri dari sejumlah berhingga elemen yang berbeda

-        elemen-elemennya tidak bersambungan

(unconnected).

Contoh: himpunan bilangan bulat (integer)

    * Lawan kata diskrit: kontinyu atau menerus (continuous).

Contoh: himpunan bilangan riil (real)

    * Komputer digital bekerja secara diskrit. Informasi  yang disimpan dan dimanipulasi oleh komputer adalah dalam bentuk diskrit.

    * Matematika diskrit merupakan ilmu dasar dalam pendidikan informatika atau ilmu komputer.

    * Matematika diskrit memberikan landasan matematis untuk kuliah-kuliah lain di informatika.

à algoritma, struktur data, basis data, otomata dan teori bahasa formal, jaringan komputer, keamanan komputer, sistem operasi, teknik kompilasi, dsb.

    * Matematika diskrit adalah matematika yang khas informatika à Matematika Informatika.

    * Materi-materi dalam matematika diskrit:

   1. Logika (logic)
   2. Teori Himpunan (set)
   3. Matriks (matrice)
   4. Relasi dan Fungsi (relation and function)
   5. Induksi Matematik (mathematical induction)
   6. Algoritma (algorithms)
   7. Teori Bilangan Bulat (integers)
   8. Barisan dan Deret (sequences and series)
   9. Teori Grup dan Ring (group and ring)

10.  Aljabar Boolean (Boolean algebra)

11.  Kombinatorial (combinatorics)

12.  Teori Peluang Diskrit (discrete probability)

13.  Fungsi Pembangkit dan Analisis Rekurens

14.  Teori Graf (graph – included tree)

15.  Kompleksitas Algoritma (algorithm complexity)

   1. Otomata & Teori Bahasa Formal (automata and formal language theory)

    * Contoh-contoh persoalan matematika diskrit:

-              berapa banyak kemungkinan jumlah password yang dapat dibuat dari 8 karakter?

-              bagaimana nomor ISBN sebuah buku divalidasi?

-              berapa banyak string biner yang panjangnya 8 bit yang mempunyai bit 1 sejumlah ganjil?

-              bagaimana menentukan lintasan terpendek dari satu kota a ke kota b?




Matemtika Diskrit merupakan cabang matematika yang mempelajari tentang obyek-obyek diskrit.Diskrit itu sendiri adalah sejumlah berhingga elemen yang berbeda atau elemen-elemen yang tidak bersambungan. Dimana data diskrit merupakan data yang satuannya selalu bulat dalam bilangan asli, tidak berbentuk pecahan, Contoh dari data diskrit misalnya manusia, pohon, bola dan lain-lain. trus mengapa belajar Matematika Diskrit ? ..

1. Landasan berbagai bidang matematika: logika, teori bilangan, aljabar linier dan abstrak, kombinatorika, teori graf, teori peluang (diskrit).

2. Landasan ilmu komputer: struktur data, algoritma, teori database, bahasa formal, teori automata, teori compiler, sistem operasi, dan pengamanan komputer (computer security).

3. Mempelajari latar belakang matematis yang diperlukan untuk memecahkan masalah dalam riset operasi (optimasi diskrit), kimia, ilmu-ilmu teknik, biologi, telekomunikasi, dsb.

materi Matematika Diskrit.

BAB I HIMPUNAN
BAB II RELASI DAN FUNGSI
BAB III KOMBINATORIKA
BAB IV TEORI GRAF
BAB V POHON (TREE)
BAB VI PEWARNAAN GRAF

BAB I
H I M P U N A N

Dalam kehidupan nyata, banyak sekali masalah yang terkait dengan data (objek) yang dikumpulkan berdasarkan kriteria tertentu. Kumpulan data (objek) inilah yang selanjutnya didefinisikan sebagai himpunan. Pada bab awal ini akan dibahas tentang definisi dan keanggotaan suatu himpunan, operasi himpunan dari beberapa jenis himpunan.
1.1 Definisi dan Keanggotaan Suatu Himpunan
Himpunan (set) merupakan sekumpulan objek-objek yang berbeda yang dapat didefinisikan dengan jelas. Objek di dalam himpunan dinamakan unsur atau anggota himpunan. Keanggotaan suatu himpunan dinyatakan oleh notasi ’?’.
Contoh 1 :
A = {x, y, z}
x ? A : x merupakan anggota himpunan A.
w ? A : w bukan merupakan anggota himpunan A.
Ada beberapa cara dalam menyatakan himpunan, yaitu :
a. Mencacahkan anggotanya (enumerasi)
Dengan cara ini, himpunan tersebut dinyatakan dengan menyebutkan semua
anggota himpunannya di dalam suatu kurung kurawal.
Contoh 2 :
- Himpunan empat bilangan ganjil pertama: A = {1, 3, 5, 7}.
- Himpunan lima bilangan prima pertama: B = {2, 3, 5, 7, 11}.
- Himpunan bilangan asli yang kurang dari 50 : C = {1, 2, ..., 50}
- Himpunan bilangan bulat ditulis sebagai {…, -2, -1, 0, 1, 2, …}.

b. Menggunakan simbol standar (baku)
Suatu himpunan dapat dinyatakan dalam suatu simbol standar (baku) yang telah
diketahui secara umum oleh masyarakat (ilmiah).
Contoh 3 :
N = himpunan bilangan alami (natural) = { 1, 2, ... }
Z = himpunan bilangan bulat = { ..., -2, -1, 0, 1, 2, ... }
Q = himpunan bilangan rasional
R = himpunan bilangan riil
C = himpunan bilangan kompleks
Himpunan yang universal (semesta pembicaraan) dinotasikan dengan U.

4. Menggunakan Diagram Venn
Suatu himpunan dapat dinyatakan dengan cara menuliskan anggotanya dalam
suatu gambar (diagram) yang dinamakan diagram venn.

Jumlah unsur dalam suatu himpunan dinamakan kardinalitas dari himpunan tersebut. Misalkan, untuk menyatakan kardinalitas himpunan A ditulis dengan notasi:

n(A) atau ?A ?
Contoh 8 :
(i) B = { x | x merupakan bilangan prima yang lebih kecil dari 10 },
atau B = {2, 3, 5, 7 } maka ?B? = 4
(ii) A = {a, {a}, {{a}} }, maka ?A? = 3
Jika suatu himpunan tidak mempunyai anggota, dengan kata lain dengan kardinalitas himpunan tersebut sama dengan nol maka himpunan tersebut dinamakan himpunan kosong (null set). Notasi dari suatu himpunan kosong adalah : ? atau {}
Contoh 9 :
(i) P = {Mahasiswa Teknik Industri STT Telkom yang pernah ke Mars},
maka n(P) = 0
Jadi P = ?

Himpunan A dikatakan himpunan bagian (subset) dari himpunan B jika dan hanya jika setiap unsur A merupakan unsur dari B. Dalam hal ini, B dikatakan superset dari A.
Notasi himpunan bagian : A ? B atau A ? B
Jika digambarkan dalam bentuk diagram Venn himpunan bagian tersebut menjadi :
UAB

Himpunan kuasa (power set) dari himpunan A merupakan suatu himpunan yang unsur-unsurnya merupakan semua himpunan bagian dari A, termasuk himpunan kosong dan himpunan A sendiri. Himpunan kuasa dinotasikan oleh P(A). Jumlah anggota (kardinal) dari suatu himpunan kuasa bergantung pada kardinal himpunan asal. Misalkan, kardinalitas himpunan A adalah m, maka ?P(A)? = 2m.
Contoh 12 :
Jika A = { x, y }, maka P(A) = { ?, { x }, { y }, { x, y }}
Contoh 13 :
Himpunan kuasa dari himpunan kosong adalah P(?) = {?}, sementara itu himpunan kuasa dari himpunan {?} adalah P({?}) = {?, {?}}.
Pernyataan A ? B digunakan untuk menyatakan bahwa A adalah himpunan bagian (subset) dari B yang memungkinkan A = B.
Dua buah himpunan dikatakan sama jika memenuhi kondisi berikut :
A = B jika dan hanya jika setiap unsur A merupakan unsur B dan sebaliknya setiap unsur B merupakan unsur A.
Untuk menyatakan A = B, yang perlu dibuktikan adalah A adalah himpunan bagian dari B dan B merupakan himpunan bagian dari A. Jika tidak demikian, maka A ? B.
atau
A = B ?? A ? B dan B ? A
Contoh 14 :
(i) Jika A = { 0, 1 } dan B = { x | x (x – 1) = 0 },
maka A = B
(ii) Jika A = { 3, 5, 8, 5 } dan B = {5, 3, 8 },

Dua buah himpunan dikatakan ekivalen jika masing-masing mempunyai kardinalitas yang sama. Misalkan, himpunan A adalah ekivalen dengan himpunan B berarti kardinal dari
himpunan A dan himpunan B adalah sama, notasi yang digunakan adalah : A ~ B
Contoh 15 :
Misalkan A = { 2, 3, 5, 7 } dan B = { a, b, c, d },
maka A ~ B sebab ?A? = ?B? = 4
Dua himpunan A dan B dikatakan saling lepas (disjoint) jika keduanya tidak memiliki unsur yang sama. Notasi yang digunakan adalah A // B . Jika dinyatakan dalam bentuk diagram Venn adalah sebagai berikut :
UAB
Contoh 16 :
Jika A = { x | x ? N, x < 10 } dan B = { 11, 12, 13, 14, 15 },
maka A // B.

1.2 Operasi Himpunan
Ada beberapa operasi himpunan yang perlu diketahui, yaitu : irisan , gabungan, komplemen, selisih dan beda setangkup.
a. Irisan (intersection)
Irisan antara dua buah himpunan dinotasikan oleh tanda ‘? ‘.
Misalkan A dan B adalah himpunan yang tidak saling lepas, maka
A ? B = { x | x ? A dan x ? B }

c. Komplemen (complement)
Komplemen dari suatu himpunan merupakan unsur -unsur yang ada pada himpunan
universal (semesta pembicaraan ) kecuali anggota himpunan tersebut. Misalkan A
merupakan himpunan yang berada pada semesta pembicaraan U, maka komplemen dari
himpunan A dinotasikan oleh :
A = { x | x ? U dan x ? A }

f. Perkalian Kartesian (cartesian product)
Perkalian kartesian antara dua buah himpunan dinotasikan oleh tanda ‘× ‘.
Misalkan A dan B adalah himpunan, maka perkalian kartesian antara A dan B
dinotasikan oleh :
A × B = {(a, b) ? a ? A dan b ? B }

Misalkan ada dua himpunan dengan kardinalitas berhingga, maka kardinalitas himpunan hasil dari suatu perkalian kartesian antara dua himpunan tersebut adalah perkalian antara kardinalitas masing-masing himpunan. Dengan demikian, jika A dan B merupakan himpunan berhingga, maka:

?A × B? = ?A? . ?B?.
Pasangan terurut (a, b) berbeda dengan (b, a), dengan kata lain (a, b) ? (b, a). Dengan
argumen ini berarti perkalian kartesian tidak komutatif, yaitu
A × B ? B × A
dimana A atau B bukan himpunan kosong.
Jika A = ? atau B = ?, maka
A × B = B × A = ?
Hukum-hukum yang berlaku untuk operasi himpunan adalah sebagai berikut :
1. Hukum identitas:
? A ? ? = A
? A ? U = A
2. Hukum null/dominasi:
? A ? ? = ?
? A ? U = U
3. Hukum komplemen:
? A ? A = U
? A ? A = ?
4. Hukum idempoten:
? A ? A = A
? A ? A = A
5. Hukum involusi:
)(A= A
6. Hukum penyerapan (absorpsi):
? A ? (A ? B) = A
? A ? (A ? B) = A
7. Hukum komutatif:
? A ? B = B ? A
? A ? B = B ? A
8. Hukum asosiatif:
? A ? (B ? C) = (A ? B) ? C
? A ? (B ? C) = (A ? B) ? C
9. Hukum distributif:
? A ? (B ? C) = (A ? B) ? (A ? C)
? A ? (B ? C) = (A ? B) ? (A ? C)
10. Hukum De Morgan:
? BA? = BA?
? BA? = BA?
11. Hukum komplemen
? ? = U

? U = ?
1.3 Prinsip Dualitas
Prinsip dualitas mengemukakan bahwa dua konsep yang berbeda dapat dipertukarkan namun tetap memberikan jawaban yang benar.
Contoh 24 :
AS ?? kemudi mobil di kiri depan
Indonesia ?? kemudi mobil di kanan depan
Peraturan:
(a) di Amerika Serikat,

• mobil harus berjalan di bagian kanan jalan,

• pada jalan yang berlajur banyak, lajur kiri untuk mendahului,

• bila lampu merah menyala, mobil belok kanan boleh langsung

(b) di Indonesia,

• mobil harus berjalan di bagian kiri jalan,

• pada jalur yang berlajur banyak, lajur kanan untuk mendahului,

• bila lampu merah menyala, mobil belok kiri boleh langsung

Prinsip dualitas pada kasus diatas adalah:
Konsep kiri dan kanan dapat dipertukarkan pada kedua negara tersebut sehingga peraturan yang berlaku di Amerika Serikat menjadi berlaku pula di Inggris.
(Prinsip Dualitas pada Himpunan). Misalkan S adalah suatu kesamaan (identity) yang melibatkan himpunan dan operasi-operasi seperti ?, ?, dan komplemen. Jika S* merupakan kesamaan yang berupa dual dari S maka dengan mengganti ? ? ?, ? ? ?, ? ? U, U ? ?, sedangkan komplemen dibiarkan seperti semula, maka operasi-operasi tersebut pada kesamaan S* juga benar.
Tabel 1.1 Dualitas dari Hukum Aljabar Himpunan

Hukum Aljabar

1. Hukum identitas:
A ? ? = A     Dualnya:
A ? U = A       
2. Hukum null/dominasi:
A ? ? = ?     Dualnya:
A ? U = U      
3. Hukum komplemen :
A ? A = U     Dualnya:
A ? A= ?       
4. Hukum idempoten :
A ? A = A     Dualnya:
A ? A = A    

BAB II
RELASI DAN FUNGSI
Dalam kehidupan nyata, senantiasa ada hubungan (relasi) antara dua hal atau unsur-unsur dalam suatu kelompok. Misalkan, hubungan antara suatu urusan dengan nomor telepon, antara pegai dengan gajinya, dan lain-lain. Pada bab ini, akan dibahas tentang hubungan antara dua himpunan tak kosong dengan suatu aturan pengkaitan tertentu. Pembahasan tersebut meliputi definisi relasi dan fungsi, operasi beserta sifat-sifatnya.

2.1 Definisi Relasi dan Cara Penyajian
Pada bab sebelumnya, telah dibahas tentang Cartesian product, yaitu berupa pasangan terurut yang menyatakan hubungan dari dua himpunan. Semua pasangan terurut yang mungkin merupakan anggota dari himpunan hasil Cartesian product dua buah himpunan. Sebagian dari anggota himpunan tersebut mempunyai hubungan yang khusus (tertentu) antara dua unsur pada pasangan urut tersebut, dengan aturan tertentu. Aturan yang menghubungkan antara dua himpunan dinamakan relasi biner. Relasi antara himpunan A dan himpunan B merupakan himpunan yang berisi pasangan terurut yang mengikuti aturan tertentu. Dengan demikian relasi biner R antara himpunan A dan B merupakan himpunan bagian dari cartesian product A × B atau R ? (A × B).
Notasi dari suatu relasi biner adalah a R b atau (a, b) ? R. Ini berarti bahwa a dihubungankan dengan b oleh R. Untuk menyataan bahwa suatu unsur dalam cartesian product bukan merupakan unsur relasi adalah a R b atau (a, b) ? R, yang artinya a tidak dihubungkan oleh b oleh relasi R. Himpunan A disebut daerah asal (domain) dari R, dan
himpunan B disebut daerah hasil (range) dari R.
Contoh 2.1 :
Misalkan A = {2, 3, 4} dan B = {2, 4, 8, 9, 15}.
Jika kita definisikan relasi R dari A ke B dengan aturan :
(a, b) ? R jika a faktor prima dari b
Jawab :
Seperti yang telah dipelajari sebelumnya, cartesian product A × B adalah :
A × B = {(2, 2), (2, 4), (2, 8), (2, 9), (2, 15), (3, 2), (3, 4), (3, 8),
(3, 9), (3, 15), (4, 2), (4, 4), (4, 8), (4, 9), (4, 15)}
Dengan menggunakan definisi relasi diatas, relasi R dari A ke B yang mengikuti aturan tersebut adalah :
R = {(2, 2), (2, 4), (2, 8), (3, 9), (3, 15) }
Relasi dapat pula terjadi hanya pada sebuah himpunan, yaitu relasi pada A.. Relasi pada himpunan A merupakan himpunan bagian dari cartesian product A × A.

Contoh 2.2 :
Misalkan R adalah relasi pada A = {2, 3, 4, 8, 9} yang didefinisikan oleh :
(x, y) ? R jika dan hanya jika x habis dibagi oleh y.
Jawab :
Relasi R pada A yang mengikuti aturan tersebut adalah :
R = {(2, 2), (4, 4), (4, 2), (8, 8), (8, 2), (8, 4), (3, 3), (9, 9), (9, 3)}
Cara menyatakan suatu relasi bisa bermacam-macam, antara lain : dengan diagram panah, tabel, matriks, bahkan dengan graph berarah. Berikut ini, akan dibahas satu-persatu cara
menyajikankan suatu relasi dengan cara-cara tersebut.
Cara menyajikan suatu relasi :
a. Penyajian Relasi dengan Diagram Panah
Misalkan A = {2, 3, 4} dan B = {2, 4, 8, 9, 15}.
Jika kita definisikan relasi R dari A ke B dengan aturan :
(a, b) ? R jika a faktor prima dari b
maka relasi tersebut dapat digambarkan dengan diagram panah berikut ini :
b. Penyajian Relasi berupa Pasangan Terurut
Contoh relasi pada (a) dapat dinyatakan dalam bentuk pasangan terurut, yaitu :
R = {(2, 2), (2, 4), (2, 8), (3, 9), (3, 15)}
c. Penyajian Relasi dengan Tabel
Kolom pertama tabel menyatakan daerah asal, sedangkan kolom kedua menyatakan
daerah hasil. Relasi pada yang dijelaskan pada bagian (a) dapat sebagai berikut :
Tabel Relasi faktor prima dari

BAB III
KOMBINATORIK
Persoalan kombinatorik bukan merupakan persoalan yang baru dalam kehidupan nyata. Banyak persoalan kombinatorik yang sederhana telah diselesaiakan dalam masyarakat. Misalkan, saat pemilihan pemain untuk tim sepak bola yang terdiri dari 11 pemain. Apabila ada 20 orang ingin membentuk suatu tim sepak bola, ada berapa kemungkinan komposisi pemain yang dapat terbentuk? Contoh lain adalah dalam menentukan sebuah password panjangnya 6 sampai 8 karakter. Karakter boleh berupa huruf atau angka. Berapa banyak kemungkinan password yang dapat dibuat ? Tetapi selain itu para ilmuwan pada berbagai bidang juga kerap menemukan sejumlah persoalan yang harus diselesaikan. Pada Bab ini, kita akan membahas tentang kombinatorik, permutasi dan apa yang terkait dengan itu. Kombinatorik merupakan cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya.
3.1 Prinsip Dasar Menghitung
Dua prinsip dasar yang digunakan dalam menghitung (counting) yaitu aturan
pejumlahan dan aturan perkalian.
Prinsip Penjumlahan
Jika suatu himpunan A terbagi kedalam himpunan bagian A1, A2, …, An, maka jumlah unsur pada himpunan A akan sama dengan jumlah semua unsur yang ada pada setiap himpunan bagian A1, A2, …, An.
Secara tidak langsung, pada prinsip penjumlahan, setiap himpunan bagian A1, A2, …, An tidak saling tumpang tindih (saling lepas). Untuk himpunan yang saling tumpang tindih tidak berlaku lagi prinsip penjumlahan, dan ini harus diselesaikan dengan prinsip inklusi-eksklusi yang akan dibahas kemudian.

Prinsip Perkalian
Misalkan sebuah prosedur dapat dipecah dalam dua penugasan. Penugasan pertama dapat dilakukan dalam n1 cara, dan tugas kedua dapat dilakukan dalam n2 cara setelah tugas pertama dilakukan. Dengan demikian, dalam mengerjakan prosedur tersebut ada (n1 x n2) cara.
Secara tidak langsung, pada prinsip perkalian, bisa terjadi saling tumpang tindih (tidak saling lepas).
m2 x 2 x 2 = 27
= 128 cara.

Password suatu login pada sistem komputer panjangnya lima sampai tujuh karakter. Tiap karakter boleh berupa huruf (huruf besar dan huruf kecil tidak dibedakan) atau angka. Berapa banyak password yang dapat dibuat untuk suatu login ?
Jawab :
Banyaknya huruf alfabet adalah 26 (A – Z) dan banyak angka adalah 10 (0 – 9), jadi seluruhnya 36 karakter.
Untuk password dengan panjang 5 karakter, jumlah kemungkinan password adalah
(36)(36)(36)(36)(36) = 365 = 60.466.176
untuk password dengan panjang 6 karakter, jumlah kemungkinan password adalah
(36)(36)(36)(36)(36)(36)(36) = 366 = 2.176.782.336
dan untuk password dengan panjang 8 karakter, jumlah kemungkinan password adalah
(36)(36)(36)(36)(36)(36)(36)(36) = 367 = 78.364.164.096
Jumlah seluruh password yang mungkin adalah
60.466.176 + 2.176.782.336 + 78.364.164.096 = 80.601.412.608 buah.
mJadi, untuk suatu login akan mempunyai 80.601.412.608 buah kemungkinan password.
Prinsip Inklusi-Eksklusi
Ketika dua proses dikerjakan dalam waktu yang sama, kita tidak bisa menggunakan prinsip penjumlahan untuk menghitung jumlah cara untuk memilih salah satu dari dua proses tersebut. Untuk menghitung proses tersebut, kita harus mengenal prinsip inklusi-eksklusi.
Contoh :
Berapa banyak byte yang dapat disusun oleh 8-bit, yang dimulai dengan ‘11’ atau berakhir dengan ‘00’?
Jawab :
Misalkan,
A adalah himpunan byte yang dimulai dengan ‘11’,
B adalah himpunan byte yang diakhiri dengan ‘00’,
A ? B adalah himpunan byte yang berawal dengan ‘11’ dan berakhir dengan ‘00’,
dan
A ? B adalah himpunan byte yang berawal dengan ‘11’ atau berakhir dengan ‘00’
Adiwijaya Sekolah Tinggi Teknologi Telkom 40 Matematika Diskrit
Maka jumlah kemungkinan byte yang dapat disusun pada himpunan A adalah
(1)(1)(2)(2)(2)(2)(2)(2) = 26
Tulis, ?A? = 26
= 64
Sementara itu, jumlah kemungkinan byte yang dapat disusun pada himpunan B adalah (2)(2)(2)(2)(2)(2)(1)(1) = 26
Jadi, ?B? = 26 = 64,
Dengan cara yang sama, jumlah kemungkinan byte yang dapat disusun pada himpunan A ? B adalah (1)(1)(2)(2)(2)(2)(1)(1) = 24
Sehingga ?A ? B? = 24 = 16.
maka
?A ? B? = ?A? + ?B? – ?A ? B?
= 64 + 64 – 16
= 112.
Dengan demikian, jumlah byte yang dapat disusun oleh 8-bit, yang dimulai dengan ‘11’ atau berakhir dengan ‘00’ adalah 112 buah.
3.2 Permutasi dan Kombinasi
Permutasi
Suatu permutasi merupakan susunan yang mungkin dibuat dengan memperhatikan urutan. Dengan kata lain, permutasi merupakan bentuk khusus aplikasi prinsip perkalian. Misalkan diberikan suatu himpunan A dengan jumlah anggota adalah n, maka susunan terurut yang terdiri dari r buah anggota dinamakan permutasi-r dari A, ditulis P(n, r). Agar lebih jelas dalam perhitungannya, perhatikan penjelasan berikut ini :

• Jika r > n, jelas bahwa P(n, r) = 0, karena tak mungkin menyusun r anggota dari A yang hanya terdiri dari n buah anggota dimana n < r.

• Jika r ? n,
Dari n anggota A maka urutan pertama yang dipilih dari n objek adalah dengan n cara. Urutan kedua dipilih dari n – 1 objek, adalah dengan n – 1 cara, karena satu anggota telah terpilih. Urutan ketiga dipilih dari n – 2 objek, adalah dengan n – 2 cara, karena dua anggota telah terpilih. Hal ini dilakukan terus menerus sehingga urutan terakhir dipilih dari n – r + 1 objek yang tersisa. Menurut kaidah perkalian, pemilihan objek dalam susunan r buah objek dari n buah objek dapat dilakukan dengan :

n(n – 1) (n – 2) … (n – r + 1) cara
Dengan demikian, permutasi r objek dari n buah objek adalah jumlah kemungkinan urutan r buah objek yang dipilih dari n buah objek, dengan r ? n, pada setiap kemungkinan penyusunan r buah objek tidak ada urutan objek yang sama, yaitu :
P(n, r) = n(n – 1) (n – 2) … (n – r + 1)
= )!(!rnn?

Contoh 1 :
Misalkan S = {p, q, r}. Berapa cara yang mungkin dalam penyusunan dua huruf pada S sehingga tidak ada urutan yang sama ?
Jawab :
Susunan dua huruf yang mungkin adalah :
pq, pr, qr, qp, rp, rq
Jadi penyusunan tersebut dapat dilakukan dengan enam buah cara.
Dalam penyusunan ini, dapat menggunakan definisi permutasi, yaitu :
()611.2.3!23!3)2,3(==?=P
Dengan menggunakan definisi permutasi, penyusunan tersebut dapat dilakukan dengan enam buah cara.
Contoh 2 :
Misalkan kita mempunyai lima buah bola dengan warna yang berbeda satu sama lain dan 3 buah kotak. Kita akan memasukan bola tersebut kedalam kotak. Masing-masing kotak hanya boleh diisi 1 buah bola. Berapa jumlah urutan bola dengan warna berbeda yang mungkin dibuat dari penempatan bola ke dalam kotak-kotak tersebut?
Jawab :
kotak 1 dapat diisi oleh salah satu dari 5 bola (ada 5 pilihan);
kotak 2 dapat diisi oleh salah satu dari 4 bola (ada 4 pilihan);
kotak 3 dapat diisi oleh salah satu dari 3 bola (ada 3 pilihan).
Jumlah urutan berbeda dari penempatan bola = (5)(4)(3)
= 60
Jika menggunakan definisi permutasi maka :
()601.21.2.3.4.5!35!5)3,5(==?=P
Kombinasi
Misalkan r merupakan unsur bilangan bulat tak negatif. Yang dimaksud dengan kombinasi r dari suatu himpunan B yang terdiri dari n anggota (objek) yang berbeda adalah jumlah himpunan bagian dari B yang memiliki anggota r buah objek. Interpretasi yang lain tentang kombinasi adalah menyusun (memilih) objek sejumlah r dari n buah objek yang ada.

Contoh 1 :
Misalkan A = {p, q, r }, tentukan semua himpunan bagian dari A yang memiliki kardinalitas dua.
Jawab :
Himpunan bagian tersebut antara lain : {p, q}, {p, r}, dan {q, r}.
Jadi kita mempunyai empat kombinasi :
pq, pr, dan qr
Pada himpunan, urutan unsur pada himpunan tidak diperhatikan. Dengan demikian, kombinasi 2 dari himpunan A (penyusunan dua huruf tanpa memperhatikan urutan) adalah 3, yaitu pq, pr, dan qr. Ini berbeda, pada saat kita mendefinisikan permutasi (urutan diperhatikan), penyusunan tersebut dapat dilakukan dengan enam buah cara, yaitu pq, pr, qr, qp, rp,dan rq.
Contoh 2 :
Misalkan ada 2 buah bola yang berwarna sama dan 3 buah kotak. Bola akan dimasukan ke dalam kotak sehingga setiap kotak hanya boleh berisi paling banyak 1 bola. Berapa jumlah cara memasukkan bola ke dalam kotak tersebut ?
Jawab :
Misalkan ketiga kotak tersebut ditaruh memanjang, maka ada 3 cara memasukan dua bola tersebut kedalam kotak, yaitu :
Cara I : kedua bola masing-masing ditaruh pada dua kotak pertama (kotak I dan
kotak II).
Cara II : kedua bola masing-masing ditaruh pada dua kotak yang paling ujung
(kotak I dan kotak III) .
Cara III: kedua bola masing-masing ditaruh pada dua kotak terakhir (kotak II dan
Kotak III) .
Secara umum, jumlah cara memasukkan r buah bola yang berwarna sama ke dalam n buah kotak adalah :
)!(!!!))1()...(2)(1(rnrnrrnnnn?=????
Ini merupakan rumus umum kombinasi yang dinotasikan oleh C(n, r) atau ????????rn
Diketahui ada n buah bola yang tidak seluruhnya berbeda warna (jadi, ada beberapa bola yang warnanya sama) akan dimasukan kedalam n buah kotak. Misalnya komposisi bola tersebut adalah :
n1 bola diantaranya berwarna 1,
n2 bola diantaranya berwarna 2,
M
nk bola diantaranya berwarna k,
jadi n1 + n2 + … + nk = n.
Berapa jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maksimum satu buah bola) ?

Jika n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan n buah bola ke dalam n buah kotak adalah
P(n, n) = n!.
Dari pengaturan n buah bola itu,
ada n1! cara memasukkan bola berwarna 1
ada n2! cara memasukkan bola berwarna 2
M
ada nk! cara memasukkan bola berwarna k
Permutasi n buah bola yang mana n1 diantaranya berwarna 1, n2 bola berwarna 2, …, nk bola berwarna k adalah:
!!...!!!!...!),(),...,,;(212121kkknnnnnnnnnPnnnnP==
Cara lain:
Ada C(n, n1) cara untuk menempatkan n1 buah bola yang berwarna 1.
Ada C(n – n1, n2) cara untuk menempatkan n2 buah bola berwarna 2.
Ada C(n – n1 – n3, n3) cara untuk menempatkan n3 buah bola berwarna 3.
M
Ada C(n – n1 – n2 – … – nk-1, nk ) cara untuk menempatkan nk buah bola berwarna k.
Jumlah cara pengaturan seluruh bola kedalam kotak adalah:
C(n; n1, n2, …, nk) = C(n, n1) C(n – n1, n2) C(n – n1 – n2 , n3)
… C(n – n1 – n2 – … – nk-1, nk)
= )!(!!11nnnn? )!(!)!(2121nnnnnn??? )!(!)!(21321knnnnnnnn?????
… )!...(!)!...(121121kkkknnnnnnnnnn???????????
= !!...!!!321knnnnn
Kesimpulan:
!!...!!),...,,;(),...,,;(212121kkknnnnnnnnCnnnnP==
Kombinasi Dengan Pengulangan
Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.

(i) Masing-masing kotak hanya boleh diisi paling banyak satu buah bola.
Jumlah cara memasukkan bola: C(n, r).

(ii) Jika masing-masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola)
Maka Jumlah cara memasukkan bola: C(n + r – 1, r).
C(n + r – 1, r) = C(n + r –1, n – 1).


Contoh :
20 buah apel dan 15 buah jeruk dibagikan kepada 5 orang anak, tiap anak boleh mendapat lebih dari 1 buah apel atau jeruk, atau tidak sama sekali. Berapa jumlah cara pembagian yang dapat dilakukan?
Jawab :
n = 5, r1 = 20 (apel) dan r2 = 15 (jeruk)
Membagi 20 apel kepada 5 anak: C(5 + 20 – 1, 20) cara,
Membagi 15 jeruk kepada 5 anak: C(5 + 15 – 1, 15) cara.
Jumlah cara pembagian kedua buah itu adalah
C(5 + 20 – 1, 20) × C(5 + 15 – 1, 15) = C(24, 20) × C(19, 15)
Koefisien Binomial
Misalkan n merupakan bilangan bulat positif, dengan teorema binomial, perpangkatan berbentuk (x + y)n dapat dijabarkan dalam bentuk segitiga Pascal berikut ini :
(x + y)0 = 1 1
(x + y)1 = x + y 1 1
(x + y)2 = x2 + 2xy + y2 1 2 1
(x + y)3 = x3 + 3x2y + 3xy2 + y3 1 3 3 1
(x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4 1 4 6 4 1
(x + y)5 = x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5 1 5 10 10 5 1
Secara umum, diperoleh rumus sebagai berikut :
(x + y)n = C(n, 0) xn + C(n, 1) xn-1 y1 + … + C(n, k) xn-k yk + … + C(n, n) yn
= ?x=nkknC0),(n-k yk
Bilangan C(n, k) merupakan koefisien untuk xn-kyk dinamakan koefisien binomial.
Contoh :
Jabarkan (2x + y)3.
Jawab :
Misalkan a = 2x dan b = y,
(a + b)3 = C(3, 0) a3 + C(3, 1) a2b1 + C(3, 2) a1b2 + C(3, 3) b3
= 1 (2x)3 + 3 (2x)2 (y) + 3 (2x) (y)2 + 1 (y)3
= 8 x3 + 12x2 y + 6x y2 – y3
Contoh :

Jabarkan (2x – 3)3.
Jawab :
Misalkan a = 2x dan b = –3,
(a + b)3 = C(3, 0) a3 + C(3, 1) a2b1 + C(3, 2) a1b2 + C(3, 3) b3
= 1 (2x)3 + 3 (2x)2 (–3) + 3 (2x) (–3)2 + 1 (–3)3
= 8x3 – 36x2 + 54x – 27
Contoh :
Tentukan suku kelima dari penjabaran perpangkatan (x – y)5.
Jawab :
(x – y)5 = (x + (–y))5.
Suku kelima dari hasil penjabaran adalah:
C(5, 4) x 5 – 4 (–y)4 = –10 x y4.
Latihan :
Adiwijaya Sekolah Tinggi Teknologi Telkom 46 Matematika Diskrit

1. Tentukan nilai :

a. P(6, 3)

b. C(5, 1)

2. Berapa kali akan muncul string yang terdiri dari unsur pada abcdefgh yang memuat string abc pada string tersebut.


3. Berapa banyak string dengan panjang sepuluh yang mungkin terbentuk dari dua bit (0 dan 1), yang memuat angka satu tepat tujuh buah.


4. Dalam suatu pacuan kuda dengan 12 peserta (diasumsikan semuanya dapat mencapai finish), Berapa jumlah kemungkinan susunan pemenang (pertama,
kedua, dan ketiga) dalam pacuan tersebut.

5. Pada toko ‘duny donut’ menyediakan empat jenis donat dengan rasa yang berbeda (stok masing-masing rasa 10 buah). Berapa jumlah cara pengambilan, jika seseorang membeli donat tersebut enam buah.

6. Dengan menggunakan teorema binomial, tentukan :

a. koefisien x5y8 dalam (x + y)13

b. koefisien x7 dalam (1 + x)11

c. koefisien x9 dalam (1 – x)19

Adiwijaya Sekolah Tinggi Teknologi Telkom


BAB IV
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 :
Gambar 4.1. Masalah Jembatan Königsberg (Rossen, 2003)
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.
Gambar 4.2. Representasi graf masalah jembatan Königsberg
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. CABD

4.1 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).
Contoh :
Graf kosong dengan 3 simpul (graf N3 ) e2e3e4e5e6e7e1B A C D v1v2v3

Dengan memperhatikan kondisi sisinya, suatu graf dapat dikategorikan sebagai graf tidak berarah dan graf berarah. Graf tidak berarah, seperti telah dijelaskan pada contoh graf untuk jembatan Königsberg. Sementara itu, graf berarah (directed graph, digraph) merupakan graf yang mempunyai sisi yang berarah, artinya satu buah simpul yang dihubungkan oleh sisi tersebut merupakan simpul awal (initial vertex) dan simpul yang lain dikatakan sebagai simpul akhir (terminal vertex).
Contoh :
Graf berikut merupakan graf berarah :
Terlihat bahwa e1 = (P, S), e3 = (R, Q), dan e5 = (Q, Q)
Simpul P merupkan simpul awal bagi sisi e1 dan simpul S merupakan simpul akhir bagi sisi e1.
4.2 Terminologi Graf
Ada beberapa terminologi graf yang perlu diketahui, antara lain : ketetanggaan antara dua simpul, bersisian , derajat suatu simpul, dan lain-lain. Berikut ini adalah beberapa terminoogi yang penting, yaitu :
1. Bertetangga (Adjacent)
Dua buah simpul dikatakan bertetangga jika kedua simpul tersebut terhubung langsung oleh suatu sisi.
Contoh :
Perhatikan graf berikut :
Pada graf diatas : simpul P bertetangga dengan simpul Q dan S, tetapi
simpul P tidak bertetangga dengan simpul R.
2. Bersisian (Incidency)

P

S

Q

R

P

S

Q

R

e1

e6

e4

e3

e2

Suatu sisi e dikatakan bersisian dengan simpul v1 dan simpul v2 jika e menghubungkan kedua simpul tersebut, dengan kata lain e = (v1, v2).
Contoh :
Perhatikan graf dari masalah jembatan Königsberg berikut ini :
maka e1 bersisian dengan simpul A dan simpul C , tetapi sisi tersebut tidak berisian dengan simpul B.
3. Simpul Terpencil (Isolated Vertex)
Jika suatu simpul tidak mempunyai sisi yang bersisian dengannya maka simpul tersebut dinamakan simpul terpencil.
Contoh :
Perhatikan graf berikut :
Simpul T dan simpul U merupakan simpul terpencil.
5. 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 1:
Perhatikan graf berikut : P SQR TU e2e3e4e5e6e7e1BACD

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)
Contoh 2 :
Perhatikan graf berarah berikut ini :
Pada graf diatas :
din(P) = 1 dan dout(P) = 3 maka d (P) = 4
din(Q) = 4 dan dout(Q) = 1 maka d (Q) = 5
din(R) = 1 dan dout(R) = 1 maka d (R) = 2
din(S) = 1 dan dout(S) = 2 maka d (S) = 3
Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali jumlah sisi pada graf tersebut. Jika G = (V, E) merupakan suatu graf, maka dapat ditulis :
EvdVv2)(=??
Contoh 2 : PS QR PS QR

Perhatikan graf pada contoh 1. Jumlah sisi pada graf tersebut adalah 9, sehingga Jumlah derajat pada graf tersebut adalah :
189.2.2)(===??EvdVv
atau
183555)()()()()(=+++=+++=??SdRdQdPdvdVv
Perhatikan graf pada contoh 2.
Jumlah sisi pada graf tersebut adalah 7, sehingga Jumlah derajat pada graf tersebut adalah :
147.2.2)(===??EvdVv
atau
143254)()()()()(=+++=+++=??SdRdQdPdvdVv
Dengan demikian, jika kita ingin menggambar sebuah graf dengan derajat masing-masing simpul diketahui, dan ternyata jumlah derajat seluruh simpul tersebut adalah ganjil maka hal ini tak mungkin terjadi.
6. 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 : P S QR TU


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

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

(a) (b)

4.3 Beberapa Jenis Graf
Beberapa jenis graf tak berarah yang perlu diketahui adalah :
1. Graf sederhana (simple graph).
Graf sederhana merupakan graf tak berarah yang tidak mengandung gelang maupun sisi-ganda.
Contoh :
Graf sederhana PS QR 123456512436

2. Graf Ganda (multigraph).
Graf ganda merupakan graf tak berarah yang tidak mengandung gelang (loop).
Contoh :
Graf ganda
Dengan demikian, graf sederhana pun merupakan graf ganda (multi graph).
3. Graf semu (Pseudo graph)
Graf semu merupakan graf yang boleh mengandung gelang (loop).
Contoh :
Graf semu :
Beberapa jenis graf berarah yang perlu diketahui adalah :
1. Graf berarah (directed graph atau digraph).
Graf berarah merupakan graf yang setiap sisinya mempunyai arah dan tidak mempunyai dua sisi yang berlawanan antara dua buah simpul (tak mempunyai sisi ganda)
Contoh :
Graf berarah : P S QR P S QR PS Q

2. Graf ganda berarah (directed multigraph).
Graf ganda berarah merupakan graf berarah yang membolehkan adanya sisi ganda pada graf tersebut (boleh mempunyai dua sisi yang berlawanan antara dua buah simpul).
Contoh :
Graf ganda berarah :
Dari jenis-jenis graf yang telah dijelaskan di atas, kita dapat membuat ringkasan (sebagai bahan perbandingan), sebagai berikut :
Tabel 4.1 Jenis-jenis graf [Rosen, 2003]

Jenis     Sisi     Sisi ganda dibolehkan?     Gelang (loop) dibolehkan?       
Graf sederhana
Graf ganda
Graf semu
Graf berarah
Graf ganda berarah     Tak-berarah
Tak-berarah
Tak-berarah
Bearah
Bearah     Tidak
Ya
Ya
Tidak
Ya     Tidak
Tidak
Ya
Ya
Ya    


BAB V
P O H O N ( T R E E )
Pohon (tree) merupakan salah satu bentuk khusus dari struktur suatu graf. Misalkan A merupakan sebuah himpunan berhingga simpul (vertex) pada suatu graf G yang terhubung. Untuk setiap pasangan simpul di A dapat ditentukan suatu lintasan yang menghubungkan pasangan simpul tersebut. Suatu graf terhubung yang setiap pasangan simpulnya hanya dapat dihubungkan oleh suatu lintasan tertentu, maka graf tersebut dinamakan pohon (tree). Dengan kata lain, pohon (tree) merupakan graf tak-berarah yang terhubung dan tidak memiliki sirkuit.
Contoh :
Gambar 6.1 G1 dan G2 adalah pohon, sedangkan G3 dan G4 bukan pohon
Hutan (forest) merupakan kumpulan pohon yang saling lepas. Dengan kata lain, hutan merupakan graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung tersebut adalah pohon. Pada gambar 6. 1 G4 merupakan salah satu contoh hutan, yaitu hutan yang terdiri dari dua pohon.
Berikut adalah beberapa sifat pohon :

• Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi. Jika G tidak mempunyai sirkuit maka G merupakan pohon.

• Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi.

• Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal.

• Misalkan G adalah graf sederhana dengan jumlah simpul n, jika G tidak mengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuat satu sirkuit.
G1G2G3G4 a bc de f a bc de fabcdefab cd ef

5.1 Pohon Merentang Minimum (Minimum Spanning Tree)
Spanning Tree dari suatu graf terhubung merupakan subgraf merentang yang berupa pohon. Pohon merentang diperoleh dengan cara menghilangkan sirkuit di dalam graf tersebut.
Contoh spanning tree dari suatu graf terhubung (Munir, 2003) :
Perhatikan graf dibawah ini :
G T1 T2 T3 T4
Terlihat bahwa T1, T2, T3, T4 merupakan spanning tree dari graf G. Perlu diperhatikan bahwa setiap graf terhubung berbobot paling sedikit mempunyai satu buah spanning tree. Pohon rentang yang memiliki bobot minimum dinamakan pohon merentang minimum (minimum spanning tree). Dalam kehidupan nyata, salah satu contoh aplikasi spanning tree adalah menentukan rangkaian jalan dengan jarak total seminimum mungkin yang menghubungkan semua kota sehingga setiap kota tetap terhubung satu sama lain.
Dalam menentukan suatu minimum spanning tree dari suatu graf terhubung, kita dapat menentukannya dengan mengunakan dua cara yaitu algoritma Prim dan algoritma Kruskal.
Algoritma Prim memiliki langkah-langkah sebagai berikut :

1. Pilih sisi dari graf G yang berbobot minimum, masukkan ke dalam T.

2. Pilih sisi (u, v) dalam G yang mempunyai bobot minimum dan bersisian dengan simpul di T, dengan syarat sisi tersebut tidak membentuk sirkuit di T. Masukkan (u, v) ke dalam T.

3. ulangi langkah 2 sebanyak n – 2 kali.

Jumlah langkah seluruhnya dalam algoritma Prim adalah sebanyak jumlah sisi di dalam spanning tree dengan n buah simpul, yaitu (n – 1) buah.

Contoh :
Tentukan minimum spanning tree dari graf dibawah ini :
Jawab :

• Pilih sisi fg sehingga kita mempunyai T ({f, g}, fg)

• Langkah selanjutnya dapat dipilih sisi ef karena sisi tersebut berbobot minimum yang bersisian dengan simpul f .

• Selanjutnya pilih sisi ae atau gh karena sisi tersebut berbobot minimum yang bersisian dengan simpul pada T, yaitu e dan g.

Jika proses ini dilanjutkan terus maka akan diperoleh minimum spanning tree seperti dibawah ini :
Terlihat bahwa spanning tree tersebut mempunyai total bobot 2 + 3 + 4 + 4 + 4 + 4 + 3 = 24.
Langkah-langkah dalam algoritma Kruskal agak berbeda dengan algoritma Prim. Pada algoritma Kruskal, semua sisi dengan bobot yang minimal dimasukan kedalam T secara berurutan. a b cdef gh 5 5 445454323 4 a b cdef gh 444323 4

Langkah-langkah dalam menentukan minimum spanning tree dengan algoritma Kruskal adalah sebagai berikut :
Langkah I : T berbentuk seperti pohon berikut
Langkah II : memasukan sisi-sisi yang berbobot 3 kedalam sehingga T berbentuk
Langkah II : memasukan sisi-sisi yang berbobot 4 kedalam sehingga akhirnya
diperoleh minimum spanning tree berikut :

f

g

2

c

e

f

g

3

2

3 a b c def gh 444323 4

5.2 Pohon Berakar
Pada suatu pohon, yang sisi-sisinya diberi arah sehingga menyerupai graf berarah, maka simpul yang terhubung dengan semua simpul pada pohon tersebut dinamakan akar. Suatu pohon yang satu buah simpulnya diperlakukan sebagai akar maka pohon tersebut dinamakan pohon berakar (rooted tree). Simpul yang berlaku sebagai akar mempunyai derajat masuk sama dengan nol. Sementara itu, simpul yang lain pada pohon itu memiliki derajat masuk sama dengan satu. Pada suatu pohon berakar, Simpul yang memiliki derajat keluar sama dengan nol dinamakan daun.

a. Anak (child atau children) dan Orangtua (parent)
b, c, dan d adalah anak-anak simpul a,
a adalah orangtua dari anak-anak itu
b. Lintasan (path)
Lintasan dari a ke h adalah a, b, e, h. dengan pnjang lintasannya adalah 3.
f adalah saudara kandung e, tetapi, g bukan saudara kandung e, karena orangtua mereka berbeda.
c. Subtree
c. Derajat (degree)
Derajat sebuah simpul adalah jumlah anak pada simpul tersebut.
Contoh :
Simpul yang berderajat 0 adalah simpul c, f, h, I, j, l, dan m.
Simpul yang berderajat 1 adalah simpul d dan g.
Simpul yang berderajat 2 adalah simpul b dan k.
Simpul yang berderajat 3 adalah simpul a dan e. abkgjfcdmlieh abkgjfcdmlieh

Jadi, derajat yang dimaksudkan di sini adalah derajat-keluar.
Derajat maksimum dari semua simpul merupakan derajat pohon itu sendiri. Pohon di atas berderajat 3
d. Daun (leaf)
Simpul yang berderajat nol (atau tidak mempunyai anak) disebut daun. Simpul h, i, j, f, c, l, dan m adalah daun.
e. Simpul Dalam (internal nodes)
Simpul yang mempunyai anak disebut simpul dalam. Simpul b, d, e, g, dan k adalah simpul dalam.
f. Aras (level) atau Tingkat
g. Tinggi (height) atau Kedalaman (depth)
Aras maksimum dari suatu pohon disebut tinggi atau kedalaman pohon tersebut. Pohon di atas mempunyai tinggi 4.
Pohon berakar yang urutan anak-anaknya penting (diperhatiakn) maka pohion yang demikian dinamakan pohon terurut (ordered tree). Sedangka, pohon berakar yang setiap simpul cabangnya mempunyai paling banyak n buah anak disebut pohon n-ary. Jika n = 2, pohonnnya disebut pohon biner (binary tree).
Contoh :
Berikut adalah beberapa contoh pohon biner :

1. Pohon Ekspresi
Ekspresi aritmetika (a – b)*((c + d) / e) dapat dinyatakan dalam suatu pohon biner, dimana peubah sebagai daun dan operator aritmetika sebagai simpul dalam dan akar.

2. Pohon keputusan (Munir, 2004)

Pohon keputusan untuk mengurutkan 3 buah elemen

3. Kode awalan (prefix code)
Kode awalan merupakan himpunan kode (salah satunya adalah kode biner) sedemikian sehingga tidak ada anggota himpunan yang merupakan awalan dari
kode yang lain.
Contoh :

a. { 001, 010, 011, 11,} merupakan kode awalan

b. {001, 010, 01, 111} bukan merupakan kode awalan, karena 01 merupakan awalan dari 010.

Kode awalan (a) dapat dinyatakan dalam pohon biner, yaitu :
a : ba : cb : cb : cc > a > ba : cc > b > ba > b > ca > c > bb > a > cb > c > a
Adiwijaya Sekolah Tinggi Teknologi Telkom 82 Matematika Diskrit
4. Kode Hufman
Dalam komunikasi data, seringkali ditemukan data berukuran besar sehingga waktu pengiriman data tersebut menjadi lama. Hal ini menyebabkan pentingnya kompresi data dengan tujuan memperkecil ukuran data tersebut. Kode Hufman merupakan salah satu metode pengkodean dalam hal kompresi data.   


BAB VI
PEWARNAAN GRAF
6.1 Pewarnaan Simpul
Pewarnaan dari suatu graf G merupakan suatu pemetaan dari sekumpulan warna ke beberapa simpul (vertex) yang ada pada graf G sedemikian sehingga simpul yang bertetangga memiliki warna yang berbeda.
Suatu graf G dikatakan berwarna n jika terdapat n warna dalam pewarnaan graf G tersebut. Jumlah warna minimum yang diperlukan dalam pewarnaan suatu graf dinamakan bilangan kromatik, yang dinotasikan oleh )(G? (? : dibaca chi).
Contoh :
Bilangan kromatik suatu graf lengkap-n (Kn) adalah n. Hal ini disebabkan karena setiap simpul pada graf lengkap adalah bertetangga. Jadi ?(Kn) = n.
Perhatikan graf lengkap dengan 5 simpul berikut ini :
maka untuk mewarnai graf tersebut diperlukan 5 warna.
Algoritma Welch-Powell dalam pewarnaan sutau graf G dapat diilustrasikan sebagai berikut :

• Urutkan semua simpul pada graf G berdasarkan derajat masing-masing simpul, dari besar menjadi kecil. Urutan tersebut tidak unik karena beberapa simpul mungkin mempunyai derajat yang sama.

• Gunakan warna pertama untuk mewarnai simpul pertama dan simpul lain yang berada pada urutan sepanjang simpul tersebut tidak bertetangga dengan simpul sebelumnya.

• Berikan warna kedua untuk mewarnai simpul pada urutan tertinggi (yang belum diwarnai), lakukan seperti point sebelumnya.

• Seperti point ketiga, dilakukan terus menerus sehingga setiap simpul pada graf tersebut menjadi berwarna semua.

Algoritma Welch-Powell hanya memberikan batas atas untuk bilangan kromatik. Dengan demikian, algoritma ini tidak selalu memberikan jumlah warna minimum yang diperlukan dalam pewarnaan graf. a b c d e

Pewarnaan pada graf tersebut dapat dilakuakn dengan menggunakan dua warna, yaitu :

• Warna I untuk simpul a, b, c

• Warna II untuk simpul d, e, f

Sementara itu, jika kita ingin membuat suatu sirkuit pada graf tersebut, maka sirkuit tersebut akan melewati 3 atau 5 simpul yang lain sebelum kembali ke simpul awal. Sehingga sirkuit tersebut memiliki panjang yang genap a b c d e f a b d e f

6.2 Pewarnaan Graf Planar
Definisi Daerah pada suatu Graf Planar
Sebelum membahas tentang pewarnaan daera pada suatu graf planar, perhatikan beberapa definisi yang akan disampaikan terkait dengan graf planar berikut ini:
Area r1, r2, r3, r4, dan r5 dinamakan daerah (region) dari graf planar tersebut. Dua buah daerah dalam suatu graf planar dikatakan bertetangga jika mereka paling sedikit mempunyai sebuah sisi bersama.