ДМ_Конспект

Матрица достижимости (Reachibility matrix)

квадратная (0,1)-матрица R(G) размером n n (n – число вершин в G), (i,j)-й элемент r которой равен 1, если в G существует путь из v в v (вершина v достижима из v), и равен 0 в противном случае.

Матрица инцидентности ((vertex-edge) incidence matrix)

(0,1)-матрица I(G) размером n m (n – число вершин, m – число ребер/дуг графа G), (i,j)-й элемент которой равен 1, если вершина v инцидентна ребру e в неориентированном графе или если v есть начало дуги e, равен -1, если вершина v есть конец дуги e (только для орграфов), и равен 0 в остальных случаях.

Матрица инцидентности определяет граф с точностью до изоморфизма.

Матрица Кирхгофа (Kirchhoff's matrix)

квадратная (0,1)-матрица B(G) размером n n (n – число вершин в G), (i,j)-й элемент b которой равен -1, если вершины v и v смежны (i j), равен степени deg v вершины v для i = j и равен 0 в остальных случаях. Сумма элементов в каждой строке и в каждом столбце этой матрицы равна нулю.

Матрица смежности (Adjacency matrix, vertex incidence matrix)

(0,1)-матрица A(G) размером n n (n – число вершин в G), (i,j)-й элемент a которой равен 1, если вершины v и v смежны, т.е. соединены дугой (или ребром) (v , v), и равен 0 в противном случае. Для неориентированного графа М.с. есть симметричная матрица с нулями на главной диагонали. В М.с. для мультиграфов и псевдографов (i,j)-й элемент равен числу ребер, соединяющих вершины v и v (при этом петля считается как два ребра).

М.с. определяет граф (орграф, мультиграф, псевдограф) с точностью до изоморфизма.

Матрица фундаментальных разрезов (Fundamental cut-set matrix)

матрица разрезов, ограниченная множеством фундаментальных разрезов.

Матрица фундаментальных циклов (Fundamental cycle matrix)

матрица циклов, ограниченная множеством фундаментальных циклов.

Матричная теорема о деревьях (Matrix-tree theorem)

теорема, доказанная Кирхгофом в 1847 г. и определяющая в неявном виде число каркасов в связном графе:

Число каркасов в связном графе G порядка n 2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа B(G). Следствием этой теоремы является Теорема Кэли

о числе помеченных n-вершинных деревьев (равным n).

Минимальный поток (Minimal flow)

поток наименьшей величины, удовлетворяющий нижним ограничениям на пропускную способность дуг.

Мост (Bridge)

ребро графа, удаление которого увеличивает число компонент связности графа; мост является вырожденным блоком графа.

Другое название – Перешеек.

Мультиграф (Multigraph)

281

пара (V,E), где V – непустое множество вершин, а E – семейство подмножеств множества V V (ребра); другими словами, мультиграф есть граф с кратными ребрами.

Надграф (Supergraph)

граф по отношению к любому его подграфу.

Наибольший поток(Maximum flow)

поток, величина которого наибольшая среди всех потоков по данной сети. По теореме Форда-Фалкерсона она равна пропускной способности минимального разреза.

Обхват (Girth)

наименьшая длина цикла в графе. Для графа без циклов обхват равен или , или 0, или неопределен, в зависимости от контекста.

Объединение графов (Graphs union)

операция, которая ставит в соответствие графам F и G граф H с множеством вершин V(H) = V(F) V(G) и множество ребер E(H) = E(F) E(G). В этой ситуации пишут H = F G. Объединение называется дизъюнктным, если V(F) V(G) = .

Другое название – наложение.

Однородный граф – то же, что и Регулярный граф.

Окружение графа (Circumference of a graph)

Длина самого длинного простого цикла в графе. Другое название – окружность графа.

Ориентированное дерево (Directed tree)

корневой орграф, у которого каждая вершина достижима из корня и основание его – дерево.

Ориентированный граф (Directed graph)

пара множеств (V,A), где V – конечное множеств вершин, A – множество дуг (ориентированных ребер), A V.

Ориентированный маршрут (Directed sequence)

такая последовательность S = (v , e , v , e , ... , e , v) его чередующихся вершин v и дуг e, что e = (v , v), 1 i n. Такой маршрут называется (v, v ) -маршрутом. Вершины v и v называются крайними, а остальные – промежуточными или внутренними.

Пересечение графов (Intersection of graphs)

граф G = GG, множество вершин которого есть пересечение множеств вершин, а множество ребер – пересечение множеств ребер исходных графов.

Перечисление графов (Graph enumeration)

подсчет числа неизоморфных графов в заданном классе (с заданными характеристиками).

Петля (Loop)

дуга или ребро вида (v,v), v V(G), элемент псевдографов. В приложениях, однако, допускается и в орграфах, рассматриваемых как модель системы.

Планарный граф (Planar graph)

282

граф, который может быть изображен на плоскости так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины. Другими словами, граф, изоморфный плоскому графу.

Плоский граф (Planar graph)

граф, изображенный на плоскости так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины.

См. также Планарный граф.

Подграф(Subgraph)

1.для графа G = (V,E) такой граф H = (W,U), у которого множество вершин W есть подмножество вершин графа G, W V, множество ребер/дуг U есть подмножество множества ребер/дуг E, U E, причем если (x,y) E и x,y W, то обязательно (x,y) U. Это определение подграфа мы будем называть сильным определением подграфа. Оно восходит к К.Бержу и распространено в большей части русскоязычной литературы.

2.То же, что и часть графа. Это определение будем называть слабым определением подграфа; оно распространено в части русскоязычной и практически во всей англоязычной литературе.

Подразбиение ребра (Subdivision of an edge)

операция, состоящая из удаления ребра e = (x,y) и добавления двух новых ребер e = (x,z) и e = (z,y), где z – новая вершина степени 2. См. Гомеоморфные графы.

Поиск в глубину (Depth first search)

метод ситематического прохождения (посещения) вершин графа, когда за счет продвижений от текущей вершины по ребру вперед (к еще непросмотренной вершине) всегда, когда это возможно, и возвратов от текущей вершины по пройденному ребру назад (к ранее пройденной вершине), если движение вперед от текущей вершины не возможно, осуществляется движение по всем вершинам графа, достижимым из заданной вершины s, с которой начинается поиск. Поиск в глубину всегда завершается через конечное число шагов в вершине s – начале просмотра; после его завершения все ребра связного графа оказываются разбитыми на два класса: древесные, по которым осуществлялись переходы из посещенных вершин в непосещенные, и ребра касания, замыкающие циклы. Частичный граф, порожденный древесными ребрами, называется деревом поиска в глубину; он является каркасом графа. Нумерация вершин графа в порядке их первого посещения в процессе поиска в глубину, называется M-нумерацией. Поиск в глубину в орграфе отличается тем, что при движении вперед дуги проходятся в соответствии с их ориентацией. При этом после завершения обхода дуги оказываются разбитыми на четыре класса: древесные, прямые, замыкающие какой-либо путь из древесных дуг, обратные, замыкающие контур, и поперечные, ведущие в ранее пройденные вершины и не замыкающие ни контур, ни путь из древесных дуг. Частичный орграф, порожденный древесными дугами, является либо корневым растущим ордеревом (дерево поиска в глубину), либо лесом, каждая компонента которого есть корневое растущее дерево. Поиск в глубину является основой многих

283

алгоритмов исследования структуры графа. Другие названия -Возвратный ход,

бектрекинг.

Поиск в ширину (Width (breadth) first search)

метод обхода и разметки вершин графа в следующем порядке: началу обхода s приписываем метку 0, смежным с ней вершинам – метку 1. Теперь рассматриваем поочередно окружения всех вершин с метками 1 и каждой из входящих в эти окружения еще не занумерованных вершин приписываем метку 2 и т.д. Если исходный граф связен, то поиск в ширину пометит все его вершины. Дуги вида (i,i+1) порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом. Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т.д.

Полный граф (Complete graph)

граф, у которого каждая пара вершин соединена ребром. Полный n-вершинный граф обозначается K.

Полный двудольный граф (Complete bipartite graph)

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

Полный k-дольный граф (Complete k-partite graph)

k-дольный граф, у которого любые две вершины, входящие в разные доли, смежны.

Полугамильтонов граф (Semihamiltonian graph)

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

Полустепень захода вершины (Indegree)

ворграфе – число дуг, заходящих в вершину.

Полустепень исхода вершины (Outdegree)

ворграфе число дуг, исходящих из вершины.

Полуэйлеров граф (Semieuler graph)

граф, в котором существует цепь, проходящая через каждое его ребро. Каждый эйлеров граф является полуэйлеровым.

Помеченный граф (Labeled graph)

граф, вершинам которого приписаны метки, например номера 1, 2, ... , n или символы из какого-нибудь алфавита.

Порожденный подграф (Induced subgraph)

подграф, порождаемый заданным множеством вершин, есть подграф в сильном смысле; подграф, порождаемый заданным множеством ребер, есть подграф в слабом смысле.

Порядок графа (Order of a graph)

число вершин в графе.

Поток (Flow)

целочисленная функция f(e), определенная на множестве E дуг транспортной сети и удовлетворяющая следующим условиям:

1)0 r(e) f(e) c(e), e E;

