Открыть главное меню
Граф с шестью вершинами и семью рёбрами

Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств , где есть подмножество любого счётного множества, а  — подмножество .

Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.

История возникновения теории графовПравить

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Термин «граф» впервые ввел Сильвестр, Джеймс Джозеф в 1878 году в своей статье в Nature[источник не указан 568 дней].

Терминология теории графовПравить

Терминология теории графов поныне не определена строго. В частности, в монографии Гудман, Хидетниеми, 1981 сказано: «В программистском мире нет единого мнения о том, какой из двух терминов „граф“ или „сеть“. Мы выбрали термин „сеть“, так как он, по-видимому, чаще встречается в прикладных областях». Аналогичная ситуация с терминами «вершина/точка».

Виды графов:

Изображение графов на плоскостиПравить

При изображении графов на рисунках чаще всего используется следующая система обозначений: вершины графа изображаются точками или, при конкретизации смысла вершины, прямоугольниками, овалами и др., где внутри фигуры раскрывается смысл вершины (графы блок-схем алгоритмов). Если между вершинами существует ребро, то соответствующие точки (фигуры) соединяются линией или дугой. В случае ориентированного графа дуги заменяют стрелками, они явно указывают направленность ребра. Иногда рядом с ребром размещают поясняющие надписи, раскрывающие смысл ребра, например, в графах переходов конечных автоматов. Различают планарные и не планарные графы. Планарный граф — это граф, который можно изобразить на рисунке (плоскости) без пересечения рёбер (простейшие — треугольник или пара связанных вершин), иначе граф не планарный. В том случае, если граф не содержит циклов (содержащих, по крайней мере, один путь однократного обхода рёбер и вершин с возвратом в исходную вершину), его принято называть «деревом». Важные виды деревьев в теории графов — бинарные деревья, где каждая вершина имеет одно входящее ребро и ровно два выходящих, или является конечной — не имеющей выходящих рёбер и содержит одну корневую вершину, в которую нет входящего ребра.

Не следует путать изображение графа собственно с графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет (другими словами, изоморфны ли соответствующие изображениям графы). В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.

Некоторые задачи теории графовПравить

К теории графов также относится целый ряд математических проблем, не решённых на сегодняшний день.

Применение теории графовПравить

См. такжеПравить

ПримечанияПравить

  1. Г. С. Яблонский, В. И. Быков, А. Н. Горбань, Кинетические модели каталитических реакций, Новосибирск: Наука (Сиб. отделение), 1983.- 255 c.
  2. Евстигнеев В.А. Применение теории графов в программировании. - М., Наука, 1985. - Тираж 20000 экз. - 352 c.
  3. Ерёменко А. О. Использование теории графов при решении задач в экономике // Прогрессивные технологии и экономика в машиностроении : сборник трудов VII Всероссийской научно-практической конференции для студентов и учащейся молодежи, г. Юрга, 7-9 апреля 2016 г. : в 2 т. — Томск : Изд-во ТПУ. — 2016. — Т. 2. — С. 279-281.
  4. Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.

ЛитератураПравить

СсылкиПравить