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

З пляцоўкі Вікіпедыя
Перайсці да: рух, знайсці

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

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

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

Гісторыя[правіць | правіць зыходнік]

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

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

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

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

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

Літаратура[правіць | правіць зыходнік]