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.

Definisi formal 

Sebuah graf  adalah pasangan terurut dari himpunan yang terpisah  dimana  adalah himpunan simpul (node atau vertex) dan  adalah himpunan sisi (edge) yang berlaku . Artinya, anggota himpunan  adalah himpunan bagian berpasangan dua tak terurut dari . Persisnya dalam teori graf, jenis graf ini disebut sebagai graf sederhana tak terarah.

Sebagai contoh, graf  dengan himpunan:

 
 

Sebuah himpunan simpul  dari graf  dinotasikan sebagai , sementara himpunan sisi  sebagai .

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

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.

Lihat pula 

 Galeri graf bernama
 Matamu melemahkanku
 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
 Struktur data graf
 Penggambaran graf
 Persamaan graf
 Graph rewriting
 Problem roti isi
 Sifat graf
 Graf bersimpangan
 Logika 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
 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
 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
 Paul Seymour
 Endre Szemerédi
 Robin Thomas
 Carsten Thomassen
 Pál Turán
 W. T. Tutte
 Hassler Whitney

Referensi

Daftar pustaka

Pranala luar 
 Graph theory with examples
 
 Graph theory tutorial 
 A searchable database of small connected graphs
 
 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  — tools to teach and learn 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