Tugas Matdis


Tugas Dan tugas..maap kalo p[ostnya acak acakan ini tugas yang deadlinenya 2 jam pas di kumpulin masa pengerjaan 3 hari sedangkan saya banyak kerjaan dan persiapan buat lomba web T_T..kacau seperti pikiran saya pengen tidur cape abis dari lomba web harus ngerjain tugas hha

Nama                    : Seftian Setia P

Nim                        : 10108409

Kelas                     : IF-06

Tugas                    : Graf/Matematika Diskrit

  1. Dik : 7 buah stasiun tv yang berjarak >= 150 km yang boleh beroperasi pada saluran UHF

Dit : a) Gambarkan graf yang memodelkan persoalan ini, b) planar/tidak?, c) derajat?

Jwb :

b) Bukan Graf Planar

c) D(1) = 4  , d(2) = 2 , d(3) = 4, D(4) = 4  , d(5) = 3 , d(6) = 4, d(7) = 4

  1. Gambarkan 3 buah graf yang isomorfik yang bersesuaian dengan matrik ketetanggaan diatas?

2                                                       4                                                                        5

1                                             3

4                          5                                                 1                                         3   3

2

1                                                    2                                                                               2

3                                                                      1                  3

4

5

4                                                                                                 5

  1. Dengan persamaan euleur kita harus mencar n,e dan f

Jumlah simpul = n , jumlah sisi = e , jumlah wilayah = f

.n =6 , e=12 .. n – e + f = 2 à 6 – 12 + f = 2 à f = 8

E <=  3n – 6 à 12 <= 12 betul tetapi bukan graf planar maka dibuat asumsi baru dengan dibatasi  4 buah sisi e <= 2n – 4 à 11 <= 8 saah maka BUKAN GRAF PALANAR.

  1. Tidak ismorfik dengan 4 simpul

1                                           1                           2                                   1                                     2

2

3                                                      4                     3                                    4                                     3

4

1                                                                  1                            2                                      2

2                        3                                                                                               1                                  3

4

4                          3                                            4

1                                              2                      1                        2                       1                                     2                   1           2

4                                             3                                                                                                                                           34333

4                          3                     4                                          3            4               3

  1. Jumlah 13 sisi dan tiap simpul berderajat 2, berarti e = 13

2 * jumlah sisi = Total Derajat à 2 * 13 = 26

Lemma jabat tangan:  = 2│E

= 2 . 13 = 26

Setiap simpul berderajat sama yaitu berderajat r, dan jika n adalah jumlah simpul pada graf tersebut, maka: nr = 26

Jumlah simpul pada graf sederhana tersebut adalah

n = 26 / r,             r  > 0 dan r Î Z positif dan habis membagi 26

  • Untuk r = 1, maka n = 26; akan terbentuk graf tidak terhubung yang masing-masing simpulnya berderajat 1, jumlah sisinya adalah 26/2 = 13 (memenuhi)
  • Untuk r = 2, maka n = 26, akan terbentuk graf lingkaran dengan sisi 13 (memenuhi)
  • Untuk r = 3, 6, 7, 9 tidak mungkin sebab hasil pembagian (26/r) tidak bulat.
  • Untuk r > 2, maka graf sederhana dapat terbentuk jika jumlah sisinya kecil dari jumlah sisi  graf lengkap dengan derajat r. Jika lebih maka graf tersebut bukanlah graf sederhana.

r (derajat)

n (simpul)

Maksimum sisi yang diizinkan agar terbentuk graf sederhana

Keterangan

4

10

10.9 / 2 = 45

Memenuhi sebab 13 ≤ 45

5

8

8.7 / 2 = 28

Memenuhi sebab 13 ≤ 28

8

5

5.4 / 2 = 10

Tidak memenuhi sebab 13 > 10

10

4

4.3 / 2 = 6

Tidak memenuhi 13 > 6

*) Untuk r yang lebih besar lagi tidak akan mungkin lagi terbentuk graf sederhana sebab jumlah simpulnya akan lebih kecil sehingga maksimum sisi yang diizinkan juga semakin kecil.

Jadi r yang memenuhi adalah {1, 2, 4, 5}, dan jumlah simpul di dalam graf adalah {40, 20, 10, 8}.

  1. Jumlah sisi 16 dan tiap simpul berderajat sama

Lemma jabat tangan:  = 2│E

= 2 . 16 = 32

Setiap simpul berderajat sama yaitu berderajat r, dan jika n adalah jumlah simpul pada graf tersebut, maka: nr = 32

Jumlah simpul pada graf sederhana tersebut adalah

n = 32 / r,             r  > 0 dan r Î Z positif dan habis membagi 32

  • Untuk r = 1, maka n = 32; akan terbentuk graf tidak terhubung yang masing-masing simpulnya berderajat 1, jumlah sisinya adalah 32/2 = 16 (memenuhi)
  • Untuk r = 2, maka n = 16, akan terbentuk graf lingkaran dengan sisi 16 (memenuhi)
  • Untuk r =   5, 7, 9 tidak mungkin sebab hasil pembagian (32/r) tidak bulat.
  • Untuk r > 2, maka graf sederhana dapat terbentuk jika jumlah sisinya kecil dari jumlah sisi  graf lengkap dengan derajat r. Jika lebih maka graf tersebut bukanlah graf sederhana.

r (derajat)

n (simpul)

Maksimum sisi yang diizinkan agar terbentuk graf sederhana

Keterangan

3

10

10.9 / 2 = 45

Memenuhi sebab 16 ≤ 45

4

8

8.7 / 2 = 28

Memenuhi sebab 16 ≤ 28

6

5

5.4 / 2 = 10

Tidak memenuhi sebab 16  > 10

8

4

4.3 / 2 = 6

Tidak memenuhi 16 > 6

*) Untuk r yang lebih besar lagi tidak akan mungkin lagi terbentuk graf sederhana sebab jumlah simpulnya akan lebih kecil sehingga maksimum sisi yang diizinkan juga semakin kecil.

Jadi r yang memenuhi adalah {1, 2, 3,4, }, dan jumlah simpul di dalam graf adalah

psuing pusing tuh hha

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s