Wikipedia

Teori graf: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
InternetArchiveBot (bicara | kontrib)
Bot
693.783 suntingan
Add 1 book for Wikipedia:Pemastian (20240209)) #IABot (v2.0.9.5) (GreenC bot
 
(19 revisi perantara oleh 14 pengguna tidak ditampilkan)
Baris 1:
{{Bukan|grafika}}
[[Berkas:6n-graf.svg|frame|right|Gambar yang menunjukkan suatu graf dengan 6 simpul dan 7 sisi.]]
[[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.
 
== Sedikit lebihDefinisi formal ==▼
'''Teori graf''' atau '''teori grafik''' dalam [[matematika]] dan [[ilmu komputer]] adalah cabang kajian yang mempelajari sifat-sifat [[graf|"graf" atau "grafik"]]. Ini tidak sama dengan "[[Grafika]]". Secara informal, suatu [[graf]] adalah himpunan benda-benda yang disebut [[:en:node (graph)|"simpul"]] (''vertex'' atau ''node'') yang terhubung oleh [[:en:edge (graph)|"sisi"]] (''edge'') atau [[:en:arc (graph)|"busur"]] (''arc''). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan "simpul") yang dihubungkan oleh garis-garis (melambangkan "sisi") atau garis berpanah (melambangkan "busur"). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan [[:en:loop (graph)|"gelang"]] (''loop'').
 
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''.
Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan pada [[Facebook]] bisa direpresentasikan dengan graf, yakni simpul-simpulnya adalah para pengguna Facebook dan ada sisi antar pengguna jika dan hanya jika mereka berteman. Perkembangan [[algoritma]] untuk menangani graf akan berdampak besar bagi [[ilmu komputer]].
 
Sebagai contoh, graf <math>G=(V,E) </math> dengan himpunan:
Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat sisinya berarah, yang secara teknis disebut [[graf berarah]] atau [[digraf]] (''directed graph''). Digraf dengan sisi berbobot disebut [[Jaringan (matematika)|jaringan]].
 
* <math>E V = \{{<1,2>,<1,5>,<2,5>,<3,2>,<4,3>,<5,4>,<4,6>}\} </math>▼
Jaringan banyak digunakan pada cabang praktis teori graf yaitu [[analisis jaringan]]. Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah).
* <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>.
▲== Sedikit lebih formal ==
 
