Teori graf: Perbedaan antara revisi

← Revisi sebelumnya Revisi selanjutnya →

Konten dihapus Konten ditambahkan

Sebaris

Revisi per 26 Februari 2023 14.30

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)$ dimana $V$ adalah himpunan simpul (vertex) dan $E$ adalah himpunan sisi (edge) yang berlaku $E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {dan}}\;x\neq y\}$ . Artinya, anggota himpunan $E$ adalah himpunan bagian berpasangan dua tak terurut dari $V$ .^[1] 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 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

Algoritme

Subarea

Bidang matematika terkait

Generalisasi

Teoris graf terkemuka

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

[FOOTNOTEDiestel20162-1] Diestel 2016, hlm. 2.

[FOOTNOTEWilson201331-32-2] Wilson 2013, hlm. 31-32.

[1]

[2]

@@ Baris 1: / Baris 1: @@
+{{Inuse}}{{Bukan|grafika}}
-[[Berkas:6n-graf.svg|bingkai|ka|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.
+== Definisi formal ==
-'''Teori graf''' dalam [[matematika]] dan [[ilmu komputer]] adalah cabang kajian yang mempelajari sifat-sifat [[graf|"graf"]]. Ini tidak sama dengan "[[Grafika]]". '''Graf'''  merupakan sekumpulan objek terstruktur di mana beberapa pasangan objek mempunyai hubungan ataupun keterkaitan tertentu.<ref>{{cite book|last=Mushthofa|first=|date=2021|url=http://eprints.uad.ac.id/19039/1/Kamus%20Kesehatan_11Nop18.pdf|title=Informatika untuk SMA Kelas X|place=[[Jakarta]]|publisher=Pusat Kurikulum dan Perbukuan|isbn=978-602-244-506-7|edition=|pages=246|language=|coauthors=}}</ref> 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 (''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 [[algoritme]] 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> V = \{{1,2,3,4,5,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 ==
-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:Cesta (graf).svg|bingkai|ka|Gambar dengan node yang sama dengan yang di atas, tetapi 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 ==
+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.{{Sfn|Wilson|2013|p=31-32}}
-Leonhard Euler, seorang matematikawan Swiss diperkirakan sebagai orang yang pertama kali (1736) menulis artikel ilmiah di bidang teori graf. Artikel dengan judul "''Seven Bridges of Königsberg"'' yang ditulisnya membahas permasalahan ada atau tidaknya struktur yang saat ini dikenal sebagai sirkuit Euler pada graf keterhubungan daratan kota ''Königsberg'' (sekarang Kaliningrad, Russia) dan pulau kecil di tengah sungai Pregel yang dihubungkan oleh tujuh buah jembatan.
-Disiplin ilmu teori graf belum meraih perhatian besar para matematikawan penting dalam sejarah sampai kurang lebih seratus tahun kemudian, masalah pewarnaan peta diperkenalkan oleh Francis Guthrie. Pada tahun 1852, Francis Guthrie menyadari bahwa ia hanya membutuhkan empat warna yang berbeda untuk mewarnai peta wilayah Britania Raya sehingga setiap dua daerah yang bersebelahan selalu memiliki dua warna yang berbeda. Kemudian, ia mengajukan sebuah pertanyaan pada seorang matematikawan Inggris, Augustus De Morgan, mungkinkah hal ini bukan sekadar kebetulan dan setiap peta selalu dapat diwarnai dengan empat warna saja? Pertanyaan ini membangkitkan keingintahuan para matematikawan dan sejak saat itu, teori graf menjadi bahan penelitian yang sangat menarik. Pertanyaan ini tetap menjadi misteri selama setidaknya seratus tahun kemudian dan menjadi topik yang sangat panas diperbincangkan matematikawan-matematikawan besar pada zaman itu.
-Pada awal abad keduapuluh, para saintis menemukan banyak manfaat dari teori graf di bidang-bidang lain seperti ilmu komputer, kimia teoretik, transportasi, dan lain-lain.
 == Lihat pula ==
@@ Baris 141: / Baris 121: @@
 {{reflist|30em}}
-== Pustaka ==
+== 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}}
-* {{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.
+* {{Cite book|last=Wilson|first=Robin|date=2013|title=Handbook of Graph Theory|publisher=Chapman & Hall|isbn=9781439880180|edition=2|chapter=History of Graph Theory|url-status=live}}
-* {{citation|last1=Biggs|first1=N.|last2=Lloyd|first2=E.|last3=Wilson|first3=R.|title=Graph Theory, 1736–1936|publisher=Oxford University Press|year=1986}}.
-* {{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 ==

l b s Matematika (Bidang matematika)
Fondasi	Filsafat matematika Logika matematika Teori himpunan Teori informasi Teori kategori Teori tipe
Aljabar	Abstrak Elementer Homologis Komutatif Linear Multilinear Universal Teori grup Teori representasi
Analisis	Kalkulus Analisis fungsional Analisis harmonik Analisis kompleks Analisis real Persamaan diferensial Teori ukuran Teori sistem dinamis
Diskret	Kombinatorika Teori graf Teori order
Geometri	Aljabar Analitis Diferensial Diskrit Euklides Hingga Trigonometri
Komputasi	Analisis numerik (Topik) Ilmu komputer Komputasi simbolik Teori komputasi Teori kompleksitas komputasi Optimisasi matematika
Teori bilangan	Aritmetika Geometri Diophantine Teori bilangan aljabar Teori bilangan analitis
Topologi	Teori homotopi Aljabar Diferensial Geometris Umum
Terapan	Matematika biologi Matematika ekonomi Matematika keuangan Fisika matematis Kimia matematika Psikologi matematis Statistika Statistika matematika Teori peluang Ilmu sistem (Teori kendali, Teori permainan, Riset operasi)
Divisi	Matematika murni Matematika terapan Matematika diskret Matematika komputasi
Topik terkait	Matematika dan seni Matematika rekreasi Pendidikan matematika Sejarah matematika
Kategori Portal matematika Kerangka Daftar