Teori graf
Teori graf adalah cabang matematika dan ilmu komputer yang mempelajari graf, yaitu struktur yang menggambarkan himpunan simpul (vertex) yang beberapa di antaranya dihubungkan dengan sisi-sisi (edge), beserta propertinya.
Definisi formal
Sebuah graf adalah pasangan terurut dari himpunan yang terpisah dimana adalah himpunan simpul (vertex) dan adalah himpunan sisi (edge) yang berlaku . Artinya, anggota himpunan adalah himpunan bagian berpasangan dua tak terurut dari .[1] Persisnya dalam teori graf, jenis graf ini disebut sebagai graf sederhana tak terarah.
Sebagai contoh, graf dengan himpunan:
Sebuah himpunan simpul dari graf dinotasikan sebagai , sementara himpunan sisi sebagai .
Sejarah
Teori graf bermula dari kajian matematikawan Leonhard Euler atas masalah Tujuh Jembatan Königsberg pada 1736. Tujuh Jembatan Königsberg menyajikan masalah apakah bisa melintasi tujuh jembatan yang terdapat di Königsberg (kini Kaliningrad, Rusia) sekali dalam berjalan terus-menerus.[2]
Lihat pula
Topik terkait
- Teori graf aljabaris
- Potongan graf
- Graf konseptual
- Data structure
- Struktur data himpunan terurai
- Graf entitatif
- Graf ekstensial
- Aljabar graf
- Graf automorfisme
- Pewarnaan graf
- Basis data graf
- Struktur data graf
- Penggambaran graf
- Persamaan graf
- Graph rewriting
- Problem roti isi
- Sifat graf
- Graf bersimpangan
- Logika graf
- Simpul
- Teori jaring-jaring
- Graf kosong
- Problem gerakan kerikil
- Perkolasi
- Graf sempurna
- Graf kuantum
- Graf sederhana acak
- Jaringan semantik
- Teori graf spektral
- Graf sederhana kuat
- Graf simetris
- Pengurangan transitif
- Struktur data pohon
Algoritme
- Algoritme Bellman–Ford
- Algoritme Dijkstra
- Algoritme Ford–Fulkerson
- Algoritme Kruskal
- Algoritme tetangga terdekat
- Algoritme Prim
- Pencarian Depth-first
- Pencarian Breadth-first
Subarea
- Algebraic graph theory
- Geometric graph theory
- Extremal graph theory
- Probabilistic graph theory
- Topological graph theory
Bidang matematika terkait
Generalisasi
Teoris graf terkemuka
- Noga Alon
- Claude Berge
- Béla Bollobás
- John Adrian Bondy
- Graham Brightwell
- Maria Chudnovsky
- Fan Chung
- Gabriel Andrew Dirac
- Paul Erdős
- Leonhard Euler
- Ralph Faudree
- Martin Charles Golumbic
- Ronald Graham
- Frank Harary
- Percy John Heawood
- Anton Kotzig
- Dénes Kőnig
- László Lovász
- U. S. R. Murty
- Jaroslav Nešetřil
- Alfréd Rényi
- Gerhard Ringel
- Neil Robertson
- Paul Seymour
- Endre Szemerédi
- Robin Thomas
- Carsten Thomassen
- Pál Turán
- W. T. Tutte
- Hassler Whitney
Referensi
- ^ Diestel 2016, hlm. 2.
- ^ Wilson 2013, hlm. 31-32.
Daftar pustaka
- Diestel, Reinhard (2016). Graph Theory (edisi ke-5). Heidelberg: Springer-Verlag. ISBN 978-3-662-53621-6.
- Wilson, Robin (2013). "History of Graph Theory". Handbook of Graph Theory (edisi ke-2). Chapman & Hall. ISBN 9781439880180.
Pranala luar
- Graph theory with examples
- Hazewinkel, Michiel, ed. (2001) [1994], "Graph theory", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
- Graph theory tutorial Diarsipkan 2012-01-16 di Wayback Machine.
- A searchable database of small connected graphs
- Image gallery: graphs di www.nd.edu Galat: URL arsip tidak dikenal (diarsipkan tanggal 20060206155001)
- Concise, annotated list of graph theory resources for researchers
- rocs — a graph theory IDE
- The Social Life of Routers — non-technical paper discussing graphs of people and computers
- Graph Theory Software Diarsipkan 2013-03-13 di Wayback Machine. — tools to teach and learn graph theory
- Bahan Buku daring, dan perpustakaan di perpustakaan Anda dan perpustakaan lain tentang graph theory
Buku teks online
- Phase Transitions in Combinatorial Optimization Problems, Section 3: Introduction to Graphs (2006) by Hartmann and Weigt
- Digraphs: Theory Algorithms and Applications 2007 by Jorgen Bang-Jensen and Gregory Gutin
- Graph Theory, by Reinhard Diestel