Materi Teori Graf sebelum UTS :
Jawaban yang dikemukakan oleh Euler adalah: orang tidak mungkin melalui ketujuh jembatan itu masingmasing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnyagenap. Yang dimaksud dengan derajat adalah banyaknya garis yang bersisian dengan noktah. Sebagai contoh,simpul C memiliki derajat 3 karena ada tiga buah garis yang bersisian dengannya, simpul B dan D juga berderajat dua, sedangkan simpul A berderajat 5. Karena tidak semua simpul berderajat genap, maka tidak mungkin dilakuk an perjalananan berupa sirkuit (yang dinamakan dengan sirkuit Euler) pada graf tersebut.
II. DEFINISI GRAPH
Graf G didefinisikan sebagai pasangan himpunan (V, E), yang dalam hal ini:
V = himpunan tidak-kosong dari simpul-simpul (vertices atau node) = { v1 , v2 , ... , vn }
dan
E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul = {e1 , e2 , ... , en }
atau dapat ditulis singkat notasi G = (V, E).
CATATAN : menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf
dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graf yang
hanya mempunyai satu buah simpul tanpa sebuah sisi pun dinamakan graf trivial.
Simpul pada graf dapat dinomori dengan huruf, seperti a, b, c, …, v, w, ..., dengan bilangan asli 1, 2, 3, ...,
atau gabungan keduanya. Sedangkan sisi yang menghubungkan simpul vi dengan simpul vj dinyatakan
dengan pasangan (vi, vj) atau dengan lambang e1, e2, …. Dengan kata lain, jika e adalah sisi yang
menghubungkan simpul vi dengan simpul vj , maka e dapat ditulis sebagai
e = (vi , vj)
Secara geometri graf digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dwimatra yang
dihubungkan dengan sekumpulan garis (sisi).
TEORI GRAPH
Graph digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menuyatakan objek dinyatakan sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis.
 * |
Gambar perkotaan |
I. SEJARAH GRAPH
Teori graf pertama kali dikembangkan oleh Leonhard Euler dalam memecahkan masalah jembatan Königsberg (tahun 1736). Permasalahannya adalah " Apakah bisa seseorang melalui sekali setiap jembatan yang menghubungkan kota-kota tersebut, dan kembali lagi ke kota dari mana ia berjalan".
 * |
Gambar1.1 (a) Jembatan Königsberg [ROS99], dan (b) graf yang merepresentasikan jembatan Königsberg |
Jawaban yang dikemukakan oleh Euler adalah: orang tidak mungkin melalui ketujuh jembatan itu masingmasing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnyagenap. Yang dimaksud dengan derajat adalah banyaknya garis yang bersisian dengan noktah. Sebagai contoh,simpul C memiliki derajat 3 karena ada tiga buah garis yang bersisian dengannya, simpul B dan D juga berderajat dua, sedangkan simpul A berderajat 5. Karena tidak semua simpul berderajat genap, maka tidak mungkin dilakuk an perjalananan berupa sirkuit (yang dinamakan dengan sirkuit Euler) pada graf tersebut.
II. DEFINISI GRAPH
Graf G didefinisikan sebagai pasangan himpunan (V, E), yang dalam hal ini:
V = himpunan tidak-kosong dari simpul-simpul (vertices atau node) = { v1 , v2 , ... , vn }
dan
E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul = {e1 , e2 , ... , en }
atau dapat ditulis singkat notasi G = (V, E).
CATATAN : menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf
dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graf yang
hanya mempunyai satu buah simpul tanpa sebuah sisi pun dinamakan graf trivial.
Simpul pada graf dapat dinomori dengan huruf, seperti a, b, c, …, v, w, ..., dengan bilangan asli 1, 2, 3, ...,
atau gabungan keduanya. Sedangkan sisi yang menghubungkan simpul vi dengan simpul vj dinyatakan
dengan pasangan (vi, vj) atau dengan lambang e1, e2, …. Dengan kata lain, jika e adalah sisi yang
menghubungkan simpul vi dengan simpul vj , maka e dapat ditulis sebagai
e = (vi , vj)
Secara geometri graf digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dwimatra yang
dihubungkan dengan sekumpulan garis (sisi).
 * |
Gambar2.1 |
G1 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }
G2 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) }
= { e1, e2, e3, e4, e5, e6, e7}
G3 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }
= { e1, e2, e3, e4, e5, e6, e7, e8}
Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan sisi-ganda (multiple edges atau paralel edges) karena
kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3. Pada G3, sisi e8 = (3, 3)
dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.
Tidak ada komentar:
Posting Komentar