Graf 2020 Bagian2
Graf 2020 Bagian2
Graf 2020 Bagian2
2)
Bahan Kuliah
IF2120 Matematika Diskrit
A = [aij],
1, jika simpul i dan j bertetangga
aij = {
0, jika simpul i dan j tidak bertetangga
1 1
1
2 5
3
2 3
3
2 4
4 4
1 2 3 4 1 2 3 4 5 1 2 3 4
1 0 1 1 0 0
1 0 1 1 0 1 0 1 0 0
2 1 0 1 0 0
2 1 0 1 1 2 1 0 1 1
3 1 1 0 1 0
3 1 1 0 1 3 1 0 0 0
4 0 0 1 0 0
4 0 1 1 0 4 0 1 1 0
5 0 0 0 0 0
(a) (b) (c)
1
e1 e4
e3
e2
2 e8
e6 3
e5
e7
4
1 2 3 4
1
0 1 2 0
2 1 0 1 1
3 2 1 2 2
4 0 1 2 0
3
Derajat tiap simpul i:
(a) Untuk graf tak-berarah
n
d(vi) = aij
j =1
n
dout (vi) = jumlah nilai pada baris i = a
j =1
ij
10 12
8
e b
15 9
11
d 14 c
a b c d e
a 12 10
b 12 9 11 8
c 9 14
d 11 14 15
e 10 8 15
A = [aij],
1 1
1
2 5
3
2 3
3
2 4
4
4
0 1 0 0 1
1 0 1 1 1
0 1 1 1 0
0 1 1 0 1
1 1 0 1 0
1
3
5 4
5 4
• Dua buah graf, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu
antara simpul-simpul keduanya dan antara sisi-sisi keduaya sedemikian sehingga
hubungan kebersisian tetap terjaga.
• Dengan kata lain, misalkan sisi e bersisian dengan simpul u dan v di G1, maka sisi e’
yang berkoresponden di G2 harus bersisian dengan simpul u’ dan v’ yang di G2.
• Dua buah graf yang isomorfik adalah graf yang sama, kecuali penamaan simpul dan
sisinya saja yang berbeda. Ini benar karena sebuah graf dapat digambarkan dalam
banyak cara.
Rinaldi Munir/IF2120 Matematika Diskrit 10
3 d c v w
1 2 a b x y
a v w
e
c
b d
x y
(a) G1 (b) G2
a b c d e x y w v z
a 0 1 1 1 0 x 0 1 1 1 0
b 1 0 1 0 0 y 1 0 1 0 0
AG1 = c 1 1 0 1 0 AG2 = w 1 1 0 1 0
d 1 0 1 0 1 v 1 0 1 0 1
e 0 0 0 1 0 z 0 0 0 1 0
(a)
(b)
Gambar (a) Dua buah graf isomorfik, (b) tiga buah graf isomorfik
Namun, ketiga syarat ini ternyata belum cukup menjamin. Pemeriksaan secara
visual perlu dilakukan, seperti contoh dua buah graf di bawah ini:
w
u
x
y
Simpul y bertetangga dengan hanya satu simpul
v
berderajat 1
Simpul x bertetangga dengan u dan v
yang masing-masing berderajat 1 Kesimpulan: kedua graf tidak isomorfik
Latihan
• Apakah pasangan graf di bawah ini isomorfik?
a p
e t
d h f b s w u q
g v
c r
a b p q
e f t
u
d c s r
• Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling
memotong (bersilangan) disebut graf planar,
• jika tidak, maka ia disebut graf tak-planar.
• Contoh: K4 di bawah ini adalah graf planar:
Tiga buah graf planar. Graf (b) dan (c) adalah graf bidang
H1 H2 H3 H1 H2 H3
W G E W G E
(a) (b)
(a) Graf persoalan utilitas (K3,3), (b) graf persoalan utilitas bukan graf planar.
R2 R3 R4
R6
R5
R1
R2 R3 R4
R6
R5
R1
Pada graf K5, n = 5 dan e = 10, tidak memenuhi ketidaksamaan Euler sebab
10 3(5) – 6. Jadi, K5 tidak planar
K4 K5 K3,3
Rinaldi Munir/IF2120 Matematika Diskrit 30
Ketidaksamaan e 3n – 6 tidak berlaku untuk K3,3
karena
e = 9, n = 6
9 (3)(6) – 6 = 12 (jadi, e 3n – 6)
Buat asumsi baru: setiap daerah pada graf planar dibatasi oleh
paling sedikit empat buah sisi,
H1 H2 H3 H1 H2 H3
W G E W G E
Teorema Kuratowski
v y
x
G1 G2 G3
a b a b
c c
f e d f e d
G1
G
Graf G tidak planar karena ia mengandung upagraf yang sama dengan K3,3.
a a a
i b i b
h c h c h c
d d
g f e g f e g e
G G1 K5
6 7 2 6 7 2 6 2
10
9 8 3 9 8 3 3
5 5 5
4 4 4
(a) Graf Petersen, G (b) G1 (c) G2
1 3 5
Gambar (a) Graf Petersen
(b) G1 adalah upagraf dari G
(c) G2 homeomorfik dengan G1
(d) G2 isomorfik dengan K3,3
2 4 6
(d) K3,3
Rinaldi Munir/IF2120 Matematika Diskrit 40
Latihan
G* G