Теория графов – это один из подразделов математики, главным отличительным признаком которого является геометрический метод в изучении объектов. Основателем ее принято считать известного математика Л. Эйлера.
Применение теории графов до конца 19 века сводилось к решению занимательных задач и не привлекало значительного всеобщего внимания. Начиная с 20 века, когда теория графов сформировалась в самостоятельную математическую дисциплину, она нашла широкое применение в таких областях науки, как кибернетика, физика, логистика, программирование, биология, электроника, транспортные и коммуникационные системы.
Основные понятия теории графов
Базовым является граф. В терминологии можно встретить такое понятие, как сеть, идентичное графу. Последнее – это непустое количество точек, то есть вершин, и отрезков, то есть ребер, оба конца которых соответствуют заданному количеству точек. Теория графов не вкладывает определенного смысла в значения ребер и вершин. Например, города и соединяющие их дороги, где первые – это вершины графа, а вторые – ребра. Большее значение в теории уделяется дугам. Если у ребра есть направление, то оно имеет название дуги, если граф с ориентированными ребрами, он называется орграфом.
В терминологии теории так же выделяют следующие понятия:
Подграфом называется граф, все ребра и вершины которого находятся среди вершин и ребер.
Связный граф – тот, у которого для двух разных вершин существует соединяющая их цепь.
Взвешенный связный граф – тот, у которого задана весовая функция.
Дерево – связный граф, без циклов.
Остов – подграф, являющийся деревом.
При изображении графа на плоскости используется определенная система обозначений: выбранной вершине соответствует точка на простейшей поверхности, и если между вершинами находится ребро, то соответствующие точки объединяются отрезком. Если же граф ориентированный, эти отрезки заменяются стрелками.
Но не стоит сравнивать изображение графа с ним самим, т.е с абстрактной структурой, потому что одному графу можно придать не одно графическое представление. Рисунок на плоскости дан для того, чтобы увидеть, какие пары вершин объединяются ребрами, а какие нет.
Среди некоторых задач теории графов выделяют:
- Задача о кротчайшей цепи (замена оборудования, размещение мест скорой помощи и телефонных станций).
- Задача о максимальном потоке (упорядочение движения в динамической сети, распределение работ, организация пропускной способности).
- Задача о покрытиях и упаковках (размещение диспетчерских пунктов).
- Раскраска в графах (размещение памяти на электронно-вычислительных машинах).
- Связь сетей и графов (создание коммуникационной сети, анализ сетей связи).
В настоящее время невозможно программировать большинство задач без знания теории графов. Это облегчает и упрощает работу с ЭВМ.
Программирование использует множество структур и универсальных методов для решения задач, и одним из них является теория графов. Ее значение сложно переоценить. Теория графов в программировании позволяет упростить поиск информации, оптимизировать программы, преобразовать и распределить данные. Благодаря алгоритмам теории возникает возможность применения и их оценки в использовании для решения конкретных задач, осуществлять модификацию алгоритма, не уменьшая степени математической достоверности конечного варианта программы.
Важным свойством управляющей системы или модели является совокупность бинарных отношений при наборе действий и единиц данных. Эти структуры являются единственными частями программ и преобразующейся ими информации. Поэтому графы являются основой конструкцией для программиста.
