УВОД

Първата работа по теория на графите принадлежи на известния швейцарски математик Леонард Ойлер (L.Euler) и се е появила през 1736 г.

Възникването на теорията на графите като отделна математическа дисциплина е прието да се датира от 1936 г., когато е излязла монографията на Денеш Кьониг (D.König) - "Теория на крайните и безкрайните графи". Тази книга дава достатъчно обща и пълна за това време систематизация на фактите и съдържа ред нови резултати и идеи за по-нататъчно развитие.

Преди това графите са се срещали в различни области на науката и практиката, а така също и в многобройни главоблъсканици под различни названия и не са били обединени в обща теория.

Още от XIX в. е започнало използването на графи при построяването на схеми на електрически вериги, молекулни схеми, социограми в психологията, симплекси в топологията, диаграми на организация в икономиката, комуникационни мрежи, генеалогични дървета и т.н.

Постепенно е станало ясно, че някои задачи от алгебрата, теорията на числата, геометрията, теорията на множествата, топологията и даже класическия анализ допускат формулировка на езика на чистата теория на графите, при това в отделни случаи това помага за тяхното решаване или привеждане от една в друга.

Ролята на теорията на графите нараства рязко с бурното развитие на математическата логика, машинната математика, автоматиката, кибернетиката, теорията на информацията, математическата икономика, теорията на игрите, изследването на операциите, математическата лингвистика и други области, където на преден план излизат разсъжденията и построенията от дискретно-комбинаторен характер, за разлика от класическия анализ на непрекъснати величини. Единствения начин за справяне с огромното количество възникнали важни практически и теоретически задачи, свеждащи се към задачи от теорията на графите е да се учим да решаваме тези задачи на едро, използвайки от една страна най-новите постижения на теоретичната математика, а от друга - съвременната компютърна техника.

Теорията на графите не се вмества напълно в никой раздел на математиката - алгебра, комбинаторна топология или математическа логика. Тя лежи в основата на дискретната математика и има непосредствено отношение към топологията, комбинаториката, алгебрата и теорията на числата.