TI Politala Matdis 1C

Graph Isomorfik

Sebelum kita membahas tentang graph isomorfik ada baiknya kita terlebih dahulu mengerti tentang garph.

• Graph merupakan struktur diskrit yang terdiri dari himpunan objek yang disebut simpul (vertices, vertex) dan himpunan sisi (edges) yang menghubungkan simpul-simpul tersebut.
• Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

Graph Isomorfik

Dalam geometri, dua gambar disebut kongruen jika keduanya mempunyai sifat-sifat geometri yang sama. Maka dengan cara yang sama, dua graf disebut isomorfis jika keduanya menunjukkan "bentuk" yang sama, kedua graph tersebut hanya berbeda dalam hal pemberian label titik dan garisnya saja.

Syarat dua buah graph dikatakan isomorfik, yaitu :

1. Memiliki jumlah simpul yang sama
2. Memiliki jumlah garis yang sama
3. Memiliki derajat yang sama dari simpul-simpulnya

Catatan : apabila dua graph yang berbeda tidak memiliki salah satu dari syarat diatas sudah pasti kedua graphtersebut tidak isomorfis, tetapi walaupun kedua graph tersebut memiliki seluruh syarat diatas belum tentu juga keduanya isomorfis.

Ada 2 graf yang memenuhi ketiga syarat tersebut, tetapi keduanya tidak isomorfis. Sebagai contoh adalah graf G dan G' pada Gambar di bawah ini :

Dalam G, satu-satunya titik yang berderajat 3 adalah titik x. Titik x dihubungkan dengan 2 titik lain yang berderajat 1 (titik y dan z). Sebaliknya, dalam G', satu-satunya titik yang berderajat 3 adalah c. Satu-satunya titik berderajat 1 yang dihubungkan dengan c hanyalah titik d, sehingga G tidak mungkin isomorfis dengan G'.

Untuk itu ada beberapa syarat tambahan yang wajib kita penuhi apabila ingin menunjukkan apakah kedua graph tersebut isomorfik atau tidak, yaitu :

1. Graf sederhana G₁ = (V₁, E₁) dan G₂ = (V₂, E₂) adalah  isomorfis jika ada sebuah fungsi bijektif (fungsi satu-ke-satu dan on to) dari V₁ ke V₂ dengan sifat kepemilikan bahwa jika a dan b adalah tetangga pada G₁ jika dan hanya jika  f(a) dan f(b) adalah tetangga di G₂, untuk seluruh  a dan b di V₁.
2. Misalkan sisi e bersisian dengan simpul u dan v di G₁, maka sisi e’ yang berkoresponden di G₂ harus bersisian dengan simpul u’ dan v’ yang di G₂.
3. G₁ dan G₂ adalah isomorfis jika simpul-simpulnya dapat diurut  dengan cara sedemikian rupa sehingga matriks adjacensy M_G1 dan M_G2 adalah identik.

Agar lebih mudah memahami apakah dua graf isomorfik atau tidak, berikut adalah contoh cara menunjukan dua graf yang isomorfik.

CONTOH 1 :

Periksa apakah kedua graf tersebut isomorfik? Jika ya, tentukan simpul-simpul yang saling berkorespondensi antara G₁ dan G₂

Jawab :

Ya,  kedua graf tersebut adalah isomorfik. Terlihat graf tersebut memuat simpul dimana setiap simpulnya masing-masing berderajat tiga. Simpul yang saling berkorespondensi dari kedua graf tersebut adalah :

simpul u1 dengan simpul v1

simpul u2 dengan simpul v3

simpul u3 dengan simpul v5

simpul u4 dengan simpul v6 

simpul u5 dengan simpul v4

simpul u6 dengan simpul v2

Pada dua graf yang isomorfik, kedua graf tersebut memiliki matriks ketetanggaan yang sama, tentunya setelah matriks yang berkorespondensi diurutakan dalam urutan yang sama.

Perhatikan matriks ketetanggaan dari kedua graf  tersebut. Dibawah ini adalah matriks ketetanggaan dari graf G₁ dan G₂:

Terlihat bahwa kedua graf  tersebut  memiliki  matriks  ketetanggaan  yang  sama,   yaitu  M_G1 =  M_G2.

Lintasan dan Sirkuit Euler

Lintasan dan Sirkuit Euler

Lintasan Euler ialah lintasan yang melalui tiap sisi dalam graf tepat sekali

Sirkuit Euler ialah sirkuit yang melalui tiap sisi dalam graf tepat satu kali

Graf yang mempunyai sirkuit Euler disebut graf Euler, sedang graf yang mempunyai lintasan Euler disebut semi Euler

Contoh

a. Apakah Ada Lintasan Euler ?

b. Apakah ada sirkuit Euler ?

Jawab

a. ADA lintasan euler dengan lintasan :

a,b,c,d,e,f,g,b,d,f,a,g

b. Tidak ADA sirkuit Euler.

