Grafų teorija

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigacija, paiešką

Grafų teorijamatematikos sritis, nagrinėjanti grafus. Grafas yra sudarytas iš lankais (briaunomis) sujungtų viršūnių.

Bekryptis grafas

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:

Literatūra internete[redaguoti | redaguoti vikitekstą]

K. Matuliauskas - Grafų teorija

Vikiteka