Teori Graf dan Link Download File Referensi
https://eu2.contabostorage.com/00f3241116844f24b628f46d81abb929:st1/folder8/8093/1656359281_matematika_diskrit___Matematika.pdf
2026-05-31 20:00:19 - Admin
<style> body {font-family: Arial, sans-serif; line-height: 1.6; margin:0; padding:0; background:#f9f9f9; color:#333;} header {background:#4CAF50; color:#fff; padding:20px 10%; text-align:center;} nav {background:#e2e2e2; padding:10px 10%;} nav a {margin-right:15px; color:#333; text-decoration:none; font-weight:bold;} main {padding:20px 10%; max-width:900px; margin:auto;} h2 {color:#4CAF50; margin-top:30px;} h3 {color:#333; margin-top:20px;} ul, ol {margin-left:20px;} code {background:#eee; padding:2px 4px; border-radius:3px;} table {border-collapse:collapse; width:100%; margin:20px 0;} th, td {border:1px solid #ccc; padding:8px; text-align:center;} th {background:#f0f0f0;} figure {margin:20px 0; text-align:center;} figcaption {font-size:0.9em; color:#555;} a {color:#4CAF50;} </style><header> <h1>Pengantar Teori Graf</h1></header><nav> <a href="#definisi">Definisi</a> <a href="#jenis">Jenis Graf</a> <a href="#representasi">Representasi</a> <a href="#algoritma">Algoritma Penting</a> <a href="#aplikasi">Aplikasi</a></nav><main> <section id="definisi"> <h2>Definisi Graf</h2> <p>Graf adalah struktur matematika yang terdiri dari sekumpulan <em>simpul</em> (atau <em>vertex</em>) dan sekumpulan <em>sisi</em> (atau <em>edge</em>) yang menghubungkan pasangan simpul. Secara formal, sebuah graf tak berarah dapat dituliskan sebagai <code>G = (V, E)</code> dimana <code>V</code> adalah himpunan simpul dan <code>E</code> adalah himpunan sisi, masingmasing sisi merupakan pasangan tidak berurutan <code>{u, v}</code> dengan <code>u, v V</code>. Jika sisi memiliki arah, graf disebut <em>graf berarah</em> (<em>digraph</em>) dan setiap sisi ditulis sebagai ordered pair <code>(u, v)</code>.</p> </section> <section id="jenis"> <h2>Jenisjenis Graf</h2> <h3>Graf Tak Berarah vs Berarah</h3> <p>Graf tak berarah tidak memperhatikan urutan simpul pada sisi, sedangkan graf berarah memperlakukan <code>(u, v)</code> dan <code>(v, u)</code> sebagai sisi yang berbeda.</p> <h3>Graf Sederhana</h3> <p>Graf sederhana tidak mengizinkan <em>loop</em> (sisi yang menghubungkan simpul dengan dirinya sendiri) dan tidak ada <em>multiple edges</em> (lebih dari satu sisi antara dua simpul).</p> <h3>Graf Berat</h3> <p>Setiap sisi dapat memiliki nilai numerik yang disebut <em>berat</em>. Berat biasanya mewakili jarak, biaya, atau kapasitas.</p> <h3>Graf Bipartit</h3> <p>Simpul dapat dibagi menjadi dua himpunan <code>U</code> dan <code>V</code> sehingga setiap sisi menghubungkan satu simpul dari <code>U</code> ke satu simpul dari <code>V</code>. Contoh klasik adalah graf pencocokan (matching).</p> <h3>Graf Planar</h3> <p>Graf dapat digambar di bidang tanpa ada sisi yang saling bersilangan. Teorema Kuratowski memberikan karakterisasi graf planar.</p> <h3>Graf Pohon</h3> <p>Pohon adalah graf bersambung yang tidak mengandung siklus. Pohon memiliki <code>|V| - 1</code> sisi.</p> </section> <section id="representasi"> <h2>Representasi Graf</h2> <p>Ada dua cara utama untuk menyimpan graf dalam memori komputer.</p> <h3>Matrix Adjacent</h3> <p>Matrix <code>n n</code> dimana <code>n = |V|</code>. Elemen <code>A[i][j]</code> bernilai 1 (atau berat) bila terdapat sisi antara simpul <code>i</code> dan <code>j</code>, selain itu 0.</p> <figure> <img src="https://i.imgur.com/3Z0T0bN.png" alt="Contoh matrix adjacent" width="300"> <figcaption>Matrix Adjacent untuk graf tak berarah sederhana.</figcaption> </figure> <h3>List Adjacent</h3> <p>Setiap simpul menyimpan daftar semua tetangganya. Representasi ini lebih efisien untuk graf jarang (sparse).</p> <pre><code>A: B CB: A DC: A DD: B C </code></pre> <h3>Edge List</h3> <p>Daftar berisi semua sisi sebagai pasangan simpul. Sangat sederhana, cocok untuk input file.</p> </section> <section id="algoritma"> <h2>Algoritma Penting dalam Teori Graf</h2> <h3>Pencarian Jalur</h3> <ul> <li><strong>DFS (DepthFirst Search)</strong> menelusuri graf secara mendalam dulu, cocok untuk menemukan komponen terhubung, siklus, topological order.</li> <li><strong>BFS (BreadthFirst Search)</strong> menelusuri lapisan demi lapisan, memberikan jarak terpendek pada graf tak berberat.</li> </ul> <h3>Jarak Terpendek</h3> <ul> <li><strong>Dijkstra</strong> graf berberat nonnegatif, kompleksitas <code>O((V+E) log V)</code> dengan heap.</li> <li><strong>BellmanFord</strong> menangani sisi dengan berat negatif, mendeteksi siklus negatif.</li> <li><strong>FloydWarshall</strong> semuapasangsemua, <code>O(V)</code>, berguna untuk graf kecil.</li> </ul> <h3>Minimum Spanning Tree (MST)</h3> <ul> <li><strong>Prim</strong> memulai dari satu simpul, menambah sisi terdekat secara iteratif.</li> <li><strong>Kruskal</strong> mengurutkan semua sisi dan menambahkannya bila tidak membentuk siklus (unionfind).</li> </ul> <h3>Aliran Maksimum</h3> <p>Model jaringan transportasi atau komunikasi. Algoritma klasik:</p> <ul> <li>FordFulkerson (augmenting path)</li> <li>EdmondsKarp BFS untuk jalur augmentasi, <code>O(VE)</code></li> <li>Dinic level graph + blocking flow, <code>O(VE)</code> pada umumnya.</li> </ul> <h3>Pencocokan Bipartit</h3> <p>Algoritma HopcroftKarp menemukan pencocokan maksimum pada graf bipartit dengan kompleksitas <code>O(VE)</code>.</p> </section> <section id="aplikasi"> <h2>Aplikasi Teori Graf</h2> <h3>Jaringan Komputer</h3> <p>Routing, penentuan jalur terpendek, desain jaringan, dan deteksi loop pada protokol.</p> <h3>Transportasi</h3> <p>Perencanaan rute kendaraan, penjadwalan kereta, serta optimasi logistik (Vehicle Routing Problem).</p> <h3>Ilmu Sosial</h3> <p>Analisis jaringan sosial, pengaruh, komunitas, serta penyebaran informasi atau penyakit.</p> <h3>Bioinformatika</h3> <p>Representasi protein sebagai graf, pencarian motif, dan analisis jaringan metabolik.</p> <h3>Operasi Penelitian</h3> <p>Masalah penjadwalan, penugasan, dan perancangan sirkuit elektronik (PCB layout) sering dirumuskan sebagai masalah graf.</p> <h3>Game dan AI</h3> <p>Pencarian solusi dalam papan permainan (chess, go), serta perencanaan lintasan robot.</p> <h3>Komputer Vision</h3> <p>Segmentasi citra, deteksi tepi, dan pengenalan pola menggunakan graf piksel atau superpixel.</p> <h3>Kriptografi</h3> <p>Beberapa skema kunci publik berbasis masalah graf seperti Hamiltonian cycle.</p> <h3>Data Mining</h3> <p>Frequent subgraph mining, analisis struktur data besar, serta rekomendasi produk dengan graf bipartit penggunaitem.</p> </section> <section> <h2>Kesimpulan</h2> <p>Teori graf menyediakan bahasa universal untuk memodelkan hubungan antar objek. Dari konsep dasar seperti simpul dan sisi, hingga algoritma canggih untuk aliran jaringan, graf telah menjadi fondasi penting dalam ilmu komputer, matematika terapan, serta bidangbidang teknik. Menguasai representasi graf, mengenali jenisjenisnya, dan mempelajari algoritma klasik membuka peluang untuk memecahkan beragam masalah dunia nyata secara efisien.</p> </section></main>