a. Apakah ada lintasan Euler ?

b. Apakah ada Sirkuit Euler ?

Jawab

a. ADA lintasan Euler dengan lintasan :

a,b,c,d,e,c,h,b,f,h,e,f,g,a

b. Ada sirkuit euler karena berawal dari simpul a dan berakhir di simpul a

Teorema Untuk Lintasan dan sirkuit euler

Graf tak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan mempunyai 2 buah simpul berderajat ganjil atau tidak ada simpul berderajad ganjil samasekali

Graf tak berarah G adalah graf Euler jika hanya jika setiap simpul berderajad genap

Graf berarah G memiliki sirkuit Euler jika hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama kecuali 2 simpul, yang pertama memiliki derajad keluar satu lebih besar dari derajad masuk, dan yang kedua memiliki derajad masuk satu lebih besar dari derajad keluar

Read More

TI Politala Matdis 1C

KOMBINATORIAL

Kombinatorial adalah cabang matematika yang mempelajari pengaturan objek – objek.  Solusi yang ingin kita peroleh dari kombinatorial ini adalah jumlah cara pengaturan objek– objek didalam kumpulanya. Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan (experiment) atau kejadian (event). Percobaan adalah proses fisis yang hasilnya dapat diamati.
1.    Prinsip Penjumlahan (rule of sum)
Jika suatu himpunan A terbagi kedalam himpunan bagian A1, A2, …, An, maka jumlah unsur pada himpunan A akan sama dengan jumlah semua unsur yang ada pada setiap himpunan bagian A1, A2, …,An. Setiap himpunan bagian A1, A2, …, An tidak saling tumpang tindih (saling lepas). Untuk himpunan yang saling tumpang tindih tidak berlaku lagi prinsip penjumlahan, dan ini harus diselesaikan dengan prinsip inklusi-eksklusi. Untuk himpunan yang saling tumpang tindih tidak berlaku lagi prinsip penjumlahan, dan ini harus diselesaikan dengan prinsip inklusi-eksklusi.
Misalkan,
Percobaan 1 : p hasil                    Percobaan 2 : q hasil
maka, Percobaan 1 atau percobaan 2: p + q hasil
Contoh  :
Jumlah mahasiswa laki-laki kelas 1.C adalah 31 orang sedangkan jumlah wanitanya hanya 4 orang. Untuk memilih wakil 1 orang pria dan 1 orang wanita. Berapa banyak cara memilih 2 orang wakil tersebut?
Penyelesaian : 31 x  4 = 124 cara.
2.    Prinsip Perkalian (rule of product)
Misalkan sebuah prosedur dapat dipecah dalam dua penugasan.Penugasan pertama dapat dilakukan dalam n1 cara, dan tugas kedua dapat dilakukan dalam n2 cara setelah tugas pertama dilakukan. Dengan demikian, dalam mengerjakan prosedur tersebut ada (n1 x n2) cara.Secara tidak langsung, pada prinsip perkalian, bisa terjadi saling tumpang tindih (tidak saling lepas).
Misalkan,
Percobaan 1: p hasil        Percobaan 2: q hasil
maka, Percobaan 1 dan percobaan 2: p x q hasil
Contoh
Jumlah mahasiswa laki-laki kelas 1.C adalah 31 orang sedangkan jumlah wanitanya hanya 4 orang. Untuk memilih wakil 1 orang pria dan 1 orang wanita. Berapa banyak cara memilih 2 orang wakil tersebut?
Penyelesaian:
31      4 = 124 cara.
3.    Permutasi
Permutasi merupakan susunan yang mungkin dibuat dengan memperhatikan urutan.Dengan kata lain, permutasi merupakan bentuk khusus aplikasi prinsip perkalian. Menurut kaidah perkalian, permutasi dari n objek adalah n(n – 1)(n – 2) … (2)(1) = n! Rumus permutasi-r (jumlah susunan berbeda dari pemilihan r objek yang diambil dari n objek), dilambangkan dengan P(n,r):
a.       Permutasi dengan pengulangan
Banyaknya permutasi dari n objek n1 yang sama, n2 yang sama, nr yang sama.
4.    Kombinasi
               Bentuk khusus dari permutasi adalah kombinasi.Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan.           Rumus kombinasi-r (jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen), dilambangkan dengan C(n,r) atau ( n   r ) .
5.    Peluang
Teori peluang Kombinatorial dan teori peluang (probability) berkaitan sangat erat. Teori peluang banyak menggunakan konsep-konsep dalam kombinatorial. Sebenarnya kedua bidang ini lahir dari arena judi (gambling games) – salah satu kasusnya adalah menghitung peluang munculnya nomor lotre tertentu. Meskipun demikian, aplikasi kombinatorial dan teori peluang saat ini telah meluas ke berbagai bidang ilmu lain maupun dalam kehidupan nyata seperti ilmu statistika, fisika, ekonomi, biologi, dan berbagai bidang ilmu lainnya.

Read More