Тэорыя графаў

Тэо́рыя гра́фаў — раздзел матэматыкі, які вывучае аб'екты на аснове геаметрычнага падыходу.

Асноўнае паняцце тэорыі графаў — граф: мноства пунктаў (вяршынь) і мноства сувязей (рэбраў, дуг), якія злучаюць некаторыя (або ўсе) пары вяршынь.
Напрыклад, сетка чыгунак, аўтамабільных (ці іншых) дарог з пазначэннем на дугах адлегласцей паміж населенымі пунктамі або іх прапускных здольнасцей.

Тэорыя графаў выкарыстоўваецца ў тэорыі перадачы інфармацыі, тэорыі транспартных сетак, камп'ютарнай графіцы, аўтаматызацыі праектавання і інш.

 Гісторыя 
Першыя задачы тэорыі графаў былі звязаны з рашэннем галаваломак і матэматычных забаўляльных задач (напрыклад, , , аб перавозках, кругасветным падарожжы,  і іншыя).

Адным з першых вынікаў у тэорыі графаў быў крытэрый існавання абходу графа без паўтораў рэбраў (Л. Эйлер, 1736).

У 19 ст. з'явіліся работы, у якіх пры рашэнні практычных задач былі атрыманы важныя вынікі ў тэорыі графаў (задачы пабудавання электрычных ланцугоў, падліку хімічных рэчываў з рознымі тыпамі малекулярных злучэнняў і іншыя).

У 20 ст. задачы, звязаныя з графамі, з'явіліся ў тапалогіі, алгебры, тэорыі лікаў, тэорыі імавернасці і іншых.
Найбольшае развіццё тэорыя графаў атрымала з 1950-х гадоў у сувязі са станаўленнем кібернетыкі і развіццём вылічальнай тэхнікі.

На Беларусі даследаванні па тэорыі графаў вядуцца ў БДУ (уплыў розных параметраў на уласцівасці графаў), Інстытуце матэматыкі (розныя прадстаўленні графаў, алгарытмічныя аспекты тэорыі графаў), Інстытуце тэхнічнай кібернетыкі (графы ў задачах аптымальнага ўпарадкавання) НАН Беларусі.

 Літаратура 
 Графаў тэорыя //  С. 411.
 Лекции по теории графов. М., 1990.
 Асновы ідэнтыфікацыі і сістэматызацыі графаў  (pdf)


Катэгорыя:Дыскрэтная матэматыка