Graph Theory dan Link Download File Referensi
https://eu2.contabostorage.com/00f3241116844f24b628f46d81abb929:st1/folder8/8050/1656356701_graph_teory___Matematika.pdf
2026-05-31 16:39:03 - Admin
<style> body{ font-family: Arial, Helvetica, sans-serif; line-height: 1.6; margin:0; padding:0 20px; background:#f8f9fa; color:#212529; } h1, h2, h3{ color:#2c3e50; } nav{ background:#e9ecef; padding:10px; margin-bottom:20px; } nav a{ margin-right:15px; text-decoration:none; color:#007bff; } nav a:hover{ text-decoration:underline; } .content{ max-width:800px; margin:auto; } ul{ margin-left:20px; } code{ background:#e2e3e5; padding:2px 4px; border-radius:4px; } </style> <nav> <a href="#definisi">Definisi</a> <a href="#jenis">Jenis Graf</a> <a href="#teorema">Teorema Penting</a> <a href="#aplikasi">Aplikasi</a> <a href="#referensi">Referensi</a> </nav> <div class="content"> <h1>Pengantar Teori Graf</h1> <section id="definisi"> <h2>Definisi Graf</h2> <p>Graf (atau dalam bahasa Inggris disebut <em>graph</em>) adalah struktur matematika yang terdiri atas sekumpulan <strong>simpul</strong> (vertex) dan sekumpulan <strong>sisi</strong> (edge) yang menghubungkan pasangan simpul. Secara formal, graf tak berarah dapat dituliskan sebagai pasangan terurut <code>G = (V, E)</code>, dimana <code>V</code> adalah himpunan simpul dan <code>E</code> adalah himpunan sisi, masingmasing berupa pasangan tak berurutan <code>{u, v}</code> dengan <code>u, v V</code>. Pada graf berarah (<em>directed graph</em> atau <em>digraph</code>), sisi dituliskan sebagai pasangan berurutan <code>(u, v)</code> yang menyiratkan arah dari <code>u</code> ke <code>v</code>.</p> </section> <section id="jenis"> <h2>Jenisjenis Graf</h2> <h3>Graf Sederhana</h3> <p>Graf yang tidak mengizinkan adanya sisi ganda (multiple edges) ataupun loop (sisi yang menghubungkan simpul dengan dirinya sendiri).</p> <h3>Graf Lengkap</h3> <p>Graf sederhana dimana setiap pasangan simpul terhubung oleh tepat satu sisi. Notasi umum untuk graf lengkap dengan <code>n</code> simpul adalah <code>K</code>. Pada <code>K</code> terdapat <code>n(n1)/2</code> sisi.</p> <h3>Graf Bipartit</h3> <p>Graf yang dapat dipartisi menjadi dua himpunan <code>U</code> dan <code>W</code> sehingga setiap sisi menghubungkan satu simpul dari <code>U</code> ke satu simpul dari <code>W</code>. Jika semua pasangan antara <code>U</code> dan <code>W</code> terhubung, graf tersebut disebut <em>graf lengkap bipartit</em> dan dinotasikan <code>K_{m,n}</code>.</p> <h3>Graf Berarah (Digraph)</h3> <p>Setiap sisi memiliki arah. Contoh pentingnya adalah graf alur kerja, jaringan komputer, atau graf ketergantungan pada ilmu komputer.</p> <h3>Graf Berbobot</h3> <p>Setiap sisi memiliki nilai numerik (berat) yang biasanya mewakili jarak, biaya, atau kapasitas. Berat ini memungkinkan pemecahan masalah optimasi seperti <em>shortest path</em> atau <em>minimum spanning tree</em>.</p> </section> <section id="teorema"> <h2>Teorema Penting dalam Teori Graf</h2> <ul> <li><strong>Teorema Euler tentang Graf Planar</strong> Sebuah graf terhubung planar memenuhi <code>V E + F = 2</code>, dimana <code>F</code> adalah jumlah muka (face) pada gambar planar.</li> <li><strong>Teorema Knig</strong> Pada graf bipartit, ukuran maksimum pencocokan (matching) sama dengan ukuran minimum penutup vertex (vertex cover).</li> <li><strong>Teorema Hall</strong> Menyediakan kondisi yang diperlukan dan cukup agar sebuah graf bipartit mempunyai pencocokan lengkap pada satu sisi.</li> <li><strong>Teorema Brook</strong> Sebuah graf tak lengkap dan bukan graf siklus ganjil dapat diwarnai dengan paling banyak <code></code> warna, dimana <code></code> adalah derajat maksimum.</li> <li><strong>Teorema Kuratowski</strong> Graf tidak planar bila dan hanya bila mengandung subdivisi dari <code>K</code> atau <code>K_{3,3}</code>.</li> </ul> </section> <section id="aplikasi"> <h2>Aplikasi Teori Graf</h2> <p>Teori graf tidak hanya bersifat teoritis; ia hadir dalam banyak bidang praktis:</p> <ul> <li><strong>Jaringan Komputer</strong> Representasi topologi jaringan, routing, dan deteksi siklus.</li> <li><strong>Transportasi</strong> Model jalan raya, penjadwalan penerbangan, dan optimasi rute logistik (misalnya algoritma Dijkstra atau A*).</li> <li><strong>Kimia</strong> Model molekul sebagai graf atom dan ikatan, membantu dalam perhitungan sifat kimia.</li> <li><strong>Ilmu Sosial</strong> Analisis jaringan sosial, penyebaran informasi, dan pengaruh.</li> <li><strong>Biologi</strong> Analisis jaringan metabolik, jalur regulasi gen, serta evolusi filogenetik.</li> <li><strong>Kriptografi</strong> Penyusunan graf eksponensial untuk masalah hardproblem seperti graf Hamiltonian.</li> <li><strong>Game & Puzzle</strong> Permainan labirin, Sudoku, dan tekateki lain yang dapat dimodelkan sebagai graf.</li> </ul> </section> <section id="referensi"> <h2>Referensi</h2> <p>Bagi yang ingin memperdalam materi, berikut beberapa sumber yang direkomendasikan:</p> <ol> <li>J. A. Bondy & U. S. R. Murty, <em>Graph Theory</em>, Springer, 2008.</li> <li>Douglas B. West, <em>Introduction to Graph Theory</em>, Prentice Hall, 2001.</li> <li>R. Diestel, <em>Graph Theory</em>, 5th ed., Springer, 2017.</li> <li>Wikipedia Bahasa Indonesia Teori Graf.</li> <li>Materi kuliah daring MIT OpenCourseWare: Mathematics for Computer Science.</li> </ol> </section> </div>