MATA KULIAH : MATEMATIKA DISKRIT

Materi Kuliah

1. Teori Himpunan2. Relasi & Fungsi3. Induksi Matematik4. Aljabar Boolean5. Graph

Referensi :

1. Matematika Diskrit Richard Johnson Baugh2. Dasar-Dasar Matematika Diskrit C.L. Liu3. Matematika Diskrit Rinaldi Munir

Bab I : Teori Himpunan

1.1. Definisi

Himpunan (set) adalah Kumpulan objek-objek yang berbeda

1.2. Penyajian Himpunan

a. Enumerati Menuliskan semua elemen himpunan dalam tanda kurung kurawal Contoh : Himpunan B berisi lima buah bilangan genap positip Pertama B={2, 4,6,8,10 }b. Simbol-Simbol Baku Memakai Simbol-Simbol baku yang terdapat pada Himpunan

C. Notasi Pembentuk HimpunanHimpunan di tulis dengan syarat yang harus dipenuhi anggotanyaNotasi : { x | syarat yang harus dipenuhi oleh x }

Contoh :A adalah himpunan bilangan bulat positip yang kecil dari 5A = { x | x P, x < 5 }

D. Diagram Venn Menyajikan himpunan secara grafisMis : = { 1,2 …, 6, 8 } A = { 1,,3,4,5 } B = {1, 2,,6,8 }

13

86

25

74

A B

U

1.3. KardinalitasKardinalitas adalah jumlah elemen sebuah himpunanNotasi : n ( A ) atau | A |ContohB = { x | x bilangan prima yang lebih kecil dari 20 }| B | = 8Karena B = { 2, 3, 5, 7, 11, 13, 17, 19 }

1.4. Himpunan KosongHimpunan yang tidak memiliki satupun elemen atau himpunan dengan kardinal = 0

Notasi : ø atau { }Contoh :P = himpunana orang Indonesia yang pernah ke bulan

n(P) = ø atau n(P) = { }

1.5. Himpunan Bagian (Subset)Himpunan A di katakan himpunan bagian dari himpunan Bjika dan hanya jika setiap elemen A merupakan elemen dari BNotasi : A BContoh :{ 1, 2, 3 } { 1, 2, 3, 4, 5 }

1.6. Himpunan yang samaHimpunan A diketahui sama dengan himpunan B jika danhanya jika setiap elemen A merupakan elemen B dan sebaliknya.Notasi : A = B A B B AContoh :Jika A = {0,1} dan B = {xx (x-1) = 0} maka A = B

1.7 Himp. Yang EkivalenHimp. A dikatakan ekivalen dengan himp. B jika dan hanya jika bil. kardinalnya sama.Notasi : A ~ B A = B ContohJika A = { 1, 3, 5, 7 } dan B = { a, b, c, d }maka A ~ B

1.8 Himp. Saling lepas (disjoint)Dua himp A, B dikatakan disjoint jika keduanya tidak memiliki elemen yang sama.Notasi : A // BContoh :Jika A = { x / x P, x < 8} B = { 10, 20, 30, …….}Maka A // B

1.9 Himpunan Kuota ( Power Set ) Suatu himpunan yang elemennya semua himpunan bagian dari A termasuk himpunan kosong dan himpunan A sendiriNotasi : P(A) atau 2AContoh :

