Matematika DIskret Graf
Graf
1. Berdasarkan orientasi arah
a. Graf tak berarah (undirect graf) adalah graf yang orientasi sisinya tidak mempunyai arah
b. Graf berarah(direct graf) adalah graf orientasi sisinya mempunyai arah
sisi yang berarah
- Terminologi dasar
1. Bertetangga (adjacent) adalah 2 buah graf yang terhubung langsung dengan sebuah sisi.
2. Bersisian (insident) adalah sembarang sisi yang bersisian dengan simpul u dan v
3. Simpul terpencil (isolated vertex) adalah simpul yang tidak bertetanggaan dengan simpul2 lainnya
4. Graf kosong (null graph or empty graph) adalah graf yang himpunan sisinya adalah himpunan kosong
5. Derajat (degree) adalah suatu simpul pada graf takberarah adalah jumlah sisi yang bersisian dengan simpul tersebut
6. Lintasan (path) adalah panjang dari simpul awal hingga akhir
7. Siklus (cycle)/ sirkuit (circuit) adalah lintasan yang berawal dan berahir pada simpul yang sama
8. Terhubung (connected) adalah dua simpul yang terhubung
9. Upagraf (subgraph)
dan komplemen upagraf
10. Upagraf merentang (spanning subgraf)
11. Cut set
12. Graf berbobot (Weight graph) adalah graf yang setiap sisinya diberi sebuah harga (bobot)
- Beberapa graf sederhanga khusus
1. Graf lengkap (complete graph) adalah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya.
2. Graph lingkaran adalah graph sederhana yang setiap simpulnya berderajat dua
3. Graph teratur (regular graph) adalah setiap simpulnya mempunyai derajat yang sama
4. Graph bipartit (bipartite graph) adalah graph yang himpunan simpulnya dapat dikelompokkan menjadi 2 himpunan
- Representasi graph
1. Matriks ketetanggaan (adjacency matrix)
2. Matriks bersisian (incidency matrix)
3. Senarai ketetanggaan (adjacency list)
- Graph isomorfik
Adalah dua buah graph, G1 dan G2 terdapat korespodensi satu-satu antara simpul-simpul keduanya.
- Graph planar dan graph bidang
Graf planar adalah graf yang dapat digambarkan pada bidang datar dengan sisi yang tidak saling memotong (berpotongan). sedangkan graf bidang adalah representasi dari graf planar
Rumus euler
n-e-f=2
e=jumlah sisi
n=jumlah simpul
- Teorema kuratowski
Graf g adalah tidak planar jika dan hanya jika ia mengandung upagraf yang isomorfik dg k5 atau k3,3 atau homeomorfik dengan salah satu dari keduanya.
dalam literatur dalam graf, matematikawan Polandia, Kasimir Kuratowski menemukan sifat yang unik:
1. graf lengkap yang mempunyai 5 buah simpul(K5) adalah graf tidak planar
2. graf terhubung teratur dengan 6 buah simpul dan 9 buah sisi (K3,3) adalah graf tidak planar
- Sifat graf kuratowski
1. kedua graf kuratowski adalah graf teratur
2. kedua graf kuratowski adalah graf tidak planar
3. penghapusan sisi atau simpul dari graf kuratowski menyebabkan menjadi graf planar
4. graf kuratowski pertama adalah graf tidak planar dengan jumlah simpul minimum. dan graf kuratowski kedua adalah graf tidak planar dengan jumlah sisi minimum. keduanya adalah graf tidak planar paling sederhana.
A. Graph dual (dual graph)
Adalah graf yang terbentuk dengan cara penggambaran di titik luar dari graf yang asli
B. Lintasan dan sirkuit euler
Lintasan euler adalah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali. bila lintasan tersebut kembali ke asal, sehingga membentuk lintasan tertutup maka disebut sirkuit euler.
C. Lintasan dan sirkuit hamilton
Lintasan hamilton adalah lintasan yang melalui tiap simpul didalam graf tepat satu kali. bila lintasan itu kembali ke asal membentuk lintasan tertutup(sirkuit), maka lintasan tersebut adalah sirkuit hamilton.
1. Lintasan terpendek (shortest path)
Graf yang digunakan mencari lintasan terpendek adalah graf berbobot (weighted graph).
ada beberapa macam persoalan lintasan terpendek antara lain :
1. Lintasan terpendek antara 2 buah simpul tertentu
2. Lintasan terpendek antara semua pasangan simpul
3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.
4. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.
1. Berdasarkan orientasi arah
a. Graf tak berarah (undirect graf) adalah graf yang orientasi sisinya tidak mempunyai arah
b. Graf berarah(direct graf) adalah graf orientasi sisinya mempunyai arah
sisi yang berarah
- Terminologi dasar
1. Bertetangga (adjacent) adalah 2 buah graf yang terhubung langsung dengan sebuah sisi.
2. Bersisian (insident) adalah sembarang sisi yang bersisian dengan simpul u dan v
3. Simpul terpencil (isolated vertex) adalah simpul yang tidak bertetanggaan dengan simpul2 lainnya
4. Graf kosong (null graph or empty graph) adalah graf yang himpunan sisinya adalah himpunan kosong
5. Derajat (degree) adalah suatu simpul pada graf takberarah adalah jumlah sisi yang bersisian dengan simpul tersebut
6. Lintasan (path) adalah panjang dari simpul awal hingga akhir
7. Siklus (cycle)/ sirkuit (circuit) adalah lintasan yang berawal dan berahir pada simpul yang sama
8. Terhubung (connected) adalah dua simpul yang terhubung
9. Upagraf (subgraph)
dan komplemen upagraf
10. Upagraf merentang (spanning subgraf)
11. Cut set
12. Graf berbobot (Weight graph) adalah graf yang setiap sisinya diberi sebuah harga (bobot)
- Beberapa graf sederhanga khusus
1. Graf lengkap (complete graph) adalah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya.
2. Graph lingkaran adalah graph sederhana yang setiap simpulnya berderajat dua
3. Graph teratur (regular graph) adalah setiap simpulnya mempunyai derajat yang sama
4. Graph bipartit (bipartite graph) adalah graph yang himpunan simpulnya dapat dikelompokkan menjadi 2 himpunan
- Representasi graph
1. Matriks ketetanggaan (adjacency matrix)
2. Matriks bersisian (incidency matrix)
3. Senarai ketetanggaan (adjacency list)
- Graph isomorfik
Adalah dua buah graph, G1 dan G2 terdapat korespodensi satu-satu antara simpul-simpul keduanya.
- Graph planar dan graph bidang
Graf planar adalah graf yang dapat digambarkan pada bidang datar dengan sisi yang tidak saling memotong (berpotongan). sedangkan graf bidang adalah representasi dari graf planar
Rumus euler
n-e-f=2
e=jumlah sisi
n=jumlah simpul
- Teorema kuratowski
Graf g adalah tidak planar jika dan hanya jika ia mengandung upagraf yang isomorfik dg k5 atau k3,3 atau homeomorfik dengan salah satu dari keduanya.
dalam literatur dalam graf, matematikawan Polandia, Kasimir Kuratowski menemukan sifat yang unik:
1. graf lengkap yang mempunyai 5 buah simpul(K5) adalah graf tidak planar
2. graf terhubung teratur dengan 6 buah simpul dan 9 buah sisi (K3,3) adalah graf tidak planar
- Sifat graf kuratowski
1. kedua graf kuratowski adalah graf teratur
2. kedua graf kuratowski adalah graf tidak planar
3. penghapusan sisi atau simpul dari graf kuratowski menyebabkan menjadi graf planar
4. graf kuratowski pertama adalah graf tidak planar dengan jumlah simpul minimum. dan graf kuratowski kedua adalah graf tidak planar dengan jumlah sisi minimum. keduanya adalah graf tidak planar paling sederhana.
A. Graph dual (dual graph)
Adalah graf yang terbentuk dengan cara penggambaran di titik luar dari graf yang asli
B. Lintasan dan sirkuit euler
Lintasan euler adalah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali. bila lintasan tersebut kembali ke asal, sehingga membentuk lintasan tertutup maka disebut sirkuit euler.
C. Lintasan dan sirkuit hamilton
Lintasan hamilton adalah lintasan yang melalui tiap simpul didalam graf tepat satu kali. bila lintasan itu kembali ke asal membentuk lintasan tertutup(sirkuit), maka lintasan tersebut adalah sirkuit hamilton.
1. Lintasan terpendek (shortest path)
Graf yang digunakan mencari lintasan terpendek adalah graf berbobot (weighted graph).
ada beberapa macam persoalan lintasan terpendek antara lain :
1. Lintasan terpendek antara 2 buah simpul tertentu
2. Lintasan terpendek antara semua pasangan simpul
3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.
4. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.
Komentar
Posting Komentar