284

2).

3)

4) Здесь r(e) называется нижней пропускной способностью дуги e, а c(e) – верхней пропускной способностью. Число

где s – вход сети, а t – выход, называется величиной или мощностью потока. Поток, величина которого наибольшая среди всех потоков по данной сети, называется наибольшим или максимальным потоком. Аналогично определяется минимальный поток. Для наибольших потоков справедлива теорема ФордаФалкерсона:

Величина наибольшего потока равна пропускной способности минимального разреза.

Потомок вершины (Descendent of a vertex)

для вершины v любая вершина w, достижимая из v; w называется непосредственным потомком вершины v, если существует дуга (v,w). Непосредственный потомок в ордереве часто называют сыном вершины v.

Правильная раскраска (Proper (vertex) colouring)

раскраска, при которой всякие смежные вершины (смежные ребра) раскрашены в разные цвета.

Предок вершины (Predecessor of a vertex)

для вершины w всякая вершина v, из которой достижима w; v называется непосредственным предком (или предшественником), если существует дуга (v,w); непосредственный предок в ордереве часто называется отцом вершины w.

Простой контур (Simple cycle)

контур, в котором ни одна вершина не встречается дважды.

Простой путь (Simple path)

путь, в котором ни одна вершина не встречается дважды.

Простой разрез (Simple cutset)

