02. risasi febriani ganda (matdis)

7/26/2019 02. Risasi Febriani Ganda (Matdis)

1/7

Tugas Individu 2: Matematika Diskrit

KUMPULAN 6 SOAL MATEMATIKA DISKRIT

MATERI KELOMPOK I SAMPAI KELOMPOK VI

Disusun Oleh:

Risasi Febriani Ganda

201284202006

Kelas / Semester : A (Pagi) / IV (Empat)

Dosen Pembimbing : Kamariah, S.Pd., M.Pd.

PROGRAM STUDI MATEMATIKA

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

UNIVERSITAS MUSAMUS MERAUKE

TAHUN 2014


2/7

Tugas Matematika Diskrit Page 2

Kelompok 1 (Terminologi Graf)

Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang

mempunyai 16 buah sisi dan tiap simpul berderajat sama dan tiap simpul

berderajat 4 ?

Jawab :

Tiap simpul berderajat sama, itu artinya graf teratur.

Jumlah sisi pada graf teratur berderajat radalah e = nr/2.

Jadi, n = 2e/r = (2)(16)/r = 32/r.

Untuk r = 4, jumlah simpul yang dapat dibuat adalah maksimum, yaitu

n = 32/4 = 8.

Untuk ryang lain (r > 4dan r merupakan pembagi bilangan bulat dari 32):

328 8 (tidak mungkin membentuk graf sederhana)

4

3216 2 (tidak mungkin membentuk graf sederhana)16

r n

r n

Jadi, jumlah simpul yang dapat dibuat adalah 8 buah (maksimum dan

minimum).

Anonim. 2013. (Online). (http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2011-2012/Graf.ppt,

diakses pada tanggal 4 Juni 2014)


3/7


Kelompok 2 (Graf Isomorfik)

Diketahui matriks ketetanggaan (adjacency matrices) dari sebuah graf tidak

berarah. Gambarkan dua buah graf yang yang bersesuaian dengan matriks

tersebut!

Jawab :

Anonim. (Online). (http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2011-2012/Graf.ppt,

diakses pada tanggal 4 Juni 2014)

01011

10110

01110

11101

10010

1

1

2 3

3

455 4

2


4/7


Kelompok 3 (Sirkuit Hamilton)

Tentukan dua lingkaran Hamilton berbeda pada graf di bawah ini!

Jawab :

Untuk menunjukan lingkaran Hamilton dalam sebuah graf di atas maka kita beri

label terlebih dahulu setiap titik pada graf tersebut seperti yang tampak di bawah

ini:

Berikut ini dua lingkaran Hamilton berbeda pada graf B :

(l, h, i, d, c, b, a, j, k, g, f, e, l) dan (i, h, g, f, e, l, b, a, j, k, c, d, i)

Anonim. (Online). (http://mathedu08.files.wordpress.com, diakses pada tanggal 4 Juni 2014)


5/7


Kelompok 4 (Tukang POS)

Perhatikan graph bobot G pada gambar di atas merepresentasikan suatu jaringan

jalan di sekitar kantor pos tertentu. Misalkan titik v1merepresentasikan kantor pos

dan v10 adalah tempat tujuan pengantar pos tersebut. Tentukan rute jalan

terpendek yang harus dilaluitukang pos tersebut!

Jawab :

Rute jalan terpendek yang sebaiknya dilalui oleh tukang pos adalah sebagai

berikut.

Nico. 2013. (Online). (http://elnicovengeance.wordpress.com/2011/08/18/mencari-jarak-minimum-

pada-graph-semi-euler/, diakses pada tanggal 4 Juni 2014)


6/7


Kelompok 5 (Pohon Rentang)

Gambarlah semua pohon rentang dari graf sedehana padagambar berikut ini!

Jawab :

1.

Dari graf G diatas dapat dihilangkan jalur ab untuk merusak sikel a,b,c,a

sehingga dihasilkan pohon rentang seperti gambar (i) .

2.

Dari graf G diatas dapat dihilangkan jalur ac untuk merusak sikel a,c,b,a

sehingga dihasilkan pohon rentang sepertigambar (ii) .

3. Dari graf G diatas dapat dihilangkan jalur bc untuk merusak sikel b,c,a,b

sehingga dihasilkan pohon rentang sepertigambar (iii) .

Meiva Marthaulina Lestari.2013. (Online). (http://www.scrib.com/doc/94105259/Latihan-Soal-

Pohon-dan -Graf-Matematika-Diskrit), diakses pada tanggal 4 Juni 2014)

a

bc

a

cb

a

b c

a

b c
http://www.scribd.com/meiva_lestarihttp://www.scribd.com/meiva_lestari


7/7


Kelompok 6 (Pohon Ekspresi)

Gambarkan pohon ekspresi dari notasiprefixberikut:

+^ a b^ 2 c/ 6b a

lalu tuliskan ekspresipostfixdan infixyang bersesuaian.

Jawab :

+

- /

^ ^ 6 -

a b 2 c b a

Ekspresi postfix dan infix masing-masing diperoleh dengan melakukan traversal

secarapostorderdan inorder:

Postfix: a b^ 2 c^6 b a/ +

Infix : (( a^ b)( 2 ^ c)) + (6 / ( ba ))

Anonim. 2013. (Online). (http://informatika.stei.itb.ac.id, diakses pada tanggal 4 Juni 2014)

02. risasi febriani ganda (matdis)

Documents