teori graf atau teori grafik dalam matematika dan ilmu komputer adalah cabang kajian yang mempelajari sifat-sifat "graf" atau "grafik".
ini tidak sama dengan "grafika".
secara informal, suatu graf adalah himpunan benda-benda yang disebut "simpul" (vertex atau node) yang terhubung oleh "sisi" (edge) atau "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 "gelang" (loop).
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.
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.
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).
sedikit lebih formal
suatu graf g, dinotasikan sebagai , 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 .
sebagai contoh, graf pada gambar di atas dapat dinyatakan sebagai graf di mana dan .
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 :
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
cycle siklus ?
path yang kembali melalui titik asal 2 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 (vi,vj)=(vj,vi)
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.
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 knigsberg" yang ditulisnya membahas permasalahan ada atau tidaknya struktur yang saat ini dikenal sebagai sirkuit euler pada graf keterhubungan daratan kota knigsberg (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.
teori graf aljabaris
struktur data himpunan terurai
basis data graf
struktur data graf
problem roti isi
problem gerakan kerikil
graf sederhana acak
teori graf spektral
graf sederhana kuat
struktur data pohon
algoritma tetangga terdekat
algebraic graph theory
geometric graph theory
extremal graph theory
probabilistic graph theory
topological graph theory
bidang matematika terkait
kompleks abstrak yang disederhanakan
teoris graf terkemuka
john adrian bondy
gabriel andrew dirac
martin charles golumbic
percy john heawood
u. s. r. murty
w. t. tutte
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