MAKALAH MATEMATIKA DISKRIT

DERAJAT TITIK, PENYAJIAN GRAF DENGAN MATRIKS

Diajukan Sebagai Salah Satu Penilaian Mata Kuliah Matematika Diskrit

DISUSUN OLEH:
1. AIDATUL IRA HARAHAP (19205003)
2. DALA ZULYANI (19205041)
3. CANIA KASTIRA (20205005)
4. RAHMADILA (20205024)
5. HAMIDAH (20205042)

DOSEN PEMBIMBING:
Prof. Dr. Ahmad Fauzan, M.Pd, M.Sc

PROGRAM STUDI MAGISTER PENDIDIKAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS NEGERI PADANG
2021
 KATA PENGANTAR

Dengan memanjatkan puji syukur kehadirat Allah Yang Maha Esa, atas limpahan
rahmat dan karunianya sehingga penulis dapat menyelesaikan makalah ini untuk tugas
Matematika Diskrit. Penulis juga mengucapkan terima kasih kepada dosen pembimbing mata
kuliah Matematika Diskrit, yaitu :Bapak Prof. Dr. Ahmad Fauzan, M.Pd, M.Sc yang telah
memberikan tugas kepada penulis sehingga penulis dapat memahami tentang derajat titik dan
penyajian graf dengan matriks.
Makalah ini terlaksanakan tidak lepas karena bantuan dan dukungan dari berbagai
pihak yang dengan tulus dan sabar memberikan sumbangan baik berupa ide, materi
pembahasan dan juga bantuan lainnya yang tidak dapat dijelaskan satu persatu.
Makalah ini disusun untuk membantu proses pembelajaran mahasiswa khususnya untuk
mahasiswa Pendidikan Matematika. Makalah ini membahas tentang “derajat titik dan
penyajian graf dengan matriks.”
Penulis menyadari makalah ini jauh dari kesempurnaan, maka dari itu pemakalah
berharap kepada Bapak dosen untuk memberikan kritik dan saran untuk menyempurnakan
makalah ini.

Padang, April 2021

Penulis

ii
 DAFTAR ISI

KATA PENGANTAR .................................................................................................... ii

DAFTAR ISI................................................................................................................... iii

BAB I Pendahuluan

A. Latar Belakang ............................................................................................. 1

B. Rumusan Makalah ....................................................................................... 1
C. Tujuan Penulisan Makalah ........................................................................... 1

BAB II Pembahasan

A. Derajat Titik .................................................................................................. 2

B. Penyajian Graf dengan Matriks .................................................................... 6

BAB III Penutup

Kesimpulan ........................................................................................................10

Saran ....................................................................................................................10

Daftar Pustaka ...............................................................................................................11

iii
 BAB I
PENDAHULUAN
A. Latar Belakang
Pada tahun 1836, Leonhard Euler membuktikan bahwa perjalanan di kota
Konigsberg dengan syarat melalui setiap jembatan tepat satu kali, tidak dapat
dilaksanakan. Dalam pembuktiannya Euler menyederhanakan situasi
jembatan Konigsberg itu menjadi suatu diagram seperti pada Gambar 1.

Gambar 1.
Berkat pekerjaan Euler yang diilhami melalui persoalan jembatan
Konigsberg itu, maka muncullah suatu cabang Matematika yang cukup
penting, yang dikenal dengan nama Teori Graph (Graph Theory).
Teory Graph sudah banyak berkembang dan memiliki segi terapan di
banyak bidang ilmu, misalnya di bidang Fisika, Kimia, Ilmu Komunikasi,
Rekayasa listrik, Genetika, dan lain-lain. Teori Graph juga erat kaitannya
dengan beberapa cabang Matematika, antara lain ; teory Matriks, Analisa
Numerik, Teori Kemungkinan, Topologi dan Kombinatorial.
Berdasarkan hal diatas, didalam makalah ini akan dibahas mengenai
derajat titik dan penyajian graf dengan mattiks secara ringkas serta
contohnya.
B. Rumusan Masalah
1. Bagaimana defenisi dari derajat titik ?
2. Bagaimana penyajian graf dengan matriks ?
C. Tujuan
Sesuai dengan ruang lingkup pembahasan, maka terdapat tujuan pembahasan
yaitu:
1. Mengetahui defenisi dari derajat titik.
2. Mengetahui penyajian graf dengan matriks .

1
 BAB II
PEMBAHASAN
A. Derajat Titik
Definisi 7

Misalkan v adalah titik dalam suatu Graf G. Derajat titik v (simbol d(v))
adalah jumlah sisi yang berhubungan dengan titik v dan sisi suatu loop
dihitung dua kali. Derajat total G adalah jumlah derajat semua titik
dalam G.