разрез, у которого любое собственное подмножество элементов не является разрезом.

Простой цикл (Simple circuit)

цикл, в котором ни одна вершина не встречается дважды.

Пустой граф (Empty graph)

граф, не содержащий ребер. Другие названия – вполне несвязный граф,

регулярный степени 0 граф.

Путь (Path)

в орграфе такая последовательность вершин и дуг S = (v , e , v , ..., e , v), что e = (v , v) для i = 1, ..., n; и ни одна вершина в ней не встречается дважды; данный путь называется путем из v в v длины n с начальной вершиной v, конечной вершиной v и внутренними вершинами v , ..., v.

Радиус графа (Radius of a graph)

минимальный из эксцентриситетов вершин связного графа; вершина, на которой достигается этот минимум называется центральной вершиной.

285

Разрез (Cut-set)

множество ребер связного графа, удаление которых приводит к несвязному графу.

Разрезающая вершина (Cut-vertex (cutting vertex)) – вершина x графа G такая,

что после ее удаления множество V(G) \ {x} разбивается на непересекающиеся непустые подмножества V' и V'', между которыми нет ребер графа G.

См. также точка сочленения.

Раскраска (Colouring)

для некоторого графа G и натурального числа k функция вида f: V(G) {1,2,...,k}, отображающая множество вершин в множество цветов. Иногда, чтобы подчеркнуть мощность множества цветов, говорят о вершинной k- раскраске или просто о k-раскраске. Интерес представляют только те раскраски, при которых смежные вершины окрашиваются в различные цвета. Такие раскраски называются правильными. Поскольку функция f не обязательно сюръективна, то при k-раскраске фактически может быть использовано менее k цветов. Таким образом, правильную k-раскраску графа G можно рассматривать как разбиение множества вершин на не более чем k непустых классов, каждый из которых является независимым множеством.

Раскрашенный граф (Colored graph)

граф с заданным на множестве его вершин отношением эквивалентности таким, что любые смежные вершины не эквивалентны.

k-раскрашенный граф (k-colored graph)

раскрашенный граф с k классами эквивалентности. k-раскрашиваемая карта (k-colourable map)

карта, грани которой можно раскрасить k цветами так, чтобы никакие две смежные грани (т.е. грани с общими ребрами на границе) не были одного цвета. k-раскрашиваемый граф (k-colourable graph)

граф, для которого существует правильная k-раскраска.

Реберная k-раскраска (Edge k-colouring)

функция , ставящая в соответствие каждому ребру e графа число (e) из множества {1,2,...,k};

1)если – реберная раскраска и (e) = c, то говорят, что ребро e окрашено в цвет c;

2)реберная раскраска является правильной, если инцидентные одной вершине ребра получают разные цвета.

Реберно раскрашиваемый граф (Edge colourable graph)

