Grafų teorija

Grafų teorija – matematikos šaka, tirianti grafų, kuriuos sudaro viršūnės su jas jungiančiais lankais, savybes ir jų taikymą. Grafas yra sudarytas iš lankais (briaunomis) sujungtų viršūnių.

Jei grafo briaunos turi kryptį, tai orientuotas grafas. Jei grafas turi tik vieną viršūnę ir nei vienos briaunos, tai trivialus grafas. Grafas be briaunų – tuščias grafas, o be viršūnių ir be briaunų – nulinis grafas.

 Istorija 
L. Oilerio straipsnis apie septynis Karaliaučiaus tiltus laikomas pirmuoju grafų teorijos straipsniu.

 Specialūs grafų atvejai 
Yra kelios rūšys specifinių grafų, pasižyminčių savitomis savybėmis:
 Pilnasis grafas – grafas, kurio kiekviena viršūnė sujungta su kiekviena kita.
 Medis – grafas, tarp kurio bet kurių dviejų viršūnių egzistuoja lygiai vienas kelias.
 Plokščiasis grafas – grafą, kurį plokštumoje galima pavaizduoti taip, kad briaunos nesikirstų.

 Uždaviniai bei problemos 
Populiariausi uždaviniai bei problemos, sprendžiamos grafų teorijos:
 Grafo nuspalvinimo uždavinys
 Kelio paieška:
 Septyni Karaliaučiaus tiltai
 Keliaujančio pirklio uždavinys
 Mažiausias aprėpiantis medis
 Steinerio medis
 Trumpiausio kelio problema
 Grafų panašumo uždaviniai

 Šaltiniai