Contoh 11 :
Tentukan derajat tiap-tiap titik dalam graf pada Gambar 15. Berapa derajat
totalnya ?

Penyelesaian :

d(v1) = 4 karena sisi yang berhubungan dengan v1 adalah e2, e3 dan loop e1
yang dihitung dua kali

d(v2) = 2 karena garis yang berhubungan dengan v2 adalah e2 dan e3.

d(v3) = d(v5) = 1 karena garis yang berhubungan dengan v3 dan v5 adalah e4

d(v4) = 2 karena garis yarag berhubungan dengan v4 adalah loop e5 yang
dihitung 2 kali.
d(v6) = 0 karena tidak ada garis yang berhubungan dengan v6.
2
Derajat total = 6
𝑖=1 𝑑 (𝑣𝑖 ) = 4 + 2 + 1 + 2 + 1 + 0 = 10
Teorema 2
Derajat total suatu graf selalu genap.

Bukti:
Misalkan G adalah suatu graf.
Jika G tidak memiliki sisi sama sekali berarti derajat totalnya = 0 yang
merupakan bilangan genap, sehingga teorema terbukti.

Misalkan G mempunyai n buah titik v1, v2, ... , vn (n > 0) dan k buah sisi e1, e2,

... ,ek (k>0). Ambil sembarang sisi ei. Misalkan sisi ei menghubungkan vi dengan

vj. Maka ei memberikan kontribusi masing-masing 1 ke penghitungan derajat vi

dan derajat vj (hal ini juga benar jika vi = vj karena derajat suatu loop dihitung 2

kali), sehingga ei memberi kontribusi 2 ke penghitungan derajat total. Karena e i

dipilih sembarang, berarti semua sisi dalam G memberi kontribusi 2 dalam
penghitungan derajat total. Dengan kata lain, derajat total G = 2 kali jumlah sisi
dalam G. Karena jumlah sisi dalam G merupakan bilangan bulat, berarti derajat
total G merupakan bilangan genap.

Teorema 3
Dalam sembarang graf, jumlah titik yang berderajat ganjil adalah genap.

Bukti
Misalkan G suatu graf.
Jika G tidak mempunyai sisi sama sekali berarti banyaknya titik yang
berderajat ganjil = 0 yang merupakan bilangan genap sehingga teorema
terbukti dengan sendirinya.

Misalkan G mempunyai n buah titik vi, v2, ... , vn dan k buah garis e1, e2, ... ,
ek. Misalkan di antara k sisi tersebut ada ki buah sisi yang berderajat ganjil
dan k2= k – k1 buah garis yang berderajat genap.

3
 Akan dibuktikan bahwa k1 adalah bilangan genap.

Misalkan E adalah jumlah derajat semua titik yang berderajat genap, 0 adalah
jumlah derajat semua titik yang berderajat ganjil, dan T adalah derajat total
graf G.

Menurut Teorema 2, maka T adalah bilangan genap.

Karena d(ek1 )+ d( ek2 )+ ... + d(ek) masing-masing berderajat genap,
maka E = d( ek1 )+ d( ek2 )+ ... + d(ek) juga merupakan bilangan genap.

Dari relasi T = E + O, berarti O = T – E. Karena baik T maupun E merupakan

bilangan-bilangan genap maka O = d(ei) + d(e2)+ ... + d( ek1) juga
merupakan bilangan genap. Padahal menurut asumsi, d(e1), d(e2), ... ,d( ek1 )
masing-masing adalah bilangan ganjil. Jadi O (bilangan genap) merupakan
jumlahan dari k1 buah bilangan ganjil.Hal ini hanya bisa terjadi kalau k1
adalah bilangan genap.Terbukti bahwa k1 (jumlah titik yang berderajat ganjil)
merupakan bilangan genap.

Contoh 12
Gambarlah graf dengan spesifikasi di bawah ini (jika ada).
a. Graf dengan 4 titik yang masing-masing berderajat 1,1, 2 dan 3.

b. Graf dengan 4 titik dengan masing-masing berderajat 1, 1, 3, dan 3.

c. Graf dengan 10 titik yang masing-masing berderajat 1, 1, 2, 2, 2, 3, 4, 4, 4,

dan 6.

d. Graf sederhana dengan 4 titik yang masing-masing berderajat 1, 1, 3, dan

3.
Penyelesaian :
a. Derajat total = 1 + 1 + 2 + 3 = 7 (ganjil). Menurut Teorema 2 maka tidak
ada graf dengan derajat total ganjil.

4
b. Derajat total = 1 + 1 + 3 + 3 = 8 (genap). Jadi, ada graf dengan spesifikasi
semacam itu. Beberapa di antaranya tampak pada Gambar 16.

