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

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

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

Если хотите больше математики, то сеть можно представить как пару множеств G=(V,E), где V – это подмножество любого множества натуральных чисел, то есть счетного, а E – подмножество VxV.

Теория графов используется в различных вычислениях при расчетах оптимальных маршрутов (кратчайших путей) и многого другого. Вы наверняка знакомы с Лео Эйлером, от которого данная теория и берет свое начало. Однако название этим множествам, которое есть сейчас, придумал не он, а математик Джеймс Джозеф Сильвестр спустя более сотни лет после записи Эйлера о том, как решить задачу о семи кёнингсберских мостах. Спойлер: никак. То есть «никак» и есть решение. Не заморачивайтесь.

Виды графов

Сети бывают двух видов: неориентированный и ориентированный. С первым вы познакомились в самом верху этой страницы – это и есть обычный.

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

Изображение графов на плоскости

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

Помните, что одно множество можно нарисовать по-разному, поэтому его изображение еще не есть сам граф.