== Sejarah ==▼
Suatu graf G, dinotasikan sebagai <math> G=(V,E)</math>, merupakan pasangan V dan E, di mana V merupakan himpunan tak kosong berisikan simpul pada graf tersebut dan E merupakan himpunan sisi pada graf tersebut. Secara formal, himpunan E dapat dinyatakan sebagai suatu koleksi subhimpunan berkardinalitas dua dari himpunan V, atau dalam notasi matematika <math> E\subseteq [V]^2</math>. Sebagai contoh, graf pada gambar di atas dapat dinyatakan sebagai graf <math>G=(V,E) </math> di mana <math> V = \{{1,2,3,4,5,6}\} </math> dan <math>E=\{{\{1,2\},\{1,5\},\{2,3\},\{3,4\},\{4,5\},\{5,2\},\{4,6\}}\} </math>.
[[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>
[[Berkas:Cesta (graf).svg|frame|right|Gambar dengan node yang sama dengan yang di atas, tapi merupakan digraf.]]
 
Pada [[digraf]] maka pasangan-pasangan ini merupakan pasangan terurut. Untuk menyatakan digraf (gambar kedua yang menggunakan tanda panah) kita dapat menggunakan himpunan ''edge'' sebagai berikut :
 
▲<math>E=\{{<1,2>,<1,5>,<2,5>,<3,2>,<4,3>,<5,4>,<4,6>}\} </math>
 
Dalam himpunan ''edge'' untuk digraf, urutan pasangan verteks menentukan arah dari ''edge'' tersebut.
 
Dalam teori graf, formalisasi ini untuk memudahkan ketika nanti harus membahas terminologi selanjutnya yang berhubungan dengan graph.
Beberapa terminologi berhubungan dengan teori graf :
* ''Degree'' atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.
* ''Path'' suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path <math> b \rightarrow c \rightarrow g </math>
* ''Cycle'' siklus ? path yang kembali melalui titik asal 2 <math> f \rightarrow c \rightarrow d \rightarrow e </math> kembali ke 2.
* ''Tree'' merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf di atas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV - 1. Dimana nV adalah jumlah vertex
* ''Graf Tak Berarah (Undirected Graph)'' Graf G disebut graf tak berarah (undirected graph) jika setiap sisinya tidak berarah. Dengan kata lain (v<sub>i</sub>,v<sub>j</sub>)=(v<sub>j</sub>,v<sub>i</sub>)
* ''Graf Berarah (Directed Graph)'' Graf G disebut graf berarah (directed graph) jika setiap sisinya berarah. Titik awal dari suatu sisi disebut verteks awal (initial vertex) sedangkan titik akhir dari suatu sisi disebut verteks akhir (terminal vertex). Loop pada graf adalah sisi yang verteks awal dan verteks akhirnya sama.
 
▲== Sejarah ==
 
== Lihat pula ==
{{refbegin|colwidth=20em}}
* [[Galeri graf bernama]]
* [[GlosariumMatamu teori grafmelemahkanku]]
* [[Daftar topik teori graf]]
 
=== Topik terkait ===
* [[Teori graf aljabaris]]
* [[Potongan graf]]
Baris 73 ⟶ 61:
* [[Pohon (struktur data)|Struktur data pohon]]
 
===Algoritma Algoritme ===
* [[AlgoritmaAlgoritme Bellman–Ford]]
* [[AlgoritmaAlgoritme Dijkstra]]
* [[AlgoritmaAlgoritme Ford–Fulkerson]]
* [[AlgoritmaAlgoritme Kruskal]]
* [[AlgoritmaAlgoritme tetangga terdekat]]
* [[AlgoritmaAlgoritme Prim]]
* [[Pencarian Depth-first]]
* [[Pencarian Breadth-first]]
 
=== Subarea ===
* [[Algebraic graph theory]]
* [[Geometric graph theory]]
Baris 90 ⟶ 78:
* [[Topological graph theory]]
 
=== Bidang matematika terkait ===
* [[Kombinatorika]]
* [[Teori grup]]
Baris 96 ⟶ 84:
* [[Teori Ramsey]]
 
=== Generalisasi ===
* [[Hipergraf]]
* [[Kompleks abstrak yang disederhanakan]]
Baris 136 ⟶ 124:
{{reflist|30em}}
 
== PustakaDaftar 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}}
*{{citation|authorlink=Claude Berge|last=Berge|first=Claude|title=Théorie des graphes et ses applications|series=Collection Universitaire de Mathématiques|volume=II|publisher=Dunod|location=Paris|year=1958}}. English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition, Dover, New York 2001.
* {{citationCite book|last1last=Biggs|first1first=N.Norman|last2=Lloyd|first2=E. Keith|last3=Wilson|first3=RRobin|date=1986|url=https://books.google.co.id/books?id=XqYTk0sXmpoC|title=Graph Theory, 1736–19361736-1936|publisherlocation=OxfordNew UniversityYork|publisher=Clarendon Press|yearisbn=19869780198539162|ref=harv|url-status=live}}.
*{{citation|last1=Bondy|first1=J.A.|last2=Murty|first2=U.S.R.|title=Graph Theory|publisher=Springer|year=2008|isbn=978-1-84628-969-9}}.
*{{citation|last1=Bondy|first1=Riordan, O.M|title=Mathematical results on scale-free random graphs in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed.|year=2003}}.
*{{citation|last=Chartrand|first=Gary|authorlink=Gary Theodore Chartrand|title=Introductory Graph Theory|publisher=Dover|isbn=0-486-24775-9|year=1985}}.
*{{citation|first=Alan|last=Gibbons|authorlink=|title=Algorithmic Graph Theory|year=1985|publisher=[[Cambridge University Press]]}}.
*{{citation|first=Shlomo Havlin|last=Reuven Cohen|title=Complex Networks: Structure, Robustness and Function|year=2010|publisher=Cambridge University Press}}
*{{citation|first=Martin|last=Golumbic|authorlink=Martin Charles Golumbic|title=Algorithmic Graph Theory and Perfect Graphs|year=1980|publisher=[[Academic Press]]}}.
*{{citation|authorlink=Frank Harary|last=Harary|first=Frank|title=Graph Theory|publisher=Addison-Wesley|location=Reading, MA|year=1969}}.
*{{citation|author1-link=Frank Harary|last1=Harary|first1=Frank|last2=Palmer|first2=Edgar M.|title=Graphical Enumeration|year=1973|publisher=Academic Press|location=New York, NY}}.
*{{citation|last1=Mahadev|first1=N.V.R.|last2=Peled|first2=Uri N.|title=Threshold Graphs and Related Topics|publisher=[[North-Holland Publishing Company|North-Holland]] |year=1995}}.
*{{citation|last1=Mark Newman|title=Networks: An Introduction|publisher=Oxford University Press|year=2010}}.
 
== 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}}
Diperoleh dari "https://wiki-indonesia.club/wiki/Teori_graf"