Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 6 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

8
Здесь нужно, чтоб душа была тверда,
Здесь страх не должен подавать совета,
Здесь никогда не может интуиция одна
Дать ключ к раскрытию научного секрета…
А. Данте
ВВЕДЕНИЕ
Появление термина «
граф» как общепринятого понятия в математике
связывают с появлением монографии Д. Кёнига
1
, где графы
рассматриваются в абстрактной форме как некоторые математические
объекты. Однако о появлении
теории графов стало возможным говорить
только с появлением достаточно общих методов, изложенных в
фундаментальной работе Пойа
2
. Одним из важных и общих методов в
теории графов является геометрическая теория
транспортных сетей,
созданная в 1956 – 1957 гг. Фордом, Фалкерсоном и Гейлом. Эта теория
позволяет решать не только транспортные, но и множество других задач из
области электрических сетей, химии, социологии и других предметных
областей.
Отличительной особенностью задач теории графов, как и любых
комбинаторных задач, является, как правило, невозможность применения
для их решения хорошо разработанного аппарата
классического анализа,
основанного на исчислении бесконечно малых величин. Это требует
неформального подхода при разработке методов решения подобных задач,
что часто ставит под угрозу обеспечение гарантий точности получаемых
решений.
Разработка достаточно эффективных методов построения
кратчайшего пути на графе; решение классической и обобщенной задач
коммивояжера при большом числе вершин графа ( 1000
≥n ); поиск
маршрута с максимальной пропускной способностью и оценка пропускной
способности сети; поиск специальных точек на графе составляют
содержание и цель работы.
Во разделе 2 (в разделе 1 содержится необходимый минимум
сведений из теории графов) приведен эффективный алгоритм построения
кратчайших маршрутов на графе (
эстафетный метод). Оценка сверху для
1
König D. Theorie der Еndlichen und Unendlichen Graphen. Leipzig, 1936.
2
Polya G. Kombinatorische Anzahlbestimmungen für Gruppen // Graphen und chemische
Verbindungen. Acta Math. 68 (1937). Р. 145.

Страницы