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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

 

Теория графов в информатике: примеры
Графы являются способом определения отношений в совокупности элементов. Они включают множество объектов, называемых вершинами или узлами, некоторые пары которых связаны т. н. ребрами.
далее
Алгоритм дейкстры и его реализация
В статье рассказывается о теории графов, задаче нахождения кратчайшего пути и ее решении с помощью алгоритма Дейкстры.
далее
Графическая информация и текстовая информация. Графическая ...
Графическая информация используется сегодня в множестве областей визуальной коммуникации, однако многим людям неизвестно это понятие и где оно может использоваться.
далее
Комбинаторная задача. Простейшие комбинаторные задачи. Комбинаторные ...
Преподаватели математики знакомят своих учеников с понятием «комбинаторная задача» еще в пятом классе, это необходимо для того, чтобы они сумели в дальнейшем работать с более сложными задачами. Под комбинаторностью задачи можно понимать возможность ...
далее
Семантическая сеть: определение, классификация и использование
Семантическая сеть представляет собой информационную модель какой-либо предметной области. Сеть строится по типу ориентированного графа, в котором вершины – это объекты заданной предметной области, а ребра или дуги - отношения между объектами.
далее
Какими бывают виды алгоритмов в информатике: примеры
При изучении информатики немало внимания уделяется изучению алгоритмов и их видам. Не зная основных сведений о них, нельзя написать программу или проанализировать ее работу. Изучение алгоритмов начинается еще в школьном курсе информатики. Сегодня мы рассмотрим понятие алгоритма, свойства алгоритма, виды.
далее
Какими бывают виды алгоритмов в информатике: примеры
Что это - графоман: определение
Графоманию можно представить как маниакальную страсть к писанию, доводящую до болезненного состояния, и помеху обществу. С другой стороны, графоман — это человек, предоставляющий для широкого круга лиц полезную информацию, который творчеством сам справляется со своими внутренними проблемами.
далее
Что это - графоман: определение
Теория и определение информатики
Информатика является относительно молодой наукой. Она возникла в середине прошлого столетия. Что послужило предпосылками к возникновению? Скорее всего, это резко увеличившиеся объемы информации, которые обрушились на человечество. Далее будет рассмотрено, что такое информатика, определение этой науки, ее цели.
далее
Теория и определение информатики
Алгоритм Краскала – построение оптимального каркаса
В начале 19 века геометр из Берлина Якоб Штейнер поставил задачу, как соединить три деревни так, чтобы их протяженность была самой короткой. Впоследствии он обобщил эту задачу: требуется найти на плоскости такую точку, чтобы расстояние от нее до n других точек было наименьшим.
далее
Алгоритм Краскала – построение оптимального каркаса