Теория графов

Теория графов – это один из подразделов математики, главным отличительным признаком которого является геометрический метод в изучении объектов. Основателем ее принято считать известного математика Л. Эйлера.

Применение теории графов до конца 19 века сводилось к решению занимательных задач и не привлекало значительного всеобщего внимания. Начиная с 20 века, когда теория графов сформировалась в самостоятельную математическую дисциплину, она нашла широкое применение в таких областях науки, как кибернетика, физика, логистика, программирование, биология, электроника, транспортные и коммуникационные системы.

Основные понятия теории графов

Видео: Знакомство с теорией графов

Базовым является граф. В терминологии можно встретить такое понятие, как сеть, идентичное графу. Последнее – это непустое количество точек, то есть вершин, и отрезков, то есть ребер, оба конца которых соответствуют заданному количеству точек. Теория графов не вкладывает определенного смысла в значения ребер и вершин. Например, города и соединяющие их дороги, где первые – это вершины графа, а вторые – ребра. Большее значение в теории уделяется дугам. Если у ребра есть направление, то оно имеет название дуги, если граф с ориентированными ребрами, он называется орграфом.

В терминологии теории так же выделяют следующие понятия:

Видео: Информатика. Теория графов. Хранение графа: матрица смежности. Центр онлайн-обучения «Фоксфорд»

Подграфом называется граф, все ребра и вершины которого находятся среди вершин и ребер.

Связный граф – тот, у которого для двух разных вершин существует соединяющая их цепь.

Взвешенный связный граф – тот, у которого задана весовая функция.

Дерево – связный граф, без циклов.

Остов – подграф, являющийся деревом.

При изображении графа на плоскости используется определенная система обозначений: выбранной вершине соответствует точка на простейшей поверхности, и если между вершинами находится ребро, то соответствующие точки объединяются отрезком. Если же граф ориентированный, эти отрезки заменяются стрелками.

Но не стоит сравнивать изображение графа с ним самим, т.е с абстрактной структурой, потому что одному графу можно придать не одно графическое представление. Рисунок на плоскости дан для того, чтобы увидеть, какие пары вершин объединяются ребрами, а какие нет.

Среди некоторых задач теории графов выделяют:

1. Задача о кротчайшей цепи (замена оборудования, размещение мест скорой помощи и телефонных станций).
2. Задача о максимальном потоке (упорядочение движения в динамической сети, распределение работ, организация пропускной способности).
3. Задача о покрытиях и упаковках (размещение диспетчерских пунктов).
4. Раскраска в графах (размещение памяти на электронно-вычислительных машинах).
5. Связь сетей и графов (создание коммуникационной сети, анализ сетей связи).

В настоящее время невозможно программировать большинство задач без знания теории графов. Это облегчает и упрощает работу с ЭВМ.

Программирование использует множество структур и универсальных методов для решения задач, и одним из них является теория графов. Ее значение сложно переоценить. Теория графов в программировании позволяет упростить поиск информации, оптимизировать программы, преобразовать и распределить данные. Благодаря алгоритмам теории возникает возможность применения и их оценки в использовании для решения конкретных задач, осуществлять модификацию алгоритма, не уменьшая степени математической достоверности конечного варианта программы.

Важным свойством управляющей системы или модели является совокупность бинарных отношений при наборе действий и единиц данных. Эти структуры являются единственными частями программ и преобразующейся ими информации. Поэтому графы являются основой конструкцией для программиста.