KUMPULAN TUGAS - TUGAS MATEMATIKA DISKRIT

( Pk. Sugiartawan )


Materi Himpunan

Materi Logika

Materi Graf

Materi Pohon ( Tree )


- Tugas Jaringan Komputer ( " Pk. Ngurah semadi ")



Nama : Leo Christy
Nim : 09101303
email : Christyleo@ymail.com

SEKOLAH TINGGI ILMU KOMPUTER INDONESIA

DENPASAR

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.

Tugas Matematika Diskrit

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.

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 :

1. Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi. Jika G tidak mempunyai sirkuit maka G merupakan pohon.
2. Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi.
Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal.Misalkan G 3.adalah graf sederhana dengan jumlah simpul n, jika G tidak mengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuat satu sirkuit.



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.

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.

Pada pohon berakar diatas :
• a merupakan akar
• c, d, f, g, h, i, dan j merupakan daun
Terminologi pada Pohon Berakar.
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. 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.
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).


2. Pohon keputusan

Tugas Matematika Diskrit

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.


Contoh 4 :
(i) N ⊆ Z ⊆ R ⊆ C
(ii) {2, 3, 5} ⊆ {2, 3, 5}
Untuk setiap himpunan A berlaku hal-hal sebagai berikut:
(a) A adalah himpunan bagian dari A itu sendiri (yaitu, A ⊆ A).
(b) Himpunan kosong merupakan himpunan bagian dari A ( ∅ ⊆ A).
(c) Jika A ⊆ B dan B ⊆ C, maka A ⊆ C
∅ ⊆ A dan A ⊆ A, maka ∅ dan A disebut himpunan bagian tak sebenarnya (improper subset) dari himpunan A. Pernyataan A ⊆ B berbeda dengan A ⊂ B :
A ⊂ B : A adalah himpunan bagian dari B tetapi A ≠ B.
Yang demikian, A merupakan himpunan bagian sebenarnya (proper subset) dari B.

Contoh 5 :
Misalkan A = {1, 2, 3}.
{1} dan {2, 3} merupakan proper subset dari A.
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 6 :
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 7 :
(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 },
maka A = B
(iii) Jika A = { 3, 5, 8, 5 } dan B = {3, 8},
maka A ≠ B
Untuk tiga buah himpunan, A, B, dan C berlaku aksioma berikut:
(a) A = A, B = B, dan C = C
(b) Jika A = B, maka B = A
(c) Jika A = B dan B = C, maka A = C

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

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 }
b. Gabungan (union)
Gabungan antara dua buah himpunan dinotasikan oleh tanda ‘∪‘.
Misalkan A dan B adalah himpunan, maka
A ∪ B = { x | x ∈ A atau 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 }
d. Selisih (difference)
Selisih antara dua buah himpunan dinotasikan oleh tanda ‘– ‘.
Misalkan A dan B adalah himpunan, maka selisih A dan B dinotasikan oleh
A – B = { x | x ∈ A dan x ∉ B } = A ∩ B
e. Beda Setangkup (Symmetric Difference)
Beda setangkup antara dua buah himpunan dinotasikan oleh tanda ‘ ⊕ ‘.
Misalkan A dan B adalah himpunan, maka beda setangkup antara A dan B dinotasikan
oleh :
A ⊕ B = (A ∪ B) – (A ∩ B)
= (A – B) ∪ (B – 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 }


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

Tugas Matematika diskrit,..

Logika
Logika merupakan dasar dari semua penalaran
(reasoning).
Penalaran didasarkan pada hubungan antara
pernyataan (statements).
Proposisi
Pernyataan atau kalimat deklaratif yang bernilai
benar (true) atau salah (false), tetapi tidak
keduanya.

Contoh

“Gajah lebih besar daripada tikus.”

Apakah ini sebuah pernyataan? YA
Apakah ini sebuah proposisi? YA
Apakah nilai kebenarandari proposisi ini? Benar

“y > 5”
Apakah ini sebuah pernyataan? YA
Apakah ini sebuah proposisi? TIDAK

Nilai kebenaran dari pernyataan tersebut
bergantung pada y, tapi nilainya belum
ditentukan.
Pernyataan jenis ini kita sebut sebagai
fungsi proposisi atau kalimat terbuka.

