| Подготовьтесь к сдаче ЕГЭ интересно и эффективно
Граф: что это такое в математике, какие существуют его виды и другое
71

Граф: что это такое в математике, какие существуют его виды и другое

Содержание:





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

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

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

GeekBrains

Что такое граф или теория графов для чайников

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

Для чего вообще нужны графы? Для того чтобы визуально отразить отношение и взаимодействие между какими-то элементами в общей системе, начиная от самолетов в международном авиасообщении и  заканчивая молекулами в каком-либо веществе.



Какие бывают графы

В первую очередь все графы делятся на две большие группы:
  • ориентированные;
  • неориентированные.
Неориентированные графы — это такие графы, у которых направление ребер не имеет значения, например:

Неориентированные графы — это такие графы, у которых направление ребер не имеет значения

Ориентированный граф — это граф, у которого  направление ребер имеет существенное значение и поэтому ребра задаются со стрелками на конце, например:

Ориентированный граф — это граф, у которого  направление ребер имеет существенное значение и поэтому ребра задаются со стрелками на конце


Иногда граф бывает смешанным, это когда часть ребер идет с обязательным направлением, а часть без направления. Такие графы редкие, но они есть, например:

Иногда граф бывает смешанным, это когда часть ребер идет с обязательным направлением, а часть без направления



Какими еще бывают графы

Математический граф может быть пустым — это когда он состоит только из одних вершин, даже без одного ребра. Например:

Математический граф может быть пустым — это когда он состоит только из одних вершин, даже без одного ребра

Мультиграф — это такой вид графа, когда между вершинами графа происходит несколько видов связей, то есть между двумя конкретными вершинами может быть несколько разных ребер, например:

Мультиграф — это такой вид графа, когда между вершинами графа происходит несколько видов связей, то есть между двумя конкретными вершинами может быть несколько разных ребер

Полный граф — это такой граф, вершины которого соединены между собой всеми доступными вариантами. То есть каждая отдельная вершина соединена со всеми вершинами графа, например:

Полный граф — это такой граф, вершины которого соединены между собой всеми доступными вариантами. То есть каждая отдельная вершина соединена со всеми вершинами графа

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

Гамильтов граф — это такой граф, у которого можно обойти все вершины графа, посетив каждую из них только один раз.

Взвешенный граф — это такой граф, у которого вершинам и/или ребрам присваивается какое-то числовое значение, это значение означает «вес» или «стоимость» ребра или вершины.

Граф-дерево — это такой вид графа, у которого все вершины связаны без циклов, а строго в иерархическом порядке. У такого графа у любых двух вершин будет только одно ребро или путь соединения. Это самый распространенный вид графа, который используется человеком вне науки. В жизни такие графы можно выделить при организации управленческой структуры в школах, организациях, структурах и государствах. Суть такого графа заключается в том, что у него есть «корень графа», то есть это та вершина, с которой начинается весь граф. У людей это может быть: директор, старший менеджер, глава ведомства, мэр, президент и т. д. Граф-дерево может выглядеть вот так:

Граф-дерево — это такой вид графа, у которого все вершины связаны без циклов, а строго в иерархическом порядке.



Заключение

Граф — это способ структурировать информацию и взаимосвязи между различными частями информации. Графы важны не только  в математике, информатике и программировании, но и в других сферах человеческой деятельности. Сегодня мы лишь поверхностно пробежались по разновидностям графов. Если углубляться в теорию графов, то там можно найти еще множество подвидов  у каждого вида графов. Мы обязательно на них остановимся в следующих наших статьях.
Поделитесь в социальных сетях:
13 октября 2021, 14:58


Как вы считаете, материал был полезен?

Для оценки комментариев необходимо «войти на сайт».