Графы появились в математике в восемнадцатом столетии, когда Леонард Эйлер, пытался решить теперь уже классическую задачу о Кенигсбергских мостах. В то время в городе Кенигсберге было два острова, соединенных одним мостом друг с другом и шестью мостами с берегами протекающей через город реки так, как показано на рис. 1.
Рис. 1
Задача состоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуться в то же место, откуда начиналась прогулка. Решая эту задачу, Эйлер изобразил Кенигсберг в виде представленного на рис. 2 графа, отождествив его вершины с частями города, а ребра — с мостами, которыми связаны эти части.
Рис. 2
В общем случае любой граф G = (V, Е) состоит из множества V, чьи элементы называют вершинами графа, и множества Е его ребер, соединяющих некоторые пары вершин. На рис. 3 изображен граф G = (V, Е), состоящий из пяти вершин и восьми соединяющих их ребер .
Рис. 3
Вершины не обязательно должны соединяться ребрами. Вершины u и v графа называют смежными, если они соединены каким-то ребром е, про которое говорят, что оно инцидентно вершинам u и v, либо говорят, что вершины u и v инцидентны ребру е.
Степенью вершины v называют число S{v) ребер графа, инцидентных вершине v.
Граф называют связным, если любую пару его вершин соединяет какой-нибудь маршрут. Маршрутом в графе называют такую последовательность различных вершин, в которой каждая пара соседних вершин соединена ребром.
Граф, в котором существует маршрут, начинающийся и заканчивающийся в одной и той же вершине и проходящий по каждому ребру графа ровно один раз, называется, эйлеровым графом.
Цикл — это замкнутый маршрут, проходящий через каждую свою вершину и ребро только один раз.
Связный граф с двумя или более вершинами является эйлеровым графом тогда и только тогда, когда каждая его вершина имеет четную степень. Это и было доказано Эйлером. В задаче о Кенигсбергских мостах степени всех вершин графа нечетны S{v)=3, и поэтому искомого маршрута обхода города не существует.
Граф разбивают на подграфы, каждый из которых является связным. Минимальное число таких связных компонент называется числом связностиграфа и обозначается через c{G). Вопросы связности важны для приложений теории графов к компьютерным сетям.
Очевидно, что сумма степеней вершин произвольного графа G = (V, Е) равна удвоенному числу его ребер.
Простым принято называть граф G = (V, Е) с конечным множеством вершин V и конечным множеством ребер E, в котором нет петель и кратных ребер. Петли – эторебра, начинающиеся и заканчивающиеся в одной вершине. Кратными называются несколько ребер, соединяющих одну и ту же пару вершин. Петли и кратные ребра графа показаны на рис. 4.
Рис. 4
Цикл в графе представляется замкнутым маршрутом, у которого все вершины, кроме первой и последней, различны. Граф, не содержащий циклов, называют ацикличным. Связным является тот граф, в котором каждая пара вершин соединена маршрутом.
Гамильтоновым называют такой цикл в графе, который проходит через каждую вершину графа, причем только один раз. Граф, в котором существует гамильтонов цикл, называют гамильтоновым графом. Сравнить гамильтонов граф с эйлеровым графом.
Гамильтоновы графы применяются для моделирования многих практических задач. Основой всех таких задач служит классическая задача коммивояжера. Коммивояжер должен совершить поездку по городам и вернуться обратно, побывав в каждом городе ровно один раз, сведя при этом затраты на передвижения к минимуму, Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра — связывающие их дороги. Кроме того, каждое ребро оснащено весом, обозначающим транспортные затраты, необходимые для путешествия по соответствующей дороге, такие, как, например, расстояние между городами или время движения по дороге. Граф называется нагруженным, если каждое его ребро оснащено весом.
Представляется интересной следующая задача: доказать, что граф, изображенный на рис. 5 не является гамильтоновым.
Рис. 5
Особо выделяется класс графов, называемых деревьями, которые особенно интенсивно используются в вычислительных приложениях. Граф G = (F, Е) называется деревом,если он связен и ацикличен (т.е. не содержит циклов). Пусть G = (V, Е) — граф с п вершинами и т ребрами. Можно формулировать несколько необходимых и достаточных условий, при которых G является деревом:
• Любая пара вершин в G соединена единственным путем.
• G связен и т = п — 1.
• G связен, а удаление хотя бы одного его ребра нарушает связность графа.
• G ацикличен, но если добавить хотя бы одно ребро, то в G появится цикл.
Эквивалентность этих условий легко доказывается. Ориентированный граф (дерево) представлен на рис. 6.
Рис. 6
Остовным деревом графа G называют такой его подграф, который является деревом и содержит все вершины графа G. Алгоритм поиска минимального остовного дерева позволяет найти остовное дерево минимального общего веса в нагруженном графе и может быть использован для решения задачи поиска кратчайшего соединения.
Дерево с одной выделенной вершиной называют деревом с корнем, а выделенную вершину — его корнем. Вершины, стоявшие непосредственно
под вершиной V (и соединенные с ней ребрами), называются сыновьями вершины V. Вершины, расположенные в самом низу дерева (они не имеют сыновей), называются листьями. Вершины, отличные от корня и листьев, называют внутренними вершинами графа. Нулевое дерево — это дерево, не имеющее ни одной вершины.
Каждая вершина дерева с корнем Т является корнем какого-то другого дерева, называемого поддеревом Т. В двоичном дереве с корнем каждая вершина имеет не более двух сыновей, а два поддерева вершины V называют левым и правым поддеревьями, ассоциированными с V. Двоичное дерево с корнем называют полным, если каждая его вершина, за исключением листьев, имеет ровно по два сына.
Глубиной вершины V дерева с корнем Т принято считать длину единственного маршрута, соединяющего ее с корнем. Глубиной графа Т называют максимальную глубину его вершин.
Несложно доказать, что в любом связном графе найдется подграф, являющийся деревом. Подграф в G, являющийся деревом и включающий в себя все вершины G, называется остовным деревом.
Остовное дерево в графе G строится просто: выбираем произвольное его ребро и последовательно добавляем другие ребра, не создавая при этом циклов, до тех пор, пока нельзя будет добавить никакого ребра, не получив при этом цикла. Для построения остовного дерева в графе из п вершин необходимо выбрать ровно п — 1 ребро.
Логическая матрица отношения на множестве вершин простого графа G, которое задается его ребрами, называется матрицей смежности.
Пример простого графа с его матрицей смежности показан на рис. 7
Рис. 7
Пример ориентированного графа с его матрицей смежности показан на рис. 8
Рис. 8
Если в нагруженном графе вес каждого ребра равен 1, то элемент матрицы , полученной перемножением матриц , равен числу ориентированных маршрутов длины от вершины до вершины .
Это утверждение доказывается методом математической индукции.
В качестве примера рассмотрим матрицу , полученную простым перемножением трех матриц (см. рис. 8.)
Элемент этой матрицы указывает на существование двух ориентированных маршрутов длины три из вершины в вершину . Этими маршрутами являются и .
Граф может быть представлен матрицей инциденций. Для неориентированного графа элементы матрицы инциденций равны 1 или 0
Матрица инциденций неориентированного графа показана на рис. 9.
Рис. 9
Матрица инциденций ориентированного графа показана на рис. 10. Некоторые элементы этой матрицы отличаются от матрицы инциденций неориентированного графа на рис. 9 лишь знаком.
и восьми соединяющих их ребер 
.
матрицы 
, полученной перемножением 
матриц 
, равен числу ориентированных маршрутов длины 
до вершины 
.
, полученную простым перемножением трех матриц 
(см. рис. 8.)
этой матрицы указывает на существование двух ориентированных маршрутов длины три из вершины 
в вершину 
. Этими маршрутами являются 
и 
.
