|
Научные направления - Теория графов
Теория графов – это раздел дискретной математики, изучающий свойства конечных (и бесконечных) множеств с заданными отношениями между их элементами. Обычно под графом понимается некоторое множество вершин, соединенных ребрами.
Родоначальником Теории графов считается Леонард Эйлер, который в 1736 году сформулировал и предложил решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач Теории графов.
Как прикладная дисциплина Теория графов позволяет описывать и исследовать различные системы данных. Графы находят свое применение во многих областях знаний:
- в социологии (для представления отношений внутри некоторого социума);
- в химии (для описания химических структур, путей сложных реакций);
- в биологии (для описания генных сетей);
- в информатике и программировании (для хранения и поиска данных);
- в транспортных и коммуникационных системах, в частности, в задачах маршрутизации (см. соответствующее направление);
- в схематехнике (для описания топологии печатных плат и микросхем);
- в логистике (для анализа инфраструктуры товаропотоков).
Традиционно в Теории графов рассматриваются следующие задачи:
- изоморфизм графов;
- исследование инвариантов графов;
- раскраска графа;
- планарность графа;
- экстремальные задачи на графах;
- алгоритмы на графах;
- перечисление графов;
- и др.
Многие комбинаторные и прикладные задачи решаются с помощью графов. Теория графов имеет тесные связи с топологией, теорией групп и теорией вероятностей, а также с теорией автоматов, исследованием операций, теорией кодирования, теорией игр.
Преподаватели:
|
