Teori graf: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
gambar + link ke bhs lain |
k →Lihat pula: menghapus jejak vandalisme |
||
| (102 revisi perantara oleh 57 pengguna tidak ditampilkan) | |||
Baris 1:
{{Bukan|grafika}}
[[Berkas:Königsberg Bridges graph.svg|jmpl|Sebuah graf yang dimodelkan dari [[Tujuh Jembatan Königsberg]].]]
'''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> dimana <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>.{{Sfn|Diestel|2016|p=2}} 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 ==
[[Berkas:Solutio problematis ad geometriam situs pertinentis, Fig. 1 - Cleaned Up.png|jmpl|Diagram oleh Euler yang menunjukkan fitur utama Tujuh Jembatan Königsberg.]]
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>{{Cite book|last=Croom|first=Fred H.|date=2016|url=https://archive.org/details/principlesoftopo0000croo_q6w1|title=Principles of Topology|publisher=Courier Dover Publications|isbn=978-0-486-80154-4|pages=[https://archive.org/details/principlesoftopo0000croo_q6w1/page/7 7]|language=en|url-status=live}}</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>{{Cite book|date=1857|url=https://rcin.org.pl/dlibra/docmetadata?showContent=true&id=173708|title=On the Theory of the Analytical Forms called Trees|location=Cambridge|publisher=Cambridge University Press|isbn=978-0-511-70369-0|editor-last=Cayley|editor-first=Arthur|series=Cambridge Library Collection - Mathematics|volume=3|pages=242–246|doi=10.1017/cbo9780511703690.046|url-status=live}}</ref>
== Lihat pula ==
{{refbegin|colwidth=20em}}
* [[
* [[Daftar topik teori graf]]
=== Topik terkait ===
* [[Teori graf aljabaris]]
* [[
* [[Graf konseptual]]
* [[Data structure]]
* [[Struktur data himpunan terurai]]
* [[Graf entitatif]]
* [[Graf ekstensial]]
* [[
* [[Graf automorfisme]]
* [[
* [[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]]
=== 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]]
* [[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}}
== Referensi ==
{{reflist|30em}}
== 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}}
[[Kategori:Teori graf| ]]
| |||