Podstawowe pojęcia teorii grafów
WPROWADZENIE
W okresie kilkunastu ostatnich lat nastąpił szybki wzrost zastosowań teorii grafów I sieci w różnych dziedzinach nauki I techniki. W zastosowaniach praktycznych stanowią one wygodny aparat formalny do modelowania systemowego rozważanych obiektów.
„Teoria grafów jest pewną metodą widzenia i opisywania rzeczywistości w kategoriach wyodrębnionych jej elementów I wzajemnych powiązań między elementami. Jest to, mówiąc inaczej, metoda świadomej symplifikacji rzeczywistości poddanej ścisłym regułom logiki.
Teoria grafów została sformułowana przez D. Königa w 1936 roku, a następnie rozwinięta przez Berge”a i innych; prace ich sięgają do klasycznych publikacji szwajcarskiego matematyka L. Eulera (1707-1738), a także znanego z prac o obwodach elektrycznych R. Kirchoffa (1824-1887). W ciągu ostatnich kilkunastu lat teoria grafów rozwinęła się w samodzielną dyscyplinę naukową, charakteryzującą się wielostronnością praktycznych zastosowań. Teoria ta i oparte na niej algorytmy oraz metody numeryczne znajdują obecnie zastosowanie do opisu układów mechanicznych, elektronicznych, elektrycznych, sieci transportowych, sieci operacji, schematów organizacyjnych jak również do opisów sformalizowanych i badania struktury związków chemicznych. Umoż liwia to między innymi sieciowe podporządkowanie sekwencji czasowych, przepływów strumieni i organizacji przedsięwzięć związanych z warunkami przepustowości przepływów strumieni w zależności od przekrojów „sieci” itp. uwarunkowań. W dziedzinie organizacji pracy przy użyciu grafów sieciowych można przedstawić dynamikę procesów produkcyjnych, przebieg materiałów i półfabrykatów itd. Należy podkreślić też, że język teorii grafów jest bardzo wygodny i obrazowy przy wykładaniu takich dyscyplin, jak: teoria gier, lingwistyka matematyczna, teoria algorytmów, teoria automatów, topologia i szereg innych dyscyplin.
Kulikowski J.: Zarys teorii grafów. Warszawa: PWN 1986.
Köning D.: Theorie der endlichen und unedlichen graphen. Lipsk 1936.