Jika A = {1, 2} maka P(A) = {ø ,{1}, {2}1.10. Operasi terhadap Himpunan a. Irisan

A B = { x | x єA x єB } b. Gabungan

A B = { X | X є A x є B } c. Komplemen

A = { x | x є x є A }

d. Selisih

A - B = { x | x є A dan x є B } = A B

c. Beda setangkup ( Symmetric Difference ) A B = ( A B ) - (A B ) = ( A - B ) ( B - A )

f. Perkalian Cortesian

A x B = { (a,b) | a є A b є B }

I.11 Sifat Operasi Himpunan 1. Hukum Identitas 2. Hukum Null

- A ø = A - A ø = ø - A = A - A =

- A ø = A - A A = ø 3. Hukum Komplemen 4. Hukum Idempoten - A A = - A A = A

- A A = ø - A A = A 5. Hukum Involusi 6. HukumPenyerapan - ( A ) = A - A (A B) = A

- A (A B ) = A

7. Hukum Komutatif 8. Hukum Assosiatif - A B = B A - A (B C) = (A B) C - A B = B A - A (B C) = (A B) C - A B = B A - A (B C) = (A B) C 9. Hukum Distributif 10. Hukum De Morgan - A (B C) = (A B) - A B = A B (A C) - A ( B C) = (A B) - A B = A B (A C) 10. Hukum 0/1

- ø =

- = ø

1.12. Perampatan Ops Himpunan

A1 A2 . . . An = Ai

i=1 n

A1 A2 . . . An = Ai i=1 n

A1 x A2 x . . . X An = Ai i=1

nA1 A2 . . . …. An Ai

i=1

+ ++ +

1.13. Prinsip Inklusi - Eksklusi

Jumlah elemen hasil penggabungan seharusnya adalah jumlah elemen di masing-masing himpunan dikurangi dengan jumlahelemen dalam irisannya

|A B| = |A| + |B| - |A B|

Bab II : Relasi & Fungsi2.1. Relasi Relasi biner R antara A dan B adalah himpunan bagian dari A x B R A x B Contoh : Misalkan P = { 2, 4, 8, 9, 15 } Q = { 2, 3, 4 } Jika didefinisikan relasi R dari P ke Q dengan ( p, q )

є R jika p habis dibagi q, maka kita peroleh R = { (2,2 ), (4,2), (4,4), (8,2), (8,4), (9,3), (15,3) }

2.2. Refresentasi Relasi Selain dinyatakan dalam bentuk pasangan terurut, relasi bin er dapat dinyatakanA. Tabel Kolom pertama menyatakan daerah asal, kolom kedua me nyatakan daerah hasilContoh : r q

2 2

4 2

4 4

8 2

8 4

9 3

15 3

B. Dengan Matriks Misal R adalah relasi dari A = ( a1, a2, …., am ) dan B = { b1, b2, …. Bn }Relasi R dapat disajikan dengan matriksM = [ mij] b1 b2 ……………… bn a1 m11 m12 m1n a2 m21 m22 m2n M = . . . . . . . . . . . . am am1 am2 amn C. Dengan bentuk grafis

Jika (a,b) є R maka sebuahbusur dibuat dari a ke b

Contoh : 3 2 4

15 8

9

2.3. SIFAT - SIFAT RELASI BINER

A. Refleksif ( Reflexive )

Relasi R pada Himpunan A disebut reflexive jika ( a,a ) є R

untuk setiap a є A

B. Setangkup ( Symmetric )Relasi R pada himpunan A disebut simetric jika untuk semua

a, b є A, jika (a,b) є R maka (b, a ) є R

C. Menghantar ( Transitive )Relasi R pada himpunan A disebut transitive bilamana (a, b)

є R dan (b, c) є R maka (a, c) є R, untuk a, b, c є A

2.4. Mengkombinasikan RelasiKarena Relasi Biner merupakan himpunan pasangan terurut, maka operasi irisan, gabungan, selisih dan beda setangkupantara dua atau lebih relasi juga menghasilkan relasi.Contoh :

2.5. Komposisi RelasiMisal R adalah relasi himpunan A ke himpunan B, dan S adalahrelasi dari himpunan B ke himpunan C.Komposisi R dan S, di notasikan dengan RoS

RoS = { (a, c) | a є A, c є C, dan untuk beberapa b є B, (a, b)

є R dan (b, c) є S } Contoh :

2.6. Relasi n - aryMisalkan A1, A2, ………….., An adalah himpunan relasi n - ary R pada himpunan-himpunan tersebut adalah himpunan bagian dari A1 x A2 x ….. x an atau dengan notasi R A1 x A2 … xAnHimpunan A1, A2, …, An disebut daerah asal relasi dan n disebut derajat

2.7. FungsiMisalkan A dan B himpunan relasi biner f dari A ke B merupakan suatu fungsi jika untuk setiap elemen a didalam A terdapat satu elemen tunggal b di dalam B sedemikian sehingga (a, b)

є f kita tulis f (a) = bJika f adalah fungsi dari A ke B, kita menuliskan f : AB yang artinya f memetakan A ke B

a b

BA

f

A= daerah asal

B= Daerah Hasil

Fungsi f dikatakan satu-ke-satu (one-to-one) atau injektif (injectiv) jika tidak ada dua elemen himpunan A yang me miliki bayangan yang sama.

Fungsi satu - ke - satu

a.b.c.d.

.1

.2

.3

.4

.5

BA

Fungsi f dikatakan dipetakan pada (onto) atau surjektif (surjective) jika setiap elemen himpunan B merupakan baya ngan dari satu atau lebih elemen himpunan A. Dengan kata lain fungsi f adalah pada bila semua elemen B merupa kan daerah hasil dari f.

Fungsi PADA

a.b.c.d.

.1

.2

.3

BA

Bab III : Induksi Matematika Induksi matematika merupakan tehnik pembuktian yang baku didalam matematik. Induksi matematik digunakan untuk membuktikan pernyataan yang khusus mengenai bilangan bulat positip. Dengan induksi ini dapat di buktikan kebenaran pernyataan matematik dalam jumlah langkah terbatas.

3.1. Prinsip Induksi SederhanaMisal p(n) adalah pernyataan perihal bilangan bulat positip dankita ingin membuktikan bahwa p(n) benar untuk semua bilanganbulat positip n.Untuk membuktikan pernyataan ini, perlu ditunjukkan bahwa :

1). P(1) benar dan