c. Ada 3 titik yang berderajat ganjil (yaitu titik-titik yang berderajat 1, 1, dan
3). Menurut teorema 3, tidak mungkin ada graf dengan spesifikasi
semacam itu.Pengecekan juga dapat dilakukan dengan menghitung derajat
totalnya yang merupakan bilangan ganjil.

d. Derajat total = 1 + 1 + 3 + 3 = 8 (genap) sehingga mungkin buat graf

dengan spesifikasi tersebut. Tetapi, graf yang dapat dibuat adalah graf
secara umum (seperti soal (b)), dan bukan graf sederhana.Graf sederhana
dengan spesifikasi tersebut tidak mungkin dibuat. Hal ini dibuktikan
dengan kontradiksi sebagai berikut :

Misalkan ada graf G dengan 4 titik, masing-masing v1 dan v2 yang

berderajat 1, v3 dan v4 yang berderajat 3.karena v3 berderajat 3 dan grafnya
adalah graf sederhana (tidak boleh mengandung loop dan sisi paralel), maka
v3 harus dihubungkan ke 3 titik yang lain (v1, v2, v4). Hal tersebut dapat
dilihat pada Gambar 17.

V4 juga mempunyai derajat 3, berarti V4 juga harus dihubungkan dengan

ketiga titik yang lain. Didapatkan graf Gambar 18.
5
 Akan tetapi, jika demikian halnya, v1 dan v2 mempunyai derajat 2,
yang bertentangan dengan pengandaian mula-mula yang mengatakan bahwa
v1 dan v2 berderajat 1.Dengan demikian, terbukti bahwa tidak ada graf
dengan spesifikasi seperti ini.
B. Penyajian Graf dalam Matriks
Ada beberapa cara untuk menyajikan sebuah graf. Matriks adalah cara
yang sering digunakan. Ada duacara matriks yang akan digunakan, yaitu :
matriks berhubungan langsung (adjacency matrix) dan matriks keterkaitan
(incidence matrix).
Misal G adalah sebuah graf dengan V(G) = {v1, v2, … , vn}. Matriks
berhubungan langsung dari G adalah matriks bujur sangkar berordo n,
A(G)=(aij) dimana elemen aijmenyatakan banyaknya sisi yang
menghubungkan titik vi dan titik vj.

Perhatikan graf G dan matriks berhubungan langsungnya, berikut :

G
v1v2v3v4v5

6
 v1 0 1 0 3 0
v2 1 0 1 0 0
v3 0 1 0 1 1
v4 3 0 1 0 0
v5 0 0 1 0 1
A(G)
Perhatikan bahwa A(G) adalah matriks simetris. Kalau graf G tidak
punya gelung (loop), maka setiap unsur A(G) yang terletak pada diagonal
utama adalah nol. Kalau graf G sederhana, maka unsur-unsur dari A(G) nol
atau satu.
Jika diberikan sebuah matriks simetris A berordo n x n dimana setiap
unsur A adalah bilangan bulat non negatif, maka pasti terdapat sebuah graf G
dengan matriks berhubungan lanngsung A(G) = A.
Graf G dengan matriks berhubungan langsung A.
1 1 2 0
1 1 1 1
A=
2 1 0 0
0 1 0 0

