Lihat sumber Teori graf

[[File:Königsberg_Bridges_graph.svg|thumb|right|280px|Königsberg Bridges graph]]

'''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 <math> G</math> adalah [[pasangan terurut]] dari himpunan yang terpisah <math> (V,E)</math> di mana <math> V</math> adalah himpunan simpul (''node'' atau ''vertex'') dan <math> E</math> adalah himpunan sisi (''edge'') yang berlaku <math>E \subseteq \{ \{x, y\} \mid x, y \in V \;\textrm{ dan }\; x \neq y \}</math>. Artinya, anggota himpunan <math> E</math> adalah himpunan bagian berpasangan dua tak terurut dari <math> V</math>. Persisnya dalam teori graf, jenis graf ini disebut sebagai ''graf sederhana tak terarah''.

Sebagai contoh, graf <math>G=(V,E) </math> dengan himpunan:

* <math> V = \{{1,2,3,4,5,6}\} </math>
* <math>E=\{{\{1,2\},\{1,5\},\{2,3\},\{3,4\},\{4,5\},\{5,2\},\{4,6\}}\} </math>

Sebuah himpunan simpul <math> V</math> dari graf <math> G</math> dinotasikan sebagai <math> V(G)</math>, sementara himpunan sisi <math> E</math> sebagai <math> E(G)</math>.

== Sejarah ==
Teori graf bermula dari kajian matematikawan [[Leonhard Euler]] atas masalah [[Tujuh Jembatan Königsberg]]. Tujuh Jembatan Königsberg menyajikan masalah apakah bisa melintasi tujuh jembatan yang terdapat di [[Königsberg]] (kini [[Kaliningrad]], [[Rusia]]) sekali dalam berjalan terus-menerus. Pada 1736, Euler memaparkan penyelesaiannya dalam artikelnya yang berjudul ''Solutio problematis ad geometriam situs'' (Solusi dari masalah yang berkaitan dengan geometri posisi) yang menyimpulkan tidak ada solusi atas masalah tersebut.{{Sfn|Biggs|Lloyd|Wilson|1986|pp=2-10}} Artikel tersebut dianggap sebagai makalah pertama dalam sejarah teori graf dan penerapan praktis pertama dari [[topologi]].<ref>Fred H. Croom. [https://archive.org/details/principlesoftopo0000croo_q6w1 Principles of Topology]. Courier Dover Publications. 2016. hlm. [https://archive.org/details/principlesoftopo0000croo_q6w1/page/7 7]. ISBN 978-0-486-80154-4.</ref>

Lebih dari seabad setelah artikel Euler dan ketika [[Johann Benedict Listing]] memperkenalkan konsep [[topologi]], [[Arthur Cayley]] didorong pada minat pada bentuk analitik tertentu yang muncul dari [[kalkulus diferensial]] untuk mempelajari jenis khusus graf, [[Pohon (teori graf)|pohon]].<ref>[https://rcin.org.pl/dlibra/docmetadata?showContent=true&id=173708 On the Theory of the Analytical Forms called Trees]. Cambridge University Press. 1857. Vol. 3. hlm. 242–246. doi:10.1017/cbo9780511703690.046. ISBN 978-0-511-70369-0.</ref>

== Lihat pula ==
{{refbegin|colwidth=20em}}
* [[Galeri graf bernama]]
* [[Daftar topik teori graf]]

=== 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]]
* [[Graf (struktur data)|Struktur data graf]]
* [[Penggambaran graf]]
* [[Persamaan graf]]
* [[Graph rewriting]]
* [[Problem roti isi (graf)|Problem roti isi]]
* [[Sifat graf]]
* [[Graf bersimpangan]]
* [[Logika graf]]
* [[Simpul (teori 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]]
* [[Pohon (struktur data)|Struktur data pohon]]

=== Algoritma ===
* [[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]]
* [[Random graph|Probabilistic graph theory]]
* [[Topological graph theory]]

=== Bidang matematika terkait ===
* [[Kombinatorika]]
* [[Teori grup]]
* [[Teori Knot]]
* [[Teori Ramsey]]

=== Generalisasi ===
* [[Hipergraf]]
* [[Kompleks abstrak yang disederhanakan]]

=== 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 (matematikawan)|Neil Robertson]]
* [[Paul Seymour (matematikawan)|Paul Seymour]]
* [[Endre Szemerédi]]
* [[Robin Thomas (matematikawan)|Robin Thomas]]
* [[Carsten Thomassen]]
* [[Pál Turán]]
* [[W. T. Tutte]]
* [[Hassler Whitney]]
{{refend}}

== Daftar pustaka ==
* {{Cite book|last=Diestel|first=Reinhard|date=2016|url=https://diestel-graph-theory.com/index.html|title=Graph Theory|location=Heidelberg|publisher=Springer-Verlag|isbn=978-3-662-53621-6|edition=5|ref=harv|url-status=live}}
* {{Cite book|last=Biggs|first=Norman|last2=Lloyd|first2=E. Keith|last3=Wilson|first3=Robin|date=1986|url=https://books.google.co.id/books?id=XqYTk0sXmpoC|title=Graph Theory, 1736-1936|location=New York|publisher=Clarendon Press|isbn=9780198539162|ref=harv|url-status=live}}

== Pranala luar ==
* [http://scanftree.com/Graph-Theory/ Graph theory with examples]
* {{springer|title=Graph theory|id=p/g045010}}
* [http://www.utm.edu/departments/math/graph/ Graph theory tutorial] {{Webarchive|url=https://web.archive.org/web/20120116185332/http://www.utm.edu/departments/math/graph/ |date=2012-01-16 }}
* [http://www.gfredericks.com/main/sandbox/graphs A searchable database of small connected graphs]
* {{Wayback |date=20060206155001 |url=http://www.nd.edu/~networks/gallery.htm |title=Image gallery: graphs }}
* [http://www.babelgraph.org/links.html Concise, annotated list of graph theory resources for researchers] {{Webarchive|url=https://web.archive.org/web/20190713044422/http://www.babelgraph.org/links.html |date=2019-07-13 }}
* [http://www.kde.org/applications/education/rocs/ rocs] — a graph theory IDE
* [http://www.orgnet.com/SocialLifeOfRouters.pdf The Social Life of Routers] — non-technical paper discussing graphs of people and computers
* [http://graphtheorysoftware.com/ Graph Theory Software] {{Webarchive|url=https://web.archive.org/web/20130313205057/http://graphtheorysoftware.com/ |date=2013-03-13 }} — tools to teach and learn graph theory
* {{Library resources about |onlinebooks=yes |lcheading=Graph theory |label=graph theory}}

=== Buku teks online ===
* [http://arxiv.org/pdf/cond-mat/0602129 Phase Transitions in Combinatorial Optimization Problems, Section 3: Introduction to Graphs] (2006) by Hartmann and Weigt
* [http://www.cs.rhul.ac.uk/books/dbook/ Digraphs: Theory Algorithms and Applications] 2007 by Jorgen Bang-Jensen and Gregory Gutin
* [http://diestel-graph-theory.com/index.html Graph Theory, by Reinhard Diestel]

{{Bidang matematika}}

{{Authority control}}

== Referensi ==
<references />

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Teori+graf&oldid=28745848 Wikipedia bahasa Indonesia], revisi 28745848 (2025-12-27T05:43:31Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

<!-- WIKI_UNISSULA_PRESENTATION_V4 -->