grafów teoria
 
Encyklopedia PWN
grafów teoria,
mat. dział matematyki poświęcony badaniu własności grafów.
Jej początki (XVIII w.) były związane z rozwiązywaniem różnych łamigłówek; jednym z pierwszych wyników było — uzyskane przez L. Eulera (1736) w związku z tzw. zagadnieniem mostów królewieckich — kryterium istnienia cykli zawierających wszystkie krawędzie grafu; współczesna teoria grafów jest związana ściśle z topologią, algebrą liniową, teorią gier i in.; ma wiele zastosowań w różnych dziedzinach nauki i techniki — przy rozważaniu wszelkich zagadnień możliwych do zinterpretowania w postaci grafu, np. przy badaniu obwodów elektrycznych, relacji społecznych, procesów technologicznych, w informatyce m.in. przy obliczaniu złożoności obliczeniowej itd.
Ilustracje
Grafów teoria. Plan mostów królewieckich (ilustracja zamieszczona w artykule L. Eulera) i odpowiadający mu graf; zadanie postawione przez L. Eulera: czy można tak zaplanować spacer po Królewcu, by przejść po każdym z mostów na rzece dokładnie raz i powrócić do miejsca, z którego się wyszło?wyk. LogoScript/Archiwum Ilustracji WN PWN SA © Wydawnictwo Naukowe PWN
Przeglądaj encyklopedię
Przeglądaj tabele i zestawienia
Przeglądaj ilustracje i multimedia