2). Untuk semua bilangan bulat positip n 1, jika p(n) benar maka p(n+1) juga benar

Contoh :Tunjukkan bahwa untuk n 1, 1 + 2 + 3 + …. +n = n(n+1)/2Bukti :Basis induksiUntuk n = 1 maka 1 = 1 ( 1 + 1 )/2 1 = 1Langkah Induksi Andaikan untuk n 1 pernyataan 1 + 2 + 3 + ……..+ n + n + 1= ( n + 1 ) [ ( ( n + 1 ) + 1 ) ]/2juga benar

1 + 2 + 3 + ….. + n + (n + 1) = (1 + 2 + 3 + ….+ n) + (n + 1)= n (n + 1)/2 + (n + 1)= (n2 + n)/2 + (n + 1)= (n2 + n)/2 + (2n + 2)/2= (n2 + n + 2n + 2)/2= (n2 + 3n + 2)/2= [(n + 1)(n +2)]/2= (n + 1)[(n + 1) + 1]/2

Maka benar untuk semua bilangan bulat positip3.2. Prinsip Induksi yang di rampatkanMisalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n n0. Untuk membuktikan ini, hanya perlu ditunjukkan hal berikut :

a> p(n0) benar, danb> Untuk semua bilangan bulat n n0, jika p(n) benar maka p(n + 1) juga benar.

Contoh :Untuk semua bilangan bulat tidak negatif n, buktikan bahwa20 + 21 + 22 + ………… + 2n = 2n+1 - 1

Bukti :Basis Induksi untuk n = 020 = 20+1 - 1 ini jelas BENARLangkah induksi. Andaikan bahwa untuk semua bilangan bulattidak negatif n20 + 21 + 22 + ………… + 2n = 2n+1 - 1 adalah benar (Hipotesisinduksi). Harus ditunjukkan bahwa 20 + 21 + 22 + ………… + 2n + 2n +1 = 2 (n+1)+1 - 1 juga benar

Hal ini ditunjukkan :20 + 21 + 22 + ………. + 2n + 2n+1 = (20 + 21 + …. +2n) + 2n+1

= (2n +1 - 1) + 2n+1

= (2n+1 + 2n+1) - 1 = (2 . 2n+1) - 1 = 2n+2 - 1 = 2(n+1)+1 - 1 karena langkah 1 dan 2 benar. Maka benar untuk semua bilangan bulat tidak negatif.

BAB IV : KombinatorialKombinatorial (Combinatoric) adalah cabang matematika yangmempelajari pengaturan objek-objek.Contoh :1. Password sistem komputer panjangnya enam sampai dela pan karakter. Tiap karakter boleh berupa huruf atau angka, huruf besar dan kecil tidak dibedakan. Berapa banyak password yang bisa dibuat ? 2. Plat mobil di negara X terdiri atas 5 digit angka diikuti deng an 2 huruf. Huruf pertama tidak boleh O. Berapa banyak plat mobil yang dapat dibuat ?

Masalah-masalah ini dapt diselesaikan oleh kombinatorial