Contoh 2.
Semua pernyataan di bawah ini
bukan proposisi
(a) Jam berapa kereta api Argo Bromo tiba
di Gambir?
(b) Isilah gelas tersebut dengan air!
10
(c) x + 3 = 8
(d) x > 3
Kesimpulan: Proposisi adalah kalimat berita,...

Mengkombinasikan Proposisi
Misalkan p dan q adalah proposisi.
1. Konjungsi (conjunction): p dan q
Notasi p Ù q,
2. Disjungsi (disjunction): p atau q
Notasi:p Ú q
3. Ingkaran (negation) dari p: tidak p
Notasi: ~p
• p dan q disebut proposisi atomik
• Kombinasi p dengan q menghasilkan proposisi majemuk


Contoh tabel Kebenaran

Contoh . Misalkan,.. :
p : 17 adalah bilangan prima (benar)
q : bilangan prima selalu ganjil (salah)
p Ù q : 17 adalah bilangan prima dan bilangan prima
selalu ganjil (salah)
Hukum - Hukum Logika

1. Hukum identitas:
- p Ú F Û p
- p Ù T Û p

2. Hukum null/dominasi:
- p Ù F Û F
- p Ú T Û T

3. Hukum negasi:
- p Ú ~p Û T
- p Ù ~p Û F

4. Hukum idempoten:
- p Ú p Û p
- p Ù p Û p

5. Hukum involusi (negasi ganda):
- ~(~p) Û p

6. Hukum penyerapan(absorpsi):
- p Ú (p Ù q) Û p
- p Ù (p Ú q) Û p

7. Hukum komutatif:
- p Ú q Û q Ú p
- p Ù q Û q Ù p

8.Hukum asosiatif:
- p Ú (q Ú r) Û (p Ú q) Ú r
- p Ù (q Ù r) Û (p Ù q) Ù r

9. Hukum distributif:
- p Ú (q Ù r) Û (p Ú q) Ù (p Ú r)
- p Ù (q Ú r) Û (p Ù q) Ú (p Ù r)

10. Hukum De Morgan:
- ~(p Ù q) Û ~p Ú ~q
- ~(p Ú q) Û ~p Ù ~q



Contoh .
Tunjukkan bahwa p Ú ~(p Ú q) dan p Ú ~q
keduanya ekivalen secara logika.
Penyelesaian:

p Ú ~(p Ú q ) Ûp Ú (~p Ù ~q) (Hukum De ogran)
Û(p Ú ~p) Ù (p Ú ~q) (Hukum distributif)
ÛT Ù (p Ú ~q) (Hukum negasi)
Ûp Ú ~q (Hukum identitas)

TUGAS JARINGAN KOMPUTER

Masih Banyak lagi dan berbagai macam merk,.
Jika anda berminat bertanya ataupun tertarik untuk memesan
anda bisa menghubungi kami di
+85739712577
atau
kirimkan pesanan anda di
email : christyleo@ymail.com


Ingat !!!! Berhati - hatilan dan telitilah dalam berbelanja,..

Terima kasih dan Tuhan memberkati,..

Dan banyak lagi, bukan hanya laptop atau P

" Kata - kata bijak dalam kehidupan :

Belajar ,...........
Ok,.. Mengapa,...????

1. Kita tentu sering mengalami masalah,..
2. Dari keadaan yang kita jalani sekarang ,.

ok sampai situ dulu,......

Kita engga boleh yang namanya mengeluh pada saat masalah itu datang apalagi dalam penyelesaiannya membuat kita hampir stress,..
kenapa,............................???


masalah itu bagaikan tamu , ya ,... , karena tamu itu datang dan tentu pastinya akan pergi juga kan,..

Nah dari situ kita bisa tarik kesimpulan kalau setiap masalah datang pasti juga akan pergi / terselesaikan tergantung dari cara kita mengahadapi masalah itu,..

tentu dengan hati lapang dan penuh perhatian, dan satu yang perlu yaitu sebagai bahan pelajaran kehidupan untuk menghadapi masalah lagi nantinya




Nah untuk yang kedua ,...
kita engga boleh yang namanya puas dengan keadaan karena setiap waktu keadaan kita selalu berubah, jadi kita harus belajar dari keaadaan sebelumnya untuk belajar, mengubah keaadaan yang sebelumnya untuk menjadi yang terbaik tentunya buat kemuliaan Tuhan yang utama dan Orang yang kita sayang,...

dan jangan lupa juga buat orang " disekitar kita,...



Lagu" Rohani

Mujizat itu nyata