Teori graf merupakan cabang matematika yang mempelajari jaringan titik-titik yang dihubungkan oleh garis. Subjek teori graph berawal dari masalah matematika rekreasi, tetapi telah berkembang menjadi area penelitian matematika yang signifikan, dengan aplikasi dalam kimia, riset operasi, ilmu sosial, dan ilmu komputer.
Sejarah teori graf dapat ditelusuri secara khusus ke tahun 1735, ketika matematikawan Swiss Leonhard Euler memecahkan masalah jembatan Königsberg. Masalah jembatan Königsberg adalah teka-teki lama tentang kemungkinan menemukan jalur di atas setiap satu dari tujuh jembatan yang membentang di sungai bercabang yang mengalir melewati sebuah pulau, tetapi tanpa melintasi jembatan apa pun dua kali. Euler berpendapat bahwa tidak ada jalan seperti itu. Pembuktiannya hanya melibatkan referensi ke susunan fisik jembatan, tetapi pada dasarnya dia membuktikan teorema pertama dalam teori graph.
Definisi Graf
Graf G merupakan pasangan dua himpunan yaitu V(G) himpunan tak kosong yang anggotanya disebut titik dan E(G) himpunan yang anggotanya disebut sisi.
Dari definisi diatas dapat disimpulkan bahwa graf adalah kumpulan titik-titik yang dihubungkan oleh garis dari titik satu ke titik lainnya.
Unsur dan Elemen Graf
Berdasarkan definisi graf, graf memiliki dua elemen yaitu titik dan sisi.
Titik dapat disebut juga vertex, simpul, point, atau node. Titik dalam graf yang dapat mewakili persimpangan jalan, daratan, atau lokasi umum, seperti "kantor" atau "sekolah". Titik sering dihubungkan oleh sisi.
Sisi dapat disebut juga edge, rusuk, ruas atau line. Sisi merupakan garis yang menghubungkan pasangan titik. Sisi dapat mewakili hubungan fisik antara lokasi, seperti jalan, atau hanya bahwa ada rute yang menghubungkan dua lokasi, seperti penerbangan maskapai.
Loop adalah jenis sisi atau garis khusus yang menghubungkan titik ke dirinya sendiri. Loop tidak banyak digunakan dalam grafik jaringan jalan.
Sisi ganda, merupakan dua atau lebih garis yang memiliki 2 ujung titik yang sama. Dalam graf tak berarah, dua atau lebih sisi yang bersinggungan dengan dua simpul yang sama, atau dalam graf berarah, dua atau lebih sisi dengan kedua simpul ekor yang sama dan simpul kepala yang sama.
Adjacent (terhubung/bertetangga), dua titik dikatakan bertetangga, jika terdapat sisi atau garis yang menghubungkan kedua titik tersebut. Di sini, kedekatan simpul dipertahankan oleh sisi tunggal yang menghubungkan kedua simpul tersebut. Dalam suatu graf, dua sisi dikatakan bertetangga, jika terdapat sebuah titik persekutuan di antara kedua sisi tersebut. Titik dengan loop "melihat" dirinya sebagai titik yang berdekatan dari kedua ujung sisi sehingga menambahkan dua, bukan satu ke derajat.
Incident (bersisian), sebuah titik bersisian dengan suatu sisi jika titik tersebut adalah salah satu dari dua titik yang dihubungkan oleh sisi tersebut. Insidence adalah pasanga simpul dan merupakan titik tepi.
Isolated vertex (Titik terisolasi) adalah titik yang tidak memiliki sisi atau garis yang menghubungkan titik tersebut dengan titik lainnya.
Lintasan atau Path merupakan rute di sepanjang tepi graf. Sebuah jalur dapat mengikuti satu sisi secara langsung di antara dua titik, atau mungkin mengikuti beberapa sisi melalui beberapa titik.
Orde atau order suatu graph adalah jumlah simpul atau titik dalam graf tersebut (Orde=n[V(G)]).
Ukuran atau size suatu graph adalah jumlah sisi dalam graf tersebut (Size=n[E(G)]).
Definisi Subgraf
Misalkan G=(V,E) dan H=(W,F) graf. H dikatakan subgraph dari G jika W⊆V dan F⊆E.
Subgraf adalah Graf yang titik dan sisinya merupakan himpunan bagian dari graf lain. Subgraph bisa didapatkan dengan menghapus sisi atau titik pada suatu graf.
Sebuah subgraf dapat dibentuk dengan menghapus sisi atau sebuah sub himpunan dari E(G). Subgraf juga didapat dengan menghapus titik atau sub himpunan dari V(G) dengan menghapus juga sisi yang bersisian (incident) dengan titik yang dihapus.
Komplemen Graf
Komplemen atau invers dari graf G adalah graf H dimana graf H memiliki simpul-simpul yang sama dengan graf G sehingga dua simpul berbeda dari H bertetangga jika dan hanya jika keduanya tidak bertetangga di G.
Misalkan suatu graf lengkap memiliki titik anggota himpunan V sisi yang merupakan anggota himpunan E. Misalkan G adalah graf dengan titik himpunan V dan sisi yang anggota E1 dimana E1 adalah sub himpunan dari E. Misalkan juga graf H memiliki titik himpunan V dan sisi E2 merupakan subhimpunan E dimana E2=E-E1. Graf H disebut komplemen atau inverst graf G.
Komplemen subgraf dari graf G adalah graf yang diperoleh dari G dengan menghapus semua sisi yang ada pada subgraf.
0 komentar:
Post a Comment