граф, допускающий правильную раскраску ребер.

Реберно k-раскрашиваемый граф (Edge k-colourable graph)

граф, допускающий правильную реберную k-раскраску.

Реберно-хроматическое число (Line-chromatic number, edge chromatic number})

для данного графа G хроматическое число его реберного графа L(G).

Реберный граф (Line (edge) graph)

для заданного графа G граф L(G), вершинами которого служат ребра графа G и две вершины смежны в L(G) тогда и только тогда, когда соответствующие ребра смежны в G.

286

Регулярный граф (Regular graph)

граф, у которого степени всех вершин равны между собой; степень его вершин называется степенью регулярного графа. Все полные графы регулярны; регулярны также графы платоновых тел. Регулярным графом степени n является n-мерный куб.

Другое название – Однородный граф.

Самодополнительный граф (Self-complementary graph)

граф, изоморфный своему дополнению.

Самодополнительными графами являются, например, 4-вершинная простая цепь и 5-вершинный простой цикл.

Связанные вершины (Connected verticies)

вершины, между которыми существует простая цепь.

Связность (Connectivity)

наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.

Другое название – вершинная связность.

Связная компонента графа (Connected component of a graph)

всякий максимальный связный подграф графа; множество вершин связной компоненты называется областью связности графа.

Связный граф (Connected graph)

граф, (вершинная) связность которого больше нуля, т.е. граф, любая пара вершин которого связанная.

k-связный граф (k-connected graph)

граф, (вершинная) связность которого не меньше k.

Сеть (Net, network)

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

Сечение (Cutting set, cutset, separating set)

множество вершин, удаление которых из графа увеличивает число компонент связности.

Сильно связный орграф (Strongly connected graph)

орграф, у которого любая пара вершин сильно связана.

Симметричный орграф (Symmetric directed graph)

орграф, у которого две смежные вершины всегда соединены двумя противоположно ориентированными дугами.

Слабо связный граф (Weakly connected graph)

орграф, у которого любые две вершины соединены цепью (полупутем). Другое название – Слабый орграф.

Смежные вершины (Adjacent vertices, joined vertices)

вершины a и b, соединенные ребром (в графе), соединенные дугой (a,b) (в орграфе), принадлежащие одному ребру (в гиперграфе).

Смежные грани (Adjacent faces)

287

вплоском графе две грани, имеющие общее ребро.

Смежные дуги (Adjacent arcs)

дуги, имеющие общую вершину.

Смежные ребра (Adjacent edges)

ребра, имеющие общую вершину (в графе) или имеющие непустое пересечение (в гиперграфе).

Смежность (Adjacency)

бинарное отношение Ad на множестве вершин (ребер) графа такое, что a Ad b тогда и только тогда, когда a и b соединены дугой или ребром (имеют общую вершину).

Смешанный граф (Mixed graph)

граф, содержащий как дуги, так и ребра.

Соединение графов (Graphs union)

– для графов G и G с непересекающимися множествами вершин V и V и ребер граф

G + G = GGK(V ,V), где K(V ,V) – полный двудольный граф с множествами вершин V и V в долях.

Список ребер (Edge list)

способ задания графа (гиперграфа), состоящий в перечислении всех ребер графа (гиперграфа).

Список смежности (Adjacency list)

для заданной вершины v список вершин, смежных с v; любой граф может быть представлен с помощью n списков смежности, по одному для каждой вершины.

Степень вершины (Degree of a vertex, valency of a vertex)

вграфе – число инцидентных вершине ребер; в орграфе – число инцидентных дуг, т.е. сумма полустепеней захода и исхода.

Степень графа (Degree of a graph)

наибольшая из степеней вершин графа.

Другое название – Максимальная степень.

Стягивание графа (Contraction of a graph)

преобразование графа путем последовательного применения операции стягивания ребра.

Стягивание ребра (Contraction of an edge)

для данного ребра (u,v) слияние его концов u и v и удаление образовавшейся петли.

Суграф (Spanning subgraph)

часть графа, имеющая то же множество вершин, что и сам граф.

Сын (Son)

конец w дуги (v,w) в ордереве.

Теорема Брукса (R.L.Brooks, 1941)

Если G – связный граф, не являющийся полным, и степень графа (G) 3, то

(G).

Здесь (G) – хроматическое число графа G.

Теорема Визинга (В.Г.Визинг, 1964)

288

Каков бы ни был граф G, его хроматический индекс '(G) удовлетворяет неравенствам

