ТЕОРИЯ ГРАФОВ Граф G - совокупность двух множеств: вершин V и ребер E, между которыми определено отношение инцидентности. Каждое ребро e из E инцидентно ровно двум вершинам v', v'', которые оно соединяет. При этом вершина v' и ребро e называются инцидентными друг другу, а вершины v' и v'' называются смежными. Часто пишут v', v'' из G и e из G. Если |V(G)|=n, |E(G)|=m, то граф G есть (n,m) граф, где n - порядок графа, m - размер графа. Ребро (v',v'') может быть ориентированным и иметь начало (v') и конец (v'') (дуга в орграфе). Ребро (v,v) называется петлей (концевые вершины совпадают). Граф, содержащий ориентированные ребра (дуги), называется орграфом. Граф, не содержащий ориентированные ребра (дуги), называется неографом. Ребра, инцидентные одной паре вершин, называются параллельными или кратными. Граф с кратными ребрами называется мультиграфом. Граф, содержащий петли (и кратные ребра), называется псевдографом. Конечный граф - число вершин и ребер конечно. Пустой граф - множество ребер пусто (число вершин может быть произвольным). Полный граф - граф без петель и кратных ребер, каждая пара вершин соединена ребром. Обозначение для полного графа с n вершинами - Kn. Граф называется двудольным, если существует такое разбиение множества его вершин на две части, что концы каждого ребра принадлежат разным частям (долям). Если любые две вершины двудольного графа, входящие в разные доли, смежны, то граф называется полным двудольным . Обозначение для полного двудольного графа с n и m вершинами - Kn,m. Локальная степень вершины - число ребер ей инцидентных. В неографе сумма степеней всех вершин равна удвоенному числу ребер (лемма о рукопожатиях). Петля дает вклад, равный 2 в степень вершины. Следствие 1 из леммы о рукопожатиях. Произвольный граф имеет четное число вершин нечетной степени. Следствие 2 из леммы о рукопожатиях. Число ребер в полном графе n(n-1)/2. В орграфе две локальных степени вершины v: deg(v)+ и deg(v) - (число ребер с началом и концом в v) Графы равны, если множества вершин и инцидентных им ребер совпадают. Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными. Граф называется регулярным (однородным), если степени всех его вершин равны. Способы задания графов Матрица инцидентности A. По вертикали указываются вершины, по горизонтали - ребра. aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро - петля, то aij=2. Список ребер. В первом столбце ребра, во втором вершины им инцидентные. Матрица смежности - квадратная симметричная матрица. По горизонтали и вертикали - все вершины. Dij= число ребер, соединяющее вершины i,j. Матрица Кирхгофа: bij=-1, если вершины i и j смежны, bij=0 если вершины i и j не смежны, bii=deg(i). Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0. Связность Отношение вершин графа "существует маршрут, связывающий вершины" является отношением эквивалентности, задающее разбиение графа на компоненты связности. Индекс разбиения - k. Маршруты, пути, цепи и циклы Маршрут - последовательность ребер, в которых каждые два соседних ребра имеют общую вершину. Маршрут, в котором начало и конец совпадают - циклический. Маршрут в неографе, в котором все ребра разные - цепь. Маршрут в орграфе, в котором все дуги разные - путь. Путь, в котором начало и конец совпадают - контур. Цепь с неповторяющимися вершинами - простая. Циклический маршрут называется циклом, если он цепь и простым циклом, если эта цепь простая. Вершины связанные, если существует маршрут из одной вершины в другую. Связанный граф - если все его вершины связаны. Число ребер маршрута - его длина. Эйлеров цикл - цикл графа, содержащий все его ребра. Эйлеров граф - граф, имеющий Эйлеров цикл. Теорема Эйлера. Конечный неориентированный граф эйлеров тогда и только тогда, когда он связан и степени его вершин четны. Теорема. Мультиграф обладает эйлеровой цепью тогда и только тогда, когда он связен и число вершин нечетной степени равно 0 или 2. Гамильтонов цикл - простой цикл, проходящий через все вершины. Планарность Плоский граф - граф с вершинами, расположенными на плоскости и непересекающимися ребрами. Планарный граф изоморфен плоскому. Всякий подграф планарного графа планарен. Задача о трех домах и трех колодцах. Провести от каждого из трех домов дорожки ко всем трем колодцам так, чтобы дорожки не пересекались. Граф этой задачи не является планарным. Грань графа - множество всех точек плоскости, каждая пара которых может быть соединена жордановой кривой. Граница грани -- множество вершин и ребер, принадлежащих грани. Всякий плоский граф имеет одну, и притом единственную, неограниченную грань. Эта грань является внешней гранью графа, остальные - внутренние. Теорема Эйлера. Для всякого связного плоского графа n-m+f=2, где n - число вершин,m - число ребер, f - число граней. Подразбиение ребра -- удаление ребра и добавление двух новых, инцидентных вершинам удаленного ребра и соединенных между собой новой вершиной. Два графа называются гомеоморфными , если оба они могут быть получены из одного и того же графа подразбиением его ребер. Теорема Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K5 и K3,3. Деревья и лес Дерево - связный граф без циклов. Лес (или ациклический граф) - неограф без циклов (может быть и несвязным). Теорема. Для неографа G с n вершинами без петель следующие условия эквивалентны: G - дерево; G - связный граф, содержащий n-1 ребро; G - ациклический граф, содержащий n-1 ребро; Любые две несовпадающие вершины графа G соединяет единственная цепь. G - ациклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл. Остов (каркас) связного графа - дерево, содержащее все вершины графа. Определяется неоднозначно. Редукция графа - остов с наибольшим числом ребер. Цикломатическое (или циклический ранг) число графа ν=m-n+c, где n - число вершин,m - число ребер, c - число компонент связности графа. Коциклический ранг (или коранг) ν*=n-c. Теорема. Число ребер неографа, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно цикломатическому числу графа. Неограф G является лесом тогда и только тогда, когда ν(G)=0. Неограф G имеет единственный цикл тогда и только тогда, когда ν(G)=1. Остов неографа имеет ν* ребер. Ребра графа, не входящие в остов, называются хордами. Цикл, получающийся при добавлении к остову графа его хорды, называется фундаментальным относительно этой хорды.

См. также Кирсанов М.Н. Графы в Maple - М.:ФИЗМАТЛИТ, 2007.