TUGAS MANDIRI 3 MATEMATIKA DISKRIT

NAMA: AYU LESTARI BR GINTING

KELAS: PAGI

JURUSAN: SISTEM INFORMASI

A.) buat lh 3 contoh soal dan penyelesaian tabel kebenaran (buat yg sederhana saja)

Jb.

2). Jelaskan konsep dari matematika graf yang sudah kalian pelajari dan buat contohnya

Jb.

Teori graf adalah salah satu cabang matematika yang terus berkembang dengan pesat. Teori ini sangat berguna untuk mengembangkan model-model  terstruktur dalam berbagai keadaan. “Struktur-struktur yang terdiri atas kumpulan  objek-objek yang berkaitan satu sama lain dapat dibuat modelnya dengan sebuah  

graf, dengan simpul sebagai representasi objeknya, dan sisi sebagai representasi kaitan atau hubungan di antara objek itu” (Kusumah, 1998 : 1).  “Sebuah graf adalah sebuah himpunan terhingga tak kosong yang memuat  

objek-objek yang disebut simpul dan himpunan pasangan tak urut antara simpul- simpul yang berlainan yang disebut sisi” (Kusumah, 1998 : 8). Teori graf sering digunakan dalam studi tentang jaringan transportasi,  

jaringan komunikasi, jaringan listrik, struktur senyawa kimia, pewarnaan peta, desain arsitektur, penjodohan dan bidang yang lainnya. Perkembangan teori graf  

tidak terlepas dari permasalahan-permasalahan yang harus dipecahkan pada berbagai bidang tersebut, bahkan seringkali sebuah teori lahir dari suatu  permasalahan sederhana yang selanjutnya berkembang dengan pesat menjadi teori yang mapan.

~Graf~

Definisi Graf

Suatu graf (graph) G adalah sebuah pasangan tak-terurut dari V dan E;

yaitu G = {V(G), E(G)} = {V, E}dengan :

1. V adalah himpunan simpul (vertex).

2. E adalah himpunan sisi (edge); yaitu pasangan (tak-terurut) dari dua

simpul (Kusumah, 1998 : 8).

Mulai saat ini dan seterusnya dalam makalah ini, istilah “simpul” akan

diganti dengan “titik” dan “sisi” akan diganti dengan “garis”. Penggantian istilah

ini karena dalam kehidupan nyata istilah “titik” dan “garis” lebih sering

digunakan dari pada istilah “simpul” dan “sisi”. Dengan begitu orang yang belum

pernah belajar atau baru belajar teori graf akan mudah memahami.

Definisi Orde

Orde dari graf G, ditulis |V(G)| = n, adalah banyaknya titik pada graf.

Definisi 3Ukuran

Ukuran dari graf G, ditulis |E(G)| = m, adalah banyaknya garis pada graf.

Definisi Derajat

Derajat dari suatu titik pada graf G adalah banyaknya titik lain yang terhubung

(secara langsung) ke titik tersebut.

Definisi Titik Ujung

Dua titik pada graf yang dihubungkan oleh suatu garis disebut titik-titik ujung

(Bondy and Murty, 1976: 3).

 

Definisi  Insiden

Suatu garis dan suatu titik sebagai titik ujung pada garis tersebut dikatakan saling

berinsiden atau bersentuhan (Bondy and Murty, 1976: 3).

Definisi Garis Ajasen

Dua garis pada graf dikatakan saling berajasen atau bertetangga (secara

langsung) jika kedua garis tersebut berinsiden dengan satu titik yang sama

(Bondy and Murty, 1976: 3).

Definisi Titik Ajasen

Dua titik pada graf dikatakan saling berajasen atau bertetangga (secara

langsung) jika kedua titik tersebut berinsiden dengan satu garis yang sama

(Bondy and Murty, 1976: 3). 

Penyajian Graf

Graf dapat disajikan dalam 3 cara yang berlainan, yaitu dengan

menggunakan himpunan pasangan tak-terurut, diagram dan matriks. Sebuah graf

yang dinyatakan dalam bentuk himpunan dapat dinyatakan dalam bentuk diagram

atau matriks, dan sebaliknya.

Bentuk Diagram

Dalam bentuk diagram, setiap titik pada graf digambarkan dengan sebuah

lingkaran kecil dan setiap garis pada graf digambarkan dengan segmen garis yang

menghubungkan 2 titik.

Diameter lingkaran, terisi atau kosong di bagian dalam lingkaran, panjang

segmen garis serta kelengkungan segmen garis tidak perlu diperhatikan atau

dipermasalahkan.

Bentuk Himpunan

Dalam bentuk notasi himpunan, sebuah graf dinyatakan dengan pasangan

terurut dari dua himpunan; yaitu himpunan titik dan himpunan garis. Himpunan

garisnya merupakan kumpulan dari pasangan tak-terurut dari dua titik.

Contoh :

Graf G = {V, E} dengan V = {u, v} dan E = {e = (u, v)}.

Bentuk Matriks

Matriks yang digunakan untuk menyajikan sebuah graf adalah matriks

ajasensi (adjacency matrix) dan matriks insidensi (incidence matrix).

Definisi Matriks Ajasensi

Matriks ajasensi A(G) = [ajk] dari sebuah graf G didefinisikan dengan

ajk

ajk = 1 , jika (vj

, vk) E(G)

ajk = 0 , jika (vj

, vk) E(G)

Definisi  Matriks Insidensi

Matriks insidensi I(G) = [ijk] dari sebuah graf G didefinisikan dengan

ijk

ijk = 1 , jika garis j berinsiden dengan titik k

ijk = 0 , jika garis j tidak berinsiden dengan titik k

 

Pelabelan Pada Graf

Pelabelan pada graf adalah pemberian kode pada komponen graf, yaitu

titik dan garis. Pelabelan pada graf biasanya menggunakan warna.

Definisi 3.11 Pewarnaan Sejati (Proper Colouring)

Titik-titik atau garis-garis yang saling ajasen tidak diperbolehkan diberi kode yang

sama :

1. vi

 dan vj

 saling ajasen dengan i, j = 1, 2, 3, … , n ; i j dan | V | = n maka

tidak diperbolehkan cvi

 = cvj

.

2. ei

 dan ej

 saling ajasen dengan i, j = 1, 2, 3, … , m ; i j dan |E| = m maka

tidak diperbolehkan cei

 = cej

 (Bondy and Murty, 1976: 91).

cvi

 dan cvj

 adalah code warna pada vi

 dan vj

. Pewarnaan Tak Sejati (Improper Colouring)  

Titik-titik atau garis-garis yang saling ajasen diperbolehkan diberi kode yang

sama :

1. vi

 dan vj

 saling ajasen dengan i, j = 1, 2, 3, … , n ; i j dan | V | = n maka

diperbolehkan cvi

 = cvj

.

2. ei

 dan ej

 saling ajasen dengan i, j = 1, 2, 3, … , m ; i j dan |E| = m maka

diperbolehkan cei

 = evj

 (Bondy and Murty, 1976: 91).

cvi

 dan cvj

 adalah code warna pada vi

 dan vj

.Definisi 1

Bilangan kromatik titik (G) menyatakan total warna minimum untuk mewarnai

titik-titik dengan syarat dua titik yang berajasen harus mempunyai warna yang

berbeda (Bondy and Murty, 1976: 117).

Definisi 2

Bilangan kromatik garis ’(G) menyatakan total warna minimum untuk mewarnai

garis-garis dengan syarat dua garis yang berajasen harus mempunyai warna yang

berbeda (Bondy and Murty, 1976: 91).