Grafų teorija
Appearance
Grafų teorija – matematikos šaka, tirianti grafų, kuriuos sudaro viršūnės su jas jungiančiais lankais, savybes ir jų taikymą.[1] Grafas yra sudarytas iš lankais (briaunomis) sujungtų viršūnių.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b8/BekryptisGrafas.png/120px-BekryptisGrafas.png)
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[redaguoti | redaguoti vikitekstą]
L. Oilerio straipsnis apie septynis Karaliaučiaus tiltus laikomas pirmuoju grafų teorijos straipsniu.
Specialūs grafų atvejai[redaguoti | redaguoti vikitekstą]
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[redaguoti | redaguoti vikitekstą]
Populiariausi uždaviniai bei problemos, sprendžiamos grafų teorijos:
- Grafo nuspalvinimo uždavinys
- Kelio paieška:
- Grafų panašumo uždaviniai
Šaltiniai[redaguoti | redaguoti vikitekstą]
- ↑ grafų teorija. Visuotinė lietuvių enciklopedija (tikrinta 2024-02-04).
|