4.1. PercobaanKombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan (Experiment) atau kejadian (Event).Percobaan adalah proses fisik yang hasilnya dapat diamati.Contoh :1. Melempar daduHasil percobaan adalah muka dadu 1, 2, 3, 4, 5, 6,.2. Melempar koinHasil percobaan adalah “muka” atau “belakang”

4.2. Kaidah dasar menghitungDalam kombinatorial, harus dihitung (Counting) semua kemungkinan pengaturan objek.

A. Kaidah Perkalian (rule of product)Bila percobaan 1 menghasilkan pBila percobaan 2 menghasilkan q

Maka percobaab 1 dan percobaan 2 dilakukan maka terdapat p x q hasil percobaan

B. Kaidah Penjumlahan (rulr of sum)Bila percobaan 1 menghasilkan pBila percobaan 2 menghasilkan qMaka percobaab 1 atau percobaan 2 dilakukan maka terdapat p x q hasil percobaanContoh :Jabatan ketua himpunan mhs. TI dijabat oleh mhs angkatan 2001 atau 2002 jumlah mhs. 2001 = 45 orang dan jumlah mhs. 2002 =52 orang.Berapa cara memilih pejabat ketua himpunan ?

Jawab :Banyak cara memilih ketua dari mhs 2001 = 45 caraBanyak cara memilih ketua dari mhs 2002 = 52 caraMaka banyaknya cara memilih ketua angkatan 2001 atau 2002 = (45 + 52) cara= 97 cara

4.3. Perluasan KaidahKaidah perkalian dan perjumlahan diatas dapat diperluas sampai n percobaan.Jika n percobaan masing-masing mempunyai p1, p2 …., pn hasilpercobaan, maka jumlah hasil percobaan yang mungkin terjadi :- p1 x p2 x p3 x ….. x pn kaidah perkalian- p1 + p2 + p3 + ….. + pn kaidah perjumlahan

4.4. Permutasi- Permutasi adalah jumlah urutan berbeda dari pengaturan objek- objek p(n) = n! = n(n-1)(n-2) …….1 - Permutasi r dari n elemen adalah jumlah kemungkinan urutan r buah elemen yang dipilih dari n elemen dengan r < n n! p(n, r) = (n-r)!

Contoh :Berapa banyak “String” yang dapat dibentuk yang terdiri dari 4huruf berbeda dan diikuti dengan 3 angka yang berbeda pula ?p(26, 4) x p(10, 3) = 258.336.000

4.5. KombinasiBentuk khusus dari permutasi adalah kombinasi. Jika pada permu-tasi urutan kemunculan diperhitungkan, maka pada kombinasi urutan kemunculan diabaikan urutan acb, bca, dan acb dianggapsama dan dihitung sekali n !C (n, r) = r ! (n-r) !

Contoh :Berapa banyak cara menyusun menu ‘nasi goreng’ tiga kaliseminggu ? 7 ! C (7, 3) = = 35 Cara 3 ! 4 !

BAB V : ALJABAR BOOLEANDetAljabar boolean merupakan aljabar yang terdiri atas suatu hurup B dengan dua operator biner yang didefinisikan pada himpunantersebut yaitu : + (penambahan) • (perkalian)

Aksioma :

a> Closure : - a + b є B - a • b є B

b> Identitas : - ada elemen O є B a + o = o + a = a

- ada elemen 1 є B a • 1 = 1 • a = a

c> Komutatif : - a + b = b + a - a • b = b • a

d> Distributif : - a • (b + c) = (a • b) + (a • c) - a +(b • c) = (a + b) • (a + c) - (a • b) + c = (a +c) • (b + c)

e> Komplemen : untuk setiapa є B ada elemen a 1 є B sehingga a + a 1 = 1 dan a • a 1 = 0

f> Terdapat paling sedikit dua buah elemen a, b є B sehingga a b

g> Idempoten : a • a = a a + a = a

h> Assosiatif : a + (b + c) = (a + b) + c a • (b • c) = (a • b) • c

5.2. Aljabar Boolean Dua NilaiAljabar dua nilai didefinisikan pada himpunan dengan dua buah elemen, B = { 0, 1 }dengan kaedah operator biner berikut :

a b a.B

0011

0101

O001

a b A+B

0011

0101

O111

a A1

01

10

Untuk selanjutnya, Aljabar boolean yang akan dibahas adalah Aljabar Boolean dua nilai

