Teori graf: Perbedaan antara revisi

Revisi terkini sejak 23 Agustus 2026 10.24

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

Sebagai contoh, graf $G = (V, E)$ dengan himpunan:

$V = {1, 2, 3, 4, 5, 6}$
$E = {{1, 2}, {1, 5}, {2, 3}, {3, 4}, {4, 5}, {5, 2}, {4, 6}}$

Sebuah himpunan simpul $V$ dari graf $G$ dinotasikan sebagai $V (G)$ , sementara himpunan sisi $E$ sebagai $E (G)$ .

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.Templat:Sfn Artikel tersebut dianggap sebagai makalah pertama dalam sejarah teori graf dan penerapan praktis pertama dari topologi.^[1]

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.^[2]

Lihat pula

Templat:Refbegin

Topik terkait

Algoritma

Subarea

Bidang matematika terkait

Generalisasi

Teoris graf terkemuka

Templat:Refend

Daftar pustaka

Pranala luar

Graph theory with examples
Templat:Springer
Graph theory tutorial Templat:Webarchive
A searchable database of small connected graphs
Templat:Wayback
Concise, annotated list of graph theory resources for researchers Templat:Webarchive
rocs — a graph theory IDE
The Social Life of Routers — non-technical paper discussing graphs of people and computers
Graph Theory Software Templat:Webarchive — tools to teach and learn graph theory
Templat:Library resources about

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

Templat:Bidang matematika

Templat:Authority control

Referensi

↑ Fred H. Croom. Principles of Topology. Courier Dover Publications. 2016. hlm. 7. ISBN 978-0-486-80154-4.
↑ 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.

Sumber dan atribusi

Konten artikel ini diadaptasi dari 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.

[1] Fred H. Croom. Principles of Topology. Courier Dover Publications. 2016. hlm. 7. ISBN 978-0-486-80154-4.

[2] 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.

[1]

[2]

@@ Baris 1: / Baris 1: @@
+[[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 = \
+* <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). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.
+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 -->

Maintenance script (bicara | kontrib)