Minggu ke II Dua isomer hidrokarbon dengan rumus molekul C4H10 disajikan pada Gambar 2.1. H H H H H H H H H H H H C C C C C C H H H H H H H H Gambar 2.1 Dalam bahasa teori graf kedua graf ini tidak isomorfik. Dengan perkataan lain bahasa teori graf bagi persoalan memeriksa isomer-isomer hidrokarbon ialah memeriksa keisomorfikan graf-graf. Kita telah mengenal dua bentuk sajian graf, dengan sajian geometrik (diagram simpul-simpul) dan dengan sajian himpunan (mendaftar himpunan simpul-simpulnya dan himpunan sisi-sisinya). Kedua bentuk sajian ini tidak praktis untuk graf-graf yang simpul-simpul dan sisi-sisinya sangat banyak dan juga tidak dapat diolah oleh komputer. Bentuk sajian lainnya yang ternyata dapat diproses oleh komputer ialah dengan menggunakan matriks yang memuat informasi tentang ikatan yang ada di antara simpul-simpulnya atau hubungan kehadiran simpul pada sisi grafnya. Masing-masing matriks ini dikenal sebagai matriks ikatan dan matriks kehadiran. Contoh 2.1. Ikatan yang ada di antara keempat simpul graf pada Gambar 2.2 dapat diungkapkan dalam bentuk matriks berdimensi 4x4 seperti berikut :
v1 v2 v3 v4 0 1 0 1 v1 V1 V2 A 1 0 1 2 v2 0 1 0 1 v3 1 2 1 0 v4 Informasi yang terdapat dalam unsur-unsur matriks A ialah banyaknya sisi yang simpul-simpul ujungnya terletak pada V4 V3 baris dan lajur yang sepadan; misalnya, karena ada satu sisi Gambar 2.2 yang simpulnya v1 dan v2, maka a12 = a21 = 1. Akan tetapi a13 = a31 = 0 karena tidak ada sisi yang menghubungkan simpul v1 dan v3. Matriks A ini disebut matriks ikatan dan dengan sendirinya selalu setangkup. Karena graf ini tidak mempunyai gelang, setiap unsur pada diagonal utama matrks A bernilai 0; jumlah unsur-unsur baris atau kolom sama dengan derajat simpul padanannya, misal 4
4
j 1
i 1
aij a i1 2d v1 8
Dengan penalaran semacam secara umum dapat dikatakan bahwadan informasi adavpada DEFINISI. Misalkan G = ini, (V, E) merupakan graf dengan n simpul V = {v1yang , v2, …, n}. matriks ikatan Adapat digunakan untuk membuat sajian geometrik grafnya. Matriks A= (a ) berdimensi n x n disebut matriks ikatan jika a sama dengan banyaknya sisi ij
ij
yang menghubungkan simpul vteorema i dan vj.berikut yang telah diteladankan pada contoh 9. Akibat dari definisi ini diperoleh Akibat dari definisi ini diperoleh teorema berikut yang telah diteladankan pada contoh 1. TEOREMA 2.1. Misalkan matriks A= (aij) berdimensi n x n merpakan matriks ikatan graf G= (V, E). (1) Matriks A selalu setangkup dan graf G mempunyai n simpul (2) Unsur-unsur diagonal utama aii= 0, untuk i = 1, 2, …, n, mencirikan G tidak mempunyai gelang. (3) Unsur-unsur matriks A bernilai 1 atau 0 jika G merupakan graf sederhana. (4) Jika graf G tanpa gelang, maka jumlah unsur-unsur setiap baris atau kolom matriks A sama dengan derajat setiap simpul padanannya, misalnya untuk simpul v3 diperoleh
d v3 j1 a3j (jumlah baris ke 3) atau d v3 j1 ai3 (jumlah lajur ke-3) Contoh 2.2. Matriks ikatan A berikut ini menjelaskan bahwa grafnya mempunyai 3 simpul dan 2 sisi, terpencil, simpul v2 mempunyai satu gelang, dangeometriknya ada satu sisi dengan (5)vDari matriks Asimpul ini selalu dapat dibangkitkan graf dalam bentuk sajian 3 merupakan simpuldengan ujung nv1simpul dan v2,dan sehingga sajian seperti tampak pada Gambar m sisi,bentuk sedangkan m geometriknya = jumlah unsur-unsur diagonal utama dan di2.3. bawah diagonal utama matriks A. v1 nol v2 vmencirikan 3 (6) Semua unsur baris ke-i dan kolom ke-i sama dengan vi simpul terpencil. 0 1 0 v 1 V1 A 1 1 0 v 2 0 0 0 v 3 • V3 V2 n
Gambar 2.3 .
n
Matriks kehadiran merupakan suatu alternatif lain untuk mencirikan graf seperti diteladankan di bawah ini.
Contoh 2.3. Karena graf pada Gambar 2.2 mempunyai 4 simpul dari 6 sisi, maka hubungan kehadiran simpul-simpul pada sisi grafnya dapat diungkapkan dalam bentuk matriks berdimensi 4 x 6 seperti berikut.
e1 e2 e3 e4 e5 e6 1 0 0 1 0 0 1 1 0 0 1 1 H 0 1 1 0 0 0 0 0 1 1 1 1 Tampak bahwa unsur-unsur matriks A hanya bernilai bergantung kepada hadir atau tidaknya suatu simpul pada 9
v1 v2 v3 v4 0 atau 1 suatu sisi;
V1
V2
e1 e5
e4 V4
e2
e6 e3
V3
misalnya, karena simpul v1 hadir pada sisi e1 dan e4, maka h11= h14= 1. Akan tetap h13= i , h23= 0 karena simpul v1 dan v2 tidak hadir pada sisi e3. Matriks H ini disebut matriks kehadiran. Dapat diamati bahwa setiap kolom matriks H mempunyai tepat dua unsur bernilai 1, karena setiap sisi mempunyai dua simpul ujung; banyaknya unsur 1 pada setiap baris sama dengan derajat simpul yang sepadan dengannya, misalnya : 6
h2j j1
4 d v2
Selanjutnya kolom-kolom identik mencerminkan sisi-ganda, misalnya kolom ke-5 dan ke-6. Dengan penalaran semacam ini, secara umum dapat dikatakan bahwa informasi yang ada pada matriks kehadiran H dapat digunakan untuk membuat sajian geometrik grafnya. DEFINISI. Misalkan G = (V, E) merupakan graf dengan n simpul dan m sisi, V = {v1, v2, …, vn}, dan E= {e1, e2, …, em}. Matriks H = (hij) berdimensi n x m disebut matriks kehadiran jika 1 jika vi hadir pada sisi e hij 0 dalam hal lainnya Akibat dari definisi ini diperoleh teorema berikut yang telah diteladankan pada Teladan 2.1. TEOREMA 2.2. Misalkan matriks H = (hij) berdimen n x m merupakan matriks kehadiran graf G = (V, E). (1) Graf G mempunyai n simpul dan m sisi (2) Setiap kolom matriks A mempunyai tepat dua unsur 1, kecuali kolom yang berpadanan dengan gelang hanya mempunyai satu unsur 1. (3) Kolom-kolom identik mencarikan sisi ganda (4) Jika graf G tanpa gelang, maka jumlah unsur-unsur setiap baris matriks H sama dengan derajat setiap simpul padanannya, misalnya untuk simpul v1 diperoleh
d v1
m
hij j 1
(5) Dari matriks A ini selalu dapat dibangkitkan graf dalam bentuk sajian geometriknya dengan n simpul dan m sisi. (6) Baris ke-i bernilai nol mencarikan vi simpul terpencil. Contoh 2.4. Matriks kehadiran H berikut ini menjelaskan bahwa grafnya mempunyai 3 simpul dan 2 sisi, v2 merupakan simpul terpencil, simpul v3 mempunyai satu gelang, v1 dan v3 hadir pada sisi e1, sehingga bentuk sajian geometriknya seperti pada Gambar 2.4.
10
e1 1 H 0 1
e2 0 v1 0 v2 1 v3
V1 e2
e1 V3
V2 •
Gambar 2.4
Soal-soal Latihan (1) Perhatikanlah graf G = (V, E) pada Gambar di bawah ini : a) b) c) d) e)
Jawablah pertanyaan-pertanyaan berikut ini : v Tentukanlah anggota-anggota himpunan V dan E Tentukanlah derajat setiap simpulnya z Periksalah kebenaran Lemma Persalaman dan Teorema 2.2. u w Gambarlah suatu graf yang isomorfik dengan graf tersebut sehingga tidak ada sisi yang saling berpotongan selain pada y x simpul-simpul ujungnya. f) Tentukanlah himpunan simpul yang berkaitan dengan v3. g) Tentukanlah himpunan sisi yang berkaitan dengan e2. h) Tentukanlah himpunan sisi dengan simpul v1 hadir pada sisi itu i) Sajikanlah matriks ikatan graf ini j) Sajikanlah matriks kehadiran graf ini. (2) Periksalah apakah ada graf G = (V, E) untuk setiap persoalan berikut. Jika graf ini ada, sajikanlah gambarnya a) Graf G dengan dua simpul berderajat dua dan satu simpul berderajat enam. b) Graf G dengan dua simpul berderajat satu, dua simpul berderajat dua, dan satu simpul berderajat tiga c) Graf G dengan dua simpul berderajat satu, satu simpul berderajat dua, dua simpul berderajat tiga, dan satu simpul berderajat empat. d) Semua simpul G berderajat ganjil e) Semua simpul G berderajat genap. (3) Jelaskanlah apakah ada hidrokarbon yang mempunyai atom Hidrogen dan atom Karbon seperti berikut : a) 7 atom Karbon dan 13 atom Hidrogen b) 4 atom Karbon dan 7 atom Hidrogen c) 5 atom Karbon dan 6 atom Hidrogen (4) Berapakah banyaknya atom Hidrogen pada suatu ikatan hidrokarbon tanpa sisi ganda dengan a) satu atom 11
b) c) d) e)
dua atom tiga atom empat atom C n atom C
(5) Berapakah banyaknya simpul yang dimiliki graf dengan ciri seperti berikut : a) Memiliki 12 sisi dan setiap simpulnya berderajat 2. b) Memiliki 15 sisi, 3 simpul berderajat 4, dan simpul-simpul lainnya berderajat 3. c) 20 sisi dan semua simpulnya berderajat sama. (6) Berikan sajian geometrik, matriks ikatan, dan matriks kehadiran graf G dengan lima simpul dan delapan sisi dan mempunyai ciri seperti berikut : a) b) c) d)
G graf sederhana G graf ganda G bukan graf ganda dan mempunyai gelang G graf ganda dan mempunyai gelang.
(7) Berikan sajian geometrik graf G dengan 7 simpul dan setiap simpulnya berderajat 2. Bagaimanakah bentuk matriks ikatan dan matriks kehadirannya ? (8) Berikan sajian geometrik graf G dengan 7 simpul dan 6 sisi sedemikian sehingga ada dua simpul berderajat satu, dan simpul lainnya berderajat 2. Bagaimanakah bentuk matriks ikatan dan matriks kehadirannya ? (9) Perhatikan bahwa dalam suatu organisasi yang jumlah anggotanya paling sedikit dua orang selalu ada dua anggotanya yang masing-masing mempunyai teman yang sama banyaknya dalam kelompok tersebut. (10) Jika G = (V, E) merupakan graf sederhana dengan n simpul, perlihatkan bahwa d(v) < n-1, untuk v V . (11) Perlihatkan bahwa maksimum banyaknya sisi pada graf sederhana dengan n simpul ialah n(n–1)/2 (12) Berapakah maksimum banyaknya simpul dari suatu graf dengan 19 sisi dan semua simpulnya paling sedikit berderajat 3 ?. (13) Apakah ada sebuah kelompok yang terdiri atas tujuh puluh orang sehingga setiap anggotanya bersahabat karib dengan tepat tiga anggota lainnya dalam kelompok ini ? (14) Periksalah apakah pasangan graf di bawah ini isomorfik a)
b) 12
G1
G c)
G
G1
G
G1
d)
G1
G e)
f)
G1
G
G1
G
(15) Susunlah matriks ikatan dan matriks kehadiran bagi graf-graf berikut; periksa pula sifatsifat matriks yang diperoleh a) V2
e3 e8
e7
V1
V5
e4
e6
V6
e1 e2 V4 V5
V1
e4
•V3 e5
e7
V6
V2
e6
e4
e5 e6
V4
V2
e3
e8 e3
d) V1
V1
e7
e5
V5
c)
(16)
e1 e2
V4
e2 e1
b)
V3
V3
e1 V5 e3 e2
V2 V3
e4
V4
e5 V6
e6
Berikanlah sajian geometrik bagi graf yang matriks ikatannya ialah
13
V7
0 0 1 1 1 1 1 2 a) b) 0 1 2 0 1
1 0 1 0 1 0 c) 1 0 0 0 0 0
0 1 1 1 0
1 1 1 0 0 1 1 0 0 0 2 1 0 0 1 1 d) 0 0 2 1 0 1 1 1 1 1 1 1 1 0
0 1 1 0 1 1 0 0 0 0 0 1 0 1 0
Susunlah matriks kehadirannya (17)
Berikan sajian geometrik graf yang matriks kehadirannya ialah
1 1 a) 0 0
0 1 1 0 1 0 0 1
1 1 b) 0 0
1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1
1 1 c) 0 0 0
1 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1
1 1 d) 0 0 0
0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0
Susunlah matriks ikatannya !. (18)
Perhatikanlah graf G= (V, E) dengan V = {1,2,3,4,5} dan E = {(1,2), (2,3), (3,5), (2,5), (2,4), (4,5), (1,4), (1,5)}. a) Susunlah matriks ikatan dan matriks kehadirannya! b) Tentukan derajat setiap simpulnya dan tentukan pula himpunan simpul-simpul berderajat ganjil!
14