5.3. Prinsip DualitasMisalkan S adalah kesamaan tentang aljabar boolean yang me-libatkan operasi +, …. , komplemen, maka jika pernyataan S*diperoleh dengan cara mengganti: • dengan +

+ dengan • 0 dengan 1

1 dengan 0S* disebut dual dari scontoh : Tentukan dual dari : a • (b + c) = (a • b) + (a • c )jawab : a + (b • c) = (a + b) • (a + c)

5.4. Sifat-Sifat Aljabar Booleana> Hukum identitas

- a + 0 = a- a • 1 = a

b> Hukum Idempoten- a + a = a- a • a = a

c> Hukum Dominasi- a + a 1 = 1- a • a 1 = 0

d> Hukum Dominasi- a • 0 = 0- a + 1 = 1

e> Hukum Involusi- (a 1)1 = a

f> Hukum Penyerapan - a + (a • b) = a- a • (a + b) = a

g> Hukum Komutatif- a + b = b + a- a • b = b • a

h> Hukum Assosiatif- a + (b + c) = (a + b) + c- a • (b • c) = (a • b) • c

i> Hukum Distributif- a + (b • c) = (a + b) • (a + c)- a • (b + c = (a • b) + (a • c)

j> Hukum De Morgan- (a + b)1 = a1 • b1

- (a b)1 = a1 + b1

k> Hukum O/1- O1 = 1- 11 = O

Buktikan bahwa untuk sembarang elemen a dan b dari aljabarBoolean :

a + a1 b = a + b dan a ( a1 + b) = ab Bukti :1) a + a1b = (a + ab) + a1 b ( penyerapan)

= a +(ab + a1b) ( Assosiatif ) = a + (a + a1) b ( Distribatif ) = a + 1 • b ( Komplemen ) = a + b ( Identitas )

2) a (a1 + b) = aa1 + ab ( Distributif ) = O + ab ( Komplemen) = ab ( Identitas )

5.5. Fungsi BooleanFungsi boolean adalah ekspresi yang dibentuk dari perubah biner, dua operator ( + ) dan ( • ), operator uner komplemen ( - )tanda kurang dan tanda sama dengan ( = ).Contoh :1. f ( x ) = x2. f ( x, y ) = x1 y1 + xy1 + y1

3. f ( x, y ) = x1 y1

4. f ( x, y ) = ( x + y )1

5. F ( x, y, z ) = x y z1

5.6. Fungsi KomplemenFungsi komplemen dari suatu fungsi f, yaitu f1 dapat dicari dengan menukarkan nilai 0 dengan 1 dan nilai 1 dengan 0.Ada dua cara membentuk F komplemen

A. Menggunakan hukum De Morgan- Untuk dua peubah (x1 + x2)1 = x1

1 x21

(x1 • x2)1 = x11 + x2

1

- Untuk tiga peubah (x1 + x2 + x3)1 = (x1 +y)1 misal y = x2 + x3

= x1 1y1

= x11 (x2 + x3)1

= x11 x2

1 x31

B. Menggunakan prinsip dualitas cari dual dari f, lalu komple- menkan setiap literalnya.

5.7. Bentuk Kanonik dan Bentuk BakuAda dua macam bentuk kanonik :- Minterm atau sum of product ( SOP )- Maxterm atau product of sum ( POS )

5.8. Aplikasi Aljabar BooleanAljabar Boolean memiliki aplikasi yang luas, antara lain di bidang jaringan pensaklaran dan rangkaian digital.

5.9. Penyederhanaan Fungsi BooleanFungsi boolean seringkali mengandung operasi - operasi biner yang tidak perlu, literal atau suku - suku yang berlebihanContoh :f ( x, y ) = x1 y + xy1 + y1 dapat disederhanakan menjadi f ( x, y)= x1 + y1

Penyederhanaan dapat dilakukan melalui :- Cara aljabar- Peta karnaugh- Metoda quine Mc luskey ( metoda tabulasi )

BAB VI : TEORI GRAPH Teori graph merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Graph digunakan untuk merepresentasikan objek-objek diskrit dan hubunganantara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai TITIK atau NODE,sedangkan hubungan antara objek dengan GARIS atau EDGE.