(G) '(G) (G) + 1. Теорема Дирака (G.A.Dirac, 1952)

Если в графе с n (n 3) вершинами для любой вершины v выполняется неравенство deg (v) n/2, то G – гамильтонов граф.

Теорема Куратовского (K.Kuratowski, 1930)

Граф планарен тогда и только тогда, когда он не содержит частичных графов, гомеоморфных K или K.

Ряд авторов называют эту теорему теоремой Понтрягина-Куратовского.

Теорема Кэли (A.Cayley, 1897)

Существует ровно n различных помеченных деревьев с n вершинами.

Теорема Форда и Фалкерсона (L.R.Ford, D.R.Fulkerson, 1955)

Во всякой сети величина любого максимального потока равна пропускной способности минимального разреза.

Теорема Эйлера (L.Euler, 1736)

– Непустой связный граф эйлеров тогда и только тогда, когда граф не имеет вершин нечетной степени.

Точка сочленения графа (Articulation point, cut-vertex)

вершина v графа G, при удалении которой граф G \ v имеет больше компонент связности,

чем исходный граф G.

Другие названия – Разделяющая вершина, Шарнир.

Транзитивное замыкание орграфа (Transitive closure of a directed graph)

для данного орграфа G орграф G с тем же множеством вершин, что и G, в котором дуга (v,w) существует тогда и только тогда, когда w достижима из v в G.

Транзитивный орграф (Transitive directed graph)

орграф, у которого из существования дуг (u,v) и (v,w) вытекает существование дуги (u,w).

Транспортная сеть (Transportation network)

орграф, в котором выделены две вершины – вход и выход сети и для каждой дуги определена пропускная способность.

Треугольник (Triangle) – цикл длины 3. Тривиальный граф (Trivial graph)

граф, состоящий из одной вершины.

Турнир (Tournament)

орграф, превращающийся в полный неориентированный граф после удаления ориентации дуг. Этот класс графов получил свое название в связи со спортивными турнирами без ничьих, проводимых по круговой системе. Вершины турнира соответствуют участникам соревнований, а дуга (u,v) присутствует в орграфе, если участник u победил участника v.

Удаление вершины (Removal of a vertex)

289

преобразование графа G в граф G \ v, содержащий все вершины графа G, за исключением v, и все ребра графа G, не инцидентные v.

Удаление ребра (Removal of an edge)

преобразование графа G в граф G \ e, содержащий все вершины и все ребра графа G за исключением e.

Укладка графа (Embedding of a graph, evaluation of a graph)

1)для некоторого пространства L такое отображение графа в точки и жордановы кривые этого пространства, что различным вершинам соответствуют различные точки, а кривые, соответствующие различным ребрам, пересекаются только в инцидентных этим ребрам вершинах.

2)допустимая нумерация вершин графа, минимизирующая некоторый функционал.

Уровень вершины (Vertex level)

в ордереве (корневом дереве) расстояние от корня дерева до рассматриваемой вершины; корень дерева имеет уровень 0.

Формула Эйлера (Euler's formula)

формула, связывающая число вершин n, число ребер m и число граней f в выпуклом многограннике и плоском графе:

n + f – m = 2.

Фундаментальная система разрезов (Fundamental set of cutsets)

относительно данного каркаса T множество разрезов, определяемых удалением ребер каркаса; каждый такой разрез содержит ровно одно ребро каркаса T.

Фундаментальная система циклов (Fundamental set of circuits)

относительно данного каркаса T множество циклов, определяемых добавлением к каркасу ровно одной хорды каркаса T.

Фундаментальный цикл (Fundamental circuit)

1)относительно данного каркаса T в графе G цикл, однозначно определяемый добавлением к каркасу одной хорды e E(G) \ E(T);

2)относительно базы B матроида M = (S,) и элемента x S \ B цикл, однозначно определяемый добавлением к базе элемента x S \ B.

Хорда (Chord)

1. Ребро графа, не принадлежащее выделенному каркасу.

2. Простая цепь или ребро, связывающая две несоседние вершины простого цикла.

Хроматический индекс (Chromatic index)

минимальное число k, при котором граф является реберно k-раскрашиваемым.

Другое название – хроматический класс.

Хроматическое число (Chromatic number)

наименьшее число (G), при котором граф G правильно раскрашивается в (G) цветов.

Центр (Center)

множество центральных вершин графа; центр дерева состоит из одной или двух смежных центральных вершин.

Центральная вершина (Center vertex)

Вершина, эксцентриситет которой равен радиусу графа.

290