Москва. Столешников переулок.

ТЕОРИЯ ГРАФОВ

Граф 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 вершинами без петель следующие условия эквивалентны:
    1. G - дерево;
    2. G - связный граф, содержащий n-1 ребро;
    3. G - ациклический граф, содержащий n-1 ребро;
    4. Любые две несовпадающие вершины графа G соединяет единственная цепь.
    5. G - ациклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.
  • Остов (каркас) связного графа - дерево, содержащее все вершины графа. Определяется неоднозначно.
  • Редукция графа - остов с наибольшим числом ребер.
  • Цикломатическое (или циклический ранг) число графа ν=m-n+c, где n - число вершин,m - число ребер, c - число компонент связности графа.
  • Коциклический ранг (или коранг) ν*=n-c.
  • Теорема. Число ребер неографа, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно цикломатическому числу графа.
  • Неограф G является лесом тогда и только тогда, когда ν(G)=0.
  • Неограф G имеет единственный цикл тогда и только тогда, когда ν(G)=1.
  • Остов неографа имеет ν* ребер.
  • Ребра графа, не входящие в остов, называются хордами.
  • Цикл, получающийся при добавлении к остову графа его хорды, называется фундаментальным относительно этой хорды.
См. также Кирсанов М.Н. Графы в Maple - М.:ФИЗМАТЛИТ, 2007. Графы в Maple