grafų teorija

grãfų teòrija, matematikos šaka, tirianti grafų, kuriuos sudaro viršūnės su jas jungiančiais lankais, savybes ir jų taikymą. Grafų teorija taiko algebros, matricų teorijos, kombinatorikos, topologijos ir grupių teorijos metodus. Pirmajame grafų teorijos darbe L. Euleris (1736) išsprendė vadinamą Karaliaučiaus tiltų uždavinį, t. y. įrodė, kad neįmanoma, išėjus iš namų, pereiti per kiekvieną iš 7 tiltų tik po 1 kartą ir grįžti namo, surado būtinas ir pakankamas sąlygas apeiti visoms grafo briaunoms po 1 kartą. 1847 G. R. Kirchhoffas sukūrė specialią grafų, vadinamų medžiais, teoriją ir pritaikė ją elektros grandinių teorijai. 1857 A. Cayley šią teoriją patobulino, tirdamas organinės chemijos uždavinius. 1859 W. R. Hamiltonas sukūrė uždavinį, formaliai analogišką L. Eulerio uždaviniui: rasti bendrąjį požymį, iš kurio būtų aišku, ar grafas yra toks, kad jame galima išvesti liniją, pereinančią per visas jo viršūnes po 1 kartą. Žinomiausia (nuo 1840) grafų teorijos problema (išspręsta 1976 Jungtinėse Amerikos Valstijose) yra vadinama 4 spalvų problema: ar galima bet kurį žemėlapį nuspalvinti tik 4 spalvomis taip, kad jokios gretimos šalys nebūtų tos pačios spalvos. Kaip savarankiška šaka grafų teorija susiformavo išėjus Déneso Königo (Vengrija) knygai Baigtinių ir begalinių grafų teorija (Theorie der endlichen und Unendlichen Graphen, 1936). Taikant grafų teorijos sąvokas galima suformuluoti uždavinius, susietus su diskrečiaisiais objektais. Tokie uždaviniai atsiranda projektuojant integrinius grandynus, tiriant automatus, kompiuterinių programų blokines schemas, sprendžiant ekonomikos bei valdymo teorijos problemas, matematinės lingvistikos, bendrosios sistemų teorijos uždavinius ir kita.

grafas