6.1. DEFINISI GRAPHGraph G didefinisikan sebagai pasangan himpunan ( V, E ), yang dalam hal ini :V = himpunan berhingga dan tidak kosong dari simpul-simpul ( vertices, node) = { v1, v2, …., vn ) E = himpunan sisi (edges, ares) yang menghubungkan sepasang simpul

= { e1, e2, …., en }ditulis G = ( V, E )

Secara geometris 1

2 3

4

e1e2

e3 e4

e5e6e7

G

6.2. JENIS-JENIS GRAPH A. Berdasarkan tidak adanya sisi ganda - Graph sederhana - Graph tidak sederhana

B. Berdasarkan jumlah simpul - Graph berhingga - Graph tidak berhingga

C. Berdasar orientasi arah sisi - Graph tidak berarah - Graph berarah

6.3. TERMINOLOGI GRAPHA. Ketetanggaan ( Adjacent ) Dua buah simpul (titik) di katakan bertetangga bila keduanya terhubung langsung. Secara formal dinyatakan :

Vj bertetangga dengan Vk jika Ve є E sedemikian sehingga e = ( Vj, Vk ).

B. Bersisian ( Incidency ) Untuk sembarang sisi e = ( Vj, Vk ) dikatakan : - e bersisian dengan simpul Vk - e bersisian dengan simpul Vj

C. Simpul terpencil ( Isolated Vertex ) Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya.

D. Graph kosong Graph kosong adalah graph yang tidak memiliki sisiE. Derajat Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.F. Lintasan ( Dath ) Lintasan dari simpul Vp ke Vq dalam G ialah rangkaian simpul Vp, Vi1, Vi2, ….. , Vq sehingga ( Vp1, Vi1 ), (Vi2, Vi3), …………. ( Vim, Viq ) adalah sisi-sisi dalam graph GG. Siklus ( Cyck ) atau sirkuit ( Circuit ) Lintasan elementer dengan simpul pertama sama dengan simpul terakhir di sebut SIRKUIT atau SIKLUS.H. Terhubung ( Connected ) Dua buah simpul V1 dan simpul V2 disebut terhubung (Connected ) jika terdapat lintasan V1 ke V2.

Graph tak berarah G disebut graph terhubung jika untuk setiap pasang simpul Vi dan Vj dalam himpunanV terdapat lintasan dari Vi ke Vj.I. Pohan ( Tree ) Pohon adalah graph terhubung yang tidak mempunyai sirkuit

6.4. GRAPH SEDERHANA KHUSUS a. Graph lengkap ( Complete Grapg ) adalah graph sederhana yang setiap simpulnya mempunyai sisi ke simpul lainnya. Graph lengkap dengan titik n Kn jumlah sisinya n (n-1)/2 b. Graph lingkaran Graph sederhana yang setiap simpulnya berderajat dua. c. Graph Teratur ( Reguler Graph ) Graph yang setiap simpulnya mempunyai derajat yang sama

d. Graph Bipartite Graph G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2, sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke simpul V2

6.5. REPRESENTASI GRAPHUntuk maksud pemrosesan graph di komputer, graph harus direpresentasikan dengan matrik.

A. Matrik ketetanggaan ( Adjacency matrik ) Matrik ketetanggaan adalah matrik n x n dengan elemen matrik

1, jika simpul i,j bertetangga a i j

0, jika simpul I dan j tidak bertetangga

Contoh :1 2 3 4 5

1 0 1 1 0 0 2 1 0 1 0 0 3 1 1 0 1 0 4 0 0 1 0 0 5 0 0 0 0 0

B. Matrik bersisian ( Incidency Matriks ) Matrik bersisian G adalah matrik berukuran n x m dengan elemen aij dimana

1, jika titik i bersisian dengan sisi ja i j =

0, jika titik i tidak bersisian dengan sisi j

2

1

3

4

5

Contoh :

1 2

3

4

e1

e2

e3

e4

e5

e1 e2 e3 e4 e5

1 1 1 0 1 0

2 1 1 1 0 0

3 0 0 1 1 1

4 0 0 0 0 1

C. Senorai ketetanggaan ( Adjacency List ) Senorai ketetanggaan mengenumersi simpul-simpul yang bertetangga dengan setiap simpul di dalam graph.

Contoh : 1

2 3 4

5

Simpul

Simpul tetangga

12345

2,31,41,2,43-