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

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

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

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

Гісторыя

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

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

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

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

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

Літаратура

• Графаў тэорыя // Беларуская энцыклапедыя: У 18 т. Т. 5: Гальцы — Дагон / Рэдкал.: Г. П. Пашкоў і інш. — Мн. : БелЭн, 1997. — Т. 5. С. 411.
• Лекции по теории графов. М., 1990.
• Асновы ідэнтыфікацыі і сістэматызацыі графаў Архівавана 11 ліпеня 2019. (pdf)