Grafų teorija
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Grafų teorija – matematikos sritis, nagrinėjanti grafus. 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.
[taisyti] Istorija
L.Eulerio straipsnis apie septynis Karaliaučiaus tiltus laikomas pirmuoju grafų teorijos straipsniu.
[taisyti] Specialūs grafų atvejai
Yra kelios rūšys specifinių grafų, pasižyminčių savitom savybėm:
- Pilnasis grafas – kai kiekviena viršūnė sujungta su kiekviena kita.
- Medis – tarp bet kurių dviejų viršūnių egzistuoja lygiai vienas kelias.
- Plokščiasis grafas – kai grafą plokštumoje galima pavaizduoti taip, kad briaunos nesikirstų.
[taisyti] 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
