representasi graf, graf isomorfik, graf plannar dan graf dual
Embed Size (px)
TRANSCRIPT

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 1/44
Representasi Graf,
Graf Isomork,Graf Planar dan
Graf BidangOleh Kelompok II

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 2/44
MATERIRepresentasi Graf
Graf Isomork
Graf Planar dan Graf
Bidang
Graf Dal

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 3/44
RepresentasiGraf
Terdapat beberapa macam representasi graf. Namun di sini hanya diberikan
tiga macam representasi yang sering digunakan, yaitu matriks ketetanggaan,
matriks bersisian dan senarai ketetanggaan.
!" Matriks Ketetanggaan #Ad$a%en%&Matri'(
( )
Matriks ketetanggan menyatakan ketetanggaan simpul-simpul di dalam
graf. adalah matriks dwimatra yang berukuran . Misalkan
, adalah graf dengan simpul, 1. Bila matriks tersebut
dinama
G n n
G V E n n×
= ≥
ij ij
ij
kan A !a ", maka a 1 jika simpul dan bertetangga,
sebaliknya a # jika simpul dan tidak bertetangga.
i j
i j

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 4/44
1
$
%
&
1
%$
&
'1
& $
%
Matriks ketetanggaannyasimetri
Matriks ketetanggaannyasimetri
Matriksketetanggaannya tidak
Matriks ketetanggaan dinamakan juga matriks n(l-satu karena pada matriks
tersebut hanya berisi dari n(l dan satu. )elain angka # dan 1 elemen matriks
juga dapat dinyatakan dengan nilai *menyataka false n #+ dan *menyatakan 1+.true
1 # 1 1 #
& 1 # 1 1
$ 1 1 # 1
% # 1 1 #
1 # 1 1 # #
& 1 # 1 # #
$ 1 1 # 1 #
% # # 1 # #
' # # # # #
1 & $ % '
1 & $ % 1 # 1 # #
& 1 # 1 1
$ 1 # # #
% # 1 1 #
1 & $ %

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 5/44
1
&
$
%
e%
e
e
e&
e1
e'
e$
e
Matriks ketetanggaannyasimetri
1 # 1 & #
& 1 # 1 1
$ & 1 1 &
% # 1 & #
1 & $ %
/euntungan representasi dengan matriks ketetanggaan adalah elemen matriksnyadapat diakses langsung melalui indeks. )elain itu, kita juga dapat menentukan
dengan langsung apakah simpul dan simpuli j bertetangga.
&
0umlah elemen matriks
ketetanggan untuk graf
dengan n simpul adalah .n
1
1
erajat tiap simpul dapat dihitung dari matriks ketetanggan.
2ntuk graf tak-berarah, * +
)edangkan untuk graf berarah, * + jumlah nilai pada k(l(m
n
i ij
j
n
j ij
i
i
d v a
d v j a
=
=
=
=
∑
∑
1 * + jumlah nilai pada baris
n
i ij jd v i a=
=
∑

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 6/44
)ontoh
1
$
%
&
1
%$
&
'
Berdasarkan gambar disamping,
tentukan derajat simpul & dan derajat simpul % 3
0awab 4
erajat simpul & 1 # 1 1 $
erajat simpul % # 1 1 # &
+ + + =
+ + + =
Berdasarkan gambar disamping,
tentukan derajat simpul % dan derajat simpul ' 3
0awab 4
erajat simpul % # # 1 # # 1
erajat simpul ' # # # # # #
+ + + + =
+ + + + =

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 7/44
)ontoh
a
b
cd
e
1# 1&
5
1%
1' 11
1
& $
%
Berdasarkan gambar disamping, tentukan
derajat simpul & 3
0awab 4
erajat-masuk simpul & 1 # # 1 &
erajat-keluar simpul & 1 # 1 1 $
+ + + =
+ + + =
1& 1#1& 5 11
5 1%
11 1% 1'
1# 1'
ab
c
d
e
∞ ∞ ∞ ∞
∞ ∞ ∞
∞ ∞ ∞ ∞
a b c d e
i bawah ini merupakan gambar graf berb(b(t.
Tanda menyatakan bahwa
tidak ada sisi dari simpul
ke simpul atau dari simpul
ke simpul itu sendiri,
sehingga dapat diberi
nilai tak hingga.
ij
i
j
i i
a
∞

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 8/44
*" Matriks Bersisian #In%iden%& Matri'(
Matriks bersisian menyatakan kebersisian simpul dengan sisi.
Matriks bersisian 6 adalah matriks dwimatra yang berukuran .n m×
Baris menunjukkan label simpul, sedangkan k(l(m menunjukkan label sisi.
Bila matriks tersebut dinamakan , maka 1 jika simpul bersesuaian
dengan sisi , sebaliknya # jika simpul
ij ij
ij
A a a i
j a i =
tidak bersisian dengan sisi .
Matriks bersisian dapat digunakan untuk mempresentasikan graf yang mengandung
sisi ganda atau sisi gelang.
j

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 9/44
&
e%
1
$
%
e
e&
e1
e'
e$
i bawah ini diperlihatkan matriks bersisian untuk graf yang
direpresentasikannya. Maka jumlah elemen matriks bersisian
tersebut adalah % - &% elemen.× =
1 1 1 # 1 # #
& 1 1 1 # # #
$ # # 1 1 1 #
% # # # # 1 1
1 & $ % ' -e e e e e e

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 10/44
+" enarai Ketetanggaan #Ad$a%en%&list(
1
$
%
&
1
%$
&
'
1
& $
%
/elemahan matriks ketetanggaan adalah bila graf memiliki jumlah sisi relatifsedikit atau bersifat jarang * +, yaitu banyak mengandung banyak elemen
n(l, sedangkan elemen yang bukan n(l sedikit.
sparse
itinjau dari implementasinya
di dalam k(mputer, kebutuhan ruang mem(ri untuk matriks jarang b(r(s
karena k(mputer menyimpan elemen # yang tidak perlu.
)enarai ketetanggaan4
14 &, $
&4 1, $, %
$4 1, &, %
%4 &, $
)enarai ketetanggaan4
14 &, $
&4 1, $
$4 1, &, %
%4 $
'4 -
)enarai ketetanggaan4
14 &
&4 1, $, %
$4 1
%4 &, $

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 11/44
Graf Isomork#Isomorphi%
Graph(
1 &ua buah graf, dan dikatakan is(m(rfik jika terdapat k(resp(ndensi
satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduanya
sedemikian sehingga jika sisi bersisian dengan simpul
G G
e u 1
&
&
dan di ,
maka sisi 7 yang berk(resp(n di juga harus bersisian dengan simpul
7 dan 7 di .
v G
e G
u v G
ua buah graf yang is(m(rfik adalah graf yang sama, kecuali penamaan
simpul dan sisinya saja yang berbeda. 8ni benar karena sebuah graf dapat
digambarkan dalam banyaknya cara.

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 12/44
$
&1
%
d c
ba
v w
x y
1 & 1
&
9ada gambar diatas, is(m(rfik dengan . )impul 1, &, $, dan % di
berk(resp(nden dengan simpul a, b, c, dan d di .
)isi *1,&+, *&,$+, *$,1+, *$,%+, *1,%+ dan *&,%+ berk(resp(nden dengan sisi *
G G G
G
a
1 &
1 & $ $
, +,
* , +, * , +, * , +, * , +, * , +. )emua simpul di dan berderajat $. maupun tidak is(m(rfik dengan , karena simpul-simpul di
dua buah berderajat dua dan dua buah lagi berderajat tig
b
b c c d a d a c b d G GG G G G
1 &
a, sedangkan
simpul-simpul di dan semua berderajat tiga.G G
1G
&G
$G

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 13/44
:(nt(h lain graf yang is(m(rfik.
ari definisi is(m(rfik kita menyimpulkan dua buah is(m(rfik memenuhiketiga syarat berikut4
1. Mempunyai jumlah simpul yang sama.
&. Mempunyai jumlah sisi yang sama.
$. Mempunyai jumlah simpul yang sama berderajat tertentu.

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 14/44
u
x
v
w
y
*a+ *b+
Namun ketiga syarat ini ternyata belum cukup menjamin keis(m(rfikan.
:(nt(hnya sebagai berikut.
ua buah graf di atas memenuhi ketiga syarat yang telah disebutkan
sebelumnya. 9adahal keduanya tidak is(m(rfik. i * + terdapat dua
simpul anting-anting *berderajat 1+ yang bertetangga dengan simpul
a
, sedangkan di * + hanya terdapat satu buah simpul anting-anting
yang bertetangga dengan . 8tulah sebabnya kedua graf di atas tidak
is(m(rfik.
x b
y

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 15/44
)ontoh
d
c
e
g
h f b
a
s
r
t
v
w u q
p
Apakah pasangan graf di bawah ini is(m(rfik;
. /arena tidak ada k(resp(densi satu-satu antara simpul pada
kedua graf. Tinjau misalnya simpul , simpul bertetangga degan dua buah
simpul berderajat & * dan + dan sebuah simpul be
Tidak isomorfik
d d
a c rderajat $ * +. 6raf
disebelah kanannya tidak mempunyai simpul yang berk(resp(nden dengan
*jika dianggap sebagai simpul yang berk(resp(nden dengan , maka ini
jelas tidak benar, sebab bertetangg
h
d
s d
s a dengan sebuah simpul berderajat & * +
dan dua buah simpul berderajat $ * dan +.
r
p w

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 16/44
)ontoh
s r
t
a
u
q p
f e
d
b
c
Apakah pasangan graf di bawah ini is(m(rfik;
, . /arena terdapat k(resp(nden satu-satu antara simpul pada
graf sebelah kiri dengan simpul-simpul pada graf sebelah kanan, yaitu4
berk(resp(nden dengan <
berk(resp(n
Iya isomorfik
a u
b den dengan <
berk(resp(nden dengan <
berk(resp(nden dengan <
berk(resp(nden dengan <
berk(resp(nden dengan <
q
c r
d s
e p
f t

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 17/44
b c
a
d
ev
w
x y
)AMA
/edua graf tersebut is(m(rfik
2ntuk memperlihatkan bahwa dua buah graf is(m(rfik, kita dapat menunjukkan
bahwa matriks ketetanggan kedua graf itu sama.
# 1 1 1 #
1 # 1 # #
1 1 # 1 #
1 # 1 # 1
# # # 1 #
a
b
c
d
e
Matriks ketetanggaannya
# 1 1 1 #
1 # 1 # #
1 1 # 1 #
1 # 1 # 1
# # # 1 #
w
x
y
v
a b c d e
Matriks ketetanggaannya
w x y v

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 18/44
)ontoh
Apakah graf sederhana yang disajikan (leh pasangan matriks ketetanggaan
di bawah ini is(m(rfik; 0elaskan jawaban, lalu gambarkan grafnya3
# 1 # 1
1 # # 1
# # # 1
1 1 1 #
# 1 1 1
1 # # 1
1 # # 1
1 1 1 #
1
&
0awab4
/eduanya tidak is(m(rfik karena jumlah sisi pada graf pertama dan graf kedua
tidak sama. 6raf pertama * + mempunyai % buah sisi, sedangkan graf kedua
* + mempunyai ' buah sisi.
G
G
1* +G
&* +G

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 19/44
Graf Planar danBidang
6raf yang 7dapat digambar7 tanpa terjadinya perp(t(ngan antar dua sisi
disebut graf planar. 0ika tidak disebut graf tak-planar.
6raf planar yang 7digambarkan7 tanpa ada perp(t(ngan antar sisi
disebut graf bidang.
6raf bidang pasti merupakan graf planar, tapi graf planar
belum tentu graf bidang.

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 20/44
)ontoh
%6raf / adalah 6raf 9lanar
6raf / bukan 6raf 9lanar

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 21/44
)ontoh
E
! " ! # ! $ ! " ! $ ! #
G% E G%
1 & $Terdapat tiga buah rumah , , dan , masing-masing dihubungkan
tiga buah utilitas -air* +, gas* +, dan listrik* +- dengan alat pengantar
*pipa, kabel, dsb+. Mungkinkah membangun utilitas sehingga
! ! !
% G E
tidak ada
pengantar yang saling berp(t(gan;*sebab kalau berp(t(ngan dikhawatirkan
timbul masalah yang serius, misalnya bila kabel listrik berp(t(ngan dengan
pipa gas dapat terjadi ledakan+
$,$6raf / bukan 6raf 9lanar

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 22/44
)ontoh
6ambarkan graf planar di bawah ini sehingga tidak ada sisi-sisi yang berp(t(ngan *menjadi graf bidang+.
0awab4
)usun kembali sebuah simpul untuk mendapatkan sebuah s(lusi.

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 23/44
RmsEler
)isi pada graf bidang membagi bidang datar menjadi beberapa wilayah
* atau +.
0umlah wilayah pada bidang datar termasuk wilayah luar.
0umlah wilayah pada graf planar sederhana dapat dihitung d
region face
engan rumus,
&
atau
&
yang dalam hal ini,
jumlah simpul
jumlah sisi
n e f
f e n
n
e
− + =
= − +

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 24/44
)ontoh
&"
&' &$ &#
&(
&)
Tentukan jumlah wilayah pada graf planar berikut3
0awab4
& 11 &
0adi, jumlah wilayahnya
f e n= − + = − + =

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 25/44
)ontoh
Misalkan graf sederhana planar dan terhubung memiliki &% buah simpul,
masing-masing simpul berderajat %. =epresentasi planar dari graf tersebut
membagi bidang datar menjadi sejumlah wilayah atau muka. Berapa banyak
wilayah yang terbentuk;
0awab4
iketahui &%, maka jumlah derajat seluruh simpul adalah &% % 5.
Menurut lemma jabat tangan, jumlah derajat & jumlah sisi, sehingga
jumlah derajat 50umlah sisi * + %.& &
ari ru
n
e
×
×
mus >uler, - &, sehingga
& -
& - &% %
&
n e f
f jumlah wilayah n e
buah
+ =
= = +
= +
=

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 26/44
KetidaksamaanEler
)etiap daerah pada graf planar dibatasi (leh tiga atau lebih sisi. 0adi,
t(tal banyaknya sisi lebih besar atau sama dengan $ . Tetapi, karena
suatu sisi barada pada batas paling banyak dua wilayah, mak
f
a t(tal
banyaknya sisi lebih kecil atau sama dengan & . 0adi,
&& $ atau
$dari rumus >uler, - &
&sehingga4 &
$
& 1
- & - - &$ $
1- & $ *ketidaksamaan >uler+
$
e
ee f f
f e n
ee n
e
e n e n
e n e n
≥ ≥
= +
≥ − +
− ≥ + ⇒ ≥ +
≤ ⇒ ≤ −
)uatu graf dikatakan planar jika memenuhi ketidaksamaan >uler.
0ika tidak memenuhi maka graf dikatakan tidak planar.

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 27/44
* (
)ontoh
%9ada graf / berikut, %, . Tentukan apakan graf tersebutmemenuhi ketidaksamaan >uler;
n e= =
%
0awab4
$ - $*%+ -
karena , maka graf / dikatakan memenuhi
ketidaksamaan >uler $ - . Maka graf tersebut merupakan graf plannar
n
e
e n
= =
=
≤

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 28/44
)ontoh
* '
'9ada graf / berikut, ', 1#. Tentukan apakah graf di bawah ini
memenuhi /etidaksamaan >uler;
n e= =
'
'
0awab4$ - $*'+ - 5
/arena 1# 5, maka graf / dikatakan
tidak memenuhi /etidaksamaan >uler $ - .
Artinya graf / tidak planar.
n
e
e n
= =
= >
≤

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 29/44
9erlu diketahui bahwa /etidaksamaan >uler
merupakan < 7bukan7 .
Artinya jika suatu graf memenuhi /etidaksamaan >uler,
maka belum tentu graf tersebut planar.
syarat perlu syarat cukup

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 30/44
* $+$
)ontoh
$,$9ada graf bipartit / berikut, , 5. Tentukan apakah graf tersebutmemenuhi /etidaksamaan >uler;
n e= =
$,$
0awab4
$ - $*+ - 1&
idapat 5 1&. ?alaupun memenuhi ketidaksamaan >uler,
kita telah mengetahui bahwa graf / bukan graf planar.
n
e
= =
= <

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 31/44
$,$2ntuk menunjukkan bahwa / bukan graf planar menurut
ketidaksamaan >uler, kita perlu membuat asumsi baru bahwa setiap wilayah
pada graf bidang dibatasi (leh paling sedikit empat buah sisi *% +,
sehi
f
ngga berlaku ketidaksamaan4
& % atau&
dari rumus >uler, - &
sehingga4 - &&
- - & - - && &
- & & - %
&
ee f f
f e n
e
e n
e ee n n
en e n
≥ ≥
= +
≥ +
≥ + ⇒ ≥ +
≤ ⇒ =
$,$
$,$
dengan demikian, graf tidak memenuhi ketidaksamaan & - %, karena
5<
5 &*+ - % * +
hal ini berarti bahwa bukan graf planar.
* e n
e n
salah
*
≤
= =
≤ =

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 32/44
TeoremaKrato-ski
)ifat graf /urat(wski4
1. /edua jenis graf /urat(wski adalah graf teratur.
&. /edua graf kurat(wski adalah graf tidak planar.
$. 9enghapusan sisi atau simpul dari graf kurat(wski menyebabkan menjadi
graf planar.%. 6raf kurat(wski pertama adalah graf tidak planar dengan jumlah simpul
minimum, sedangkan graf kurat(wski keda adalah graf tidak planar
dengan jumlah sisi minimum. /eduanya adalah graf tidak planar paling
sederhana.
'
Menurut /urat(wski terdapat & jenis graf tidak planar, yaitu4
1. 6raf lengkap yang mempunyai ' buah simpul */ +, adalah
graf tidak planar.
&. 6raf terhubung teratur dengan buah simpul dan 5 buah $,$sisi*/ +
adalah graf tidak planar.

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 33/44
f e d
ca b
G
a b c
d e f
G"
' $,$
1
6raf adalah tidak planar jika dan hanya jika mengandung upagraf
yang is(m(rfik dengan atau atau h(m(erfik dengan
satu dari keduanya.
9erhatikan graf berikut. 6raf mengandung yang is(m(r
G
* *
G G
$,$
fik
dengan graf , jadi tidak planar. * G

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 34/44
d a
e f
a
b c
g d
b c
f
G"
G
a b c
d e f * $+$
e
1 $,$6raf tidak planar karena upagrafnya is(m(rfik dengan .G G *

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 35/44
v
x
y
* 'G"G
.omeomork
1 &ua graf 6 dan 6 dikatakan @(me(m(rfik jika salah satu dari kedua graf
tersebut dapat diper(leh dari graf yang lain dengan cara menyisipkan dan atau
membuang secara berulang-ulang simpul yang 7berderajat &7.
& 1
$ &
/etiga graf diatas adalah @(me(m(rfik satu sama lain.
6raf 6 didapat dengan menghilangkan simpul pada 6 .
)edangkan 6 didapat dari 6 dengan menambahkan simpul dan .
v
x y

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 36/44
)ontoh
%
&
1
' $
1#
5
%
&
1
' $
5
%
&
1
' $
%&
'$1
9erlihatkan dengan te(rema /urat(wski bahwa graf 9etersen di bawah
ini tidak 9lanar3
Buatlah sebuah upagrafnya
dengan membuang simpul-
simpul berderajat &.
&
1
/ita akan per(leh
yang h(me(m(rfik
dengan .
G
G
* + 6raf 9etersenG1
* + 2pagraf dariG G
& 1* + @(me(m(rfik denganG G
$,$ &* +h(me(m(rfik dengan * G

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 37/44
Terapan Graf
Planar9erhatikanlah bahwa te(rema /urat(wski lebih mudah digunakan untuk
menentukan bahwa sebuah graf tidak planar. 2ntuk membuktikan bahwa
suatu graf planar relatif lebih sulit.
Terapan graf planar , yaitu pers(alan utilitas dalam merancang jaringan pipa
air, pipa gas, dan kabel listrik bawah tanah agar ketiganya tidak saling
bersilangan. Terapan graf planar lainnya adalah pada perancangan
integrated circuit *8:+ pada sebuah papan. /awat-kawat yang menghubungkan
simpul-simpul 8: harus dirancang sedemikian rupa agar tidak bersilangan,
sebab persilangan dua buah kawat yang beraliran listrik dapat menimbulkan
interferensi arus, yang mengakibatkan terganggunya fungsi 8: tersebut.

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 38/44
GrafDal
Misalkan kita mempunyai sebuah graf planar yang direpresentasikan
sebagai graf bidang. /ita dapat membuat suatu graf bidang B yang secara
ge(metri merupakan dual dari graf tersebut dengan cara4
1.
G
G
9ada setiap wilayah atau muka * + di , buatlah sebuah simpul B
yang merupakan simpul untuk B .
&. 2ntuk setiap sisi di , tariklah sisi B yang mem(t(ng sisi tersebut.
6raf yang ter
face f G v
G
e G e e
bentuk dengan cara penggambaran demikian disebut graf dual
* + dari graf .dual geometri G

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 39/44
v",
v#,
v$,
e,
)ebuah graf memiliki dual hanya jika graf tersebut merupakan graf plannar.
9embentukan graf dual 6B dari graf 6.

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 40/44
e-
e) e'
e(
e#
e$e"
e-
e) e'
e#
e$
e"
e(
9erhatikan dua representasi bidang yang berbeda dari graf
yang sama di bawah ini.
Telah nyata bahwa kedua graf di atas adalah is(m(rfik.
Calu apakah graf dualnya juga akan is(m(rfik;
6raf dualnya akan dipaparkan pada slide selanjutnya.

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 41/44
9erhatikan graf pertama di bawah ini.
i atas merupakan graf dualnya.

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 42/44
9erhatikan graf pertama di bawah ini.
i atas merupakan graf dualnya.

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 43/44
ari kedua graf dual tersebut dapat kita gambar sebagai berikut.
ari kedua graf dual di atas,
telah terlihat bahwa ternyata keduanya tidak is(m(rfik.

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual
http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 44/44
Demikian presentasidari kami
emoga Bermanfaat
TERIMA KAI.