G
Sekarang, kalikan matriks A dengan dirinya sendiri diperoleh
6 4 3 1
4 4 3 1
A2 =
3 3 5 1
1 1 1 1
Perhatikan bahwa unsur A2 yang terletak di baris ke i dan kolom ke j
menyatakan banyaknya jalan –(vi, vj) di graf G dengan panjang dua.
Misalnya, unsur A2yang terletak di baris ke 1 dan kolom ke 2 adalah 4. Jadi
ada 4 jalan -(v1, v2 ) di graf G dengan panjang 2, yaitu
:𝑣1 𝑒1 𝑣1 𝑒2 𝑣2 , 𝑣1 𝑒2 𝑣2 𝑒6 𝑣2 , 𝑣1 𝑒3 𝑣3 𝑒5 𝑣2 , 𝑣1 𝑒4 𝑣3 𝑒5 𝑣2 . Ada 5 jalan –(v3, v3) di G
7
dengan panjang 2, yaitu 𝑣3 𝑒5 𝑣2 𝑒5 𝑣3 ,
𝑣3 𝑒4 𝑣1 𝑒4 𝑣3 , 𝑣3 𝑒3 𝑣1 𝑒3 𝑣3 , 𝑣3 𝑒3 𝑣1 𝑒4 𝑣3 , 𝑣3 𝑒4 𝑣1 𝑒3 𝑣3 .
Berikut diberikan generalisasi dari observasi diatas.
Teorema1 : misalkan G adalah graf dengan V(G) = {v1, v2, … , vn}. Jika A
adalah matriks berhubungan langsung dari G, maka unsur Ak, untuk suatu
bilangan bulat positif k, yang terletak di baris ke i dan kolom ke j menyatakan
banyaknya jalan di G dengan panjang k yang menghubungkan titik vidan vj.
Bukti : kita buktikan dengan induksi pada k. Jelas pernyataan diatas benar
(𝑡)
untuk k =1. Andaikan pernyataan diatas benar untuk k-1. Misalkan 𝑎𝑖𝑗
menyatakan unsur Atyang terletak di baris ke i dan kolom ke j.
Karena Ak = Ak-1.A, maka :
(𝑘) 𝑛 (𝑘−1)
𝑎𝑖𝑗 = 𝑟=1 𝑎𝑖𝑟 𝑎𝑟𝑗 (*)
(𝑘−1)
Menurut hipotesis, untuk setiap r, 1 ≤ 𝑟 ≤ 𝑛; 𝑎𝑖𝑗 menyatakan
banyaknya jalan –(vi, vr) di G dengan Panjang (k-1), sedangkan 𝑎𝑟𝑗
menyatakan banyaknya sisi di G yang menghubungkan titik vrdan titik vj.
𝑛 (𝑘−1)
Sehingga 𝑟=1 𝑎𝑖𝑟 𝑎𝑟𝑗 menyatakan semua jalan di G dengan panjang k
yang menghubungkan titik vi dan titik vj. Sekarang dari persamaan (*) dapat
(𝑘)
disimpulkan bahwa 𝑎𝑖𝑗 menyatakan banyaknya jalan di G dengan panjang k
yang menghubungkan titik vi dan titik vj. Terbukti
Dengan menggunakan Teorema 1 diatas, dapat dibuktikan teorema
berikut ini.
Teorema 2 : misalkan G adalah graf dengan V(G) = {v1, v2, … , vn}. Jika A
adalah matriks berhubungan langsung dari G dan B = 𝑏𝑖𝑗 adalah matriks
dengan B = A + A2 + A3+ … + An-1, maka graf G terhubung jika dan hanya
jika 𝑏𝑖𝑗 ≠ 0, untuk setiap i dan j ,𝑖 ≠ 𝑗.
Selain dengan matriks berhubungan langsung, kita juga dapat menyajikan
sebuah graf dengan matriks keterkaitan.

8
 Misalkan graf G mempunyai n titik : v1, v2, … , vndan s sisi : e1, e2, … ,
en. Matriks keterkaitan (incidence matrix) dari G adalah matriks M(G) = (mij)
berordo n x s, dimana :
0, jika sisi ej tidak terkait dengan titik vi
𝑚𝑖𝑗 = 1, jika ej terkait dengan vi dan ej bukan gelung
2, jika ej terkait dengan vi dan ej adalah gelung
Sebagai contoh, matriks keterkaitan dari graf G pada gambar berikut
e1 e2 e3 e4 e5 e6 e7
𝑣1 2 1 1 1 0 0 0
𝑣2 0 1 0 0 1 2 1
𝑀 𝐺 =𝑣
3 0 0 1 1 1 0 0
𝑣4 0 0 0 0 0 0 1
Perhatikan bahwa jumlah semua unsur M(G) yang terletak di baris i
menyatakan derajat dari titik vi di graf G, sedangkan jumlah semua unsur
M(G) yang terletak di suatu kolom selalu 2.

9
 BAB III
PENUTUP

1. Kesimpulan
a. Misalkan v adalah titik dalam suatu Graf G. Derajat titik v (simbol d(v))
adalah jumlah sisi yang berhubungan dengan titik v dan sisi suatu loop
dihitung dua kali. Derajat total G adalah jumlah derajat semua titik
dalam G.
b. Ada beberapa cara untuk menyajikan sebuah graf. Matriks adalah cara yang
sering digunakan. Ada dua cara matriks yang akan digunakan, yaitu :
matriks berhubungan langsung (adjacency matrix) dan matriks keterkaitan
(incidence matrix).
2. Saran
Kami menyadari dalam pembuatan makalah ini masih banyak
kekurangan.Kami berharap makalah ini tetap memberikan manfaat bagi
pembaca. Namun, saran dan kritik yang sifatnya membangun dengan tangan
terbuka kami terima demi kesempurnaan di masa yang akan datang.

10
 DAFTAR PUSTAKA

Budayasa, Ketut. 2007. Teori Graph dan Aplikasinya. Departemen Pendidikan

Nasional : Universitas Negeri Surabaya.

11