Teori graf

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.

Sebuah graf ${\displaystyle G}$ adalah pasangan terurut dari himpunan yang terpisah ${\displaystyle (V,E)}$ dimana ${\displaystyle V}$ adalah himpunan simpul (node atau vertex) dan ${\displaystyle E}$ adalah himpunan sisi (edge) yang berlaku ${\displaystyle E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {dan}}\;x\neq y\}}$. Artinya, anggota himpunan ${\displaystyle E}$ adalah himpunan bagian berpasangan dua tak terurut dari ${\displaystyle V}$.^[1] Persisnya dalam teori graf, jenis graf ini disebut sebagai graf sederhana tak terarah.

Sebagai contoh, graf ${\displaystyle G=(V,E)}$ dengan himpunan:

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

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

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

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

• Diestel, Reinhard (2016). Graph Theory (edisi ke-5). Heidelberg: Springer-Verlag. ISBN 978-3-662-53621-6.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
• Biggs, Norman; Lloyd, E. Keith; Wilson, Robin (1986). Graph Theory, 1736-1936. New York: Clarendon Press. ISBN 9780198539162.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)

• 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 Diarsipkan 2019-07-13 di Wayback Machine.
• 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

• 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