Граф — это математическое представление любых данных из жизнедеятельности человека, между которыми прослеживается связь. Граф состоит из вершин и ребер, где вершины — это любой тип закономерных данных, а ребра — это линии взаимосвязей между вершинами. Граф можно встретить в математике, информатике, в физике, химии, психологии, управлении и в других сферах науках. Но в основном граф связывают с информатикой и вычислительными технологиями.
Самый простой пример графа — это построение схемы перелетов самолетов какой-либо авиакомпании. В этом случае аэропорты на карте — это вершины графа, а ребра графа — это маршруты самолетов, курсирующих между аэропортами. Взгляните на расположение файлов в компьютере — это тоже граф, где диски, папки, файлы — это вершины графа, а зависимость и вложенность папок и файлов между собой — это будут ребра графа.
Графы бывают разные. Виды графов напрямую зависят от взаимосвязей между вершинами, то есть от строения, количества и расположения ребер графа.
Что такое граф или теория графов для чайников
Теория графов — это большой раздел в дискретной математике, в котором подробно изучают характеристики различных видов графов. Именно теория графов помогает адаптировать это математическое моделирование любой информации во многие сферы жизнедеятельности человека, включая бизнес, логистику и разные науки.
Для чего вообще нужны графы? Для того чтобы визуально отразить отношение и взаимодействие между какими-то элементами в общей системе, начиная от самолетов в международном авиасообщении и заканчивая молекулами в каком-либо веществе.
Какие бывают графы
В первую очередь все графы делятся на две большие группы:- ориентированные;
- неориентированные.
Ориентированный граф — это граф, у которого направление ребер имеет существенное значение и поэтому ребра задаются со стрелками на конце, например:
Иногда граф бывает смешанным, это когда часть ребер идет с обязательным направлением, а часть без направления. Такие графы редкие, но они есть, например:
Какими еще бывают графы
Математический граф может быть пустым — это когда он состоит только из одних вершин, даже без одного ребра. Например:Мультиграф — это такой вид графа, когда между вершинами графа происходит несколько видов связей, то есть между двумя конкретными вершинами может быть несколько разных ребер, например:
Полный граф — это такой граф, вершины которого соединены между собой всеми доступными вариантами. То есть каждая отдельная вершина соединена со всеми вершинами графа, например:
Эйлеров граф — это такой граф, у которого можно обойти все вершины, причем пройдя по каждому ребру только один раз. По своей конструкции он напоминает полный граф, о котором мы говорили чуть выше. Важная особенность — у Эйлерова графа может быть только четное количество ребер, с нечетным количеством ребер Эйлеров граф не получится. Еще такой вид графа можно определить так: любой граф, вершины которого вы сможете соединить всеми доступными ребрами, не отрывая карандаша от листочка бумаги, будет Эйлеровым графом.
Гамильтов граф — это такой граф, у которого можно обойти все вершины графа, посетив каждую из них только один раз.
Взвешенный граф — это такой граф, у которого вершинам и/или ребрам присваивается какое-то числовое значение, это значение означает «вес» или «стоимость» ребра или вершины.
Граф-дерево — это такой вид графа, у которого все вершины связаны без циклов, а строго в иерархическом порядке. У такого графа у любых двух вершин будет только одно ребро или путь соединения. Это самый распространенный вид графа, который используется человеком вне науки. В жизни такие графы можно выделить при организации управленческой структуры в школах, организациях, структурах и государствах. Суть такого графа заключается в том, что у него есть «корень графа», то есть это та вершина, с которой начинается весь граф. У людей это может быть: директор, старший менеджер, глава ведомства, мэр, президент и т. д. Граф-дерево может выглядеть вот так:
Как вы считаете, материал был полезен?