Теорема о включениях и исключениях

Пусть имеется множество из объектов произвольной природы. На этом множестве пусть задано свойств. Каждый объект может обладать либо не обладать некоторыми из этих свойств. Сами свойства обозначим: . Будем обозначать – количество объектов точно обладающих свойством и может быть какими-то другими, а – число объектов не обладающих ни свойством , ни свойством . Тогда число объектов, не обладающих ни одним из перечисленных свойств:

Теоретико-множественное произведение (произведение r множеств )

Множество всех выборок . Обозначается .

 

Основы теории графов

Алгоритм Дейкстры (E.Dijkstra)

алгоритм отыскания кратчайшего пути (цепи) во взвешенном орграфе (графе) без контуров (циклов) отрицательной длины с трудоемкостью (|V| ), предложенный Э.Дейкстрой в 1959 г.

Алгоритм Краскала (J.B.Kruskal)

1. Алгоритм построения каркаса графа путем последовательного удаления в соответствии с некоторой упорядоченностью ребер графа без нарушения связности получаемой части графа. 2. Алгоритм построения каркаса наименьшего веса описанным выше методом, но с предварительным упорядочением ребер в порядке неубывания весов. На основе А.К. созданы многочисленные модификации.

Алгоритм Прима (R.C.Prim)

алгоритм нахождения каркаса наименьшего веса графа путем наращивания поддерева (фрагмента каркаса) за счет присоединения граничного ребра (т.е. ребра, только один конец которого принадлежит фрагменту каркаса) с наименьшим весом. На основе А.П. созданы многочисленные модификации.

Алгоритм Робертса-Флореса (S.M.Roberts, B.Flores)

алгоритм построения гамильтонова цикла, использующий технику поиска с возвратом.

Алгоритм Флери (Fleury)

алгоритм построения эйлерова цикла.

Алгоритм Флойда (R.W.Floyd)

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

Антисимметрический граф (Anti-symmetric graph)

орграф, для которого выполнено следующее условие: если дуга (v ,v ) принадлежит орграфу, то в нем нет противоположно ориентированной дуги (v ,v ). Очевидно, что в А.г. нет петель.

Базис циклов (Cycle basis)

базис пространства циклов графа, состоящий только из простых циклов. Б.ц. является максимальным набором независимых простых циклов графа или минимальным набором простых циклов, от которых зависят все циклы. Мощность базиса циклов пространства циклов графа называется циклическим рангом графа. См. также Фундаментальные циклы.

Бесконечная грань плоского графа (Unbounded face)

единственная неограниченная грань плоского графа. Другое название – внешняя грань.

Биграф – то же, что и двудольный граф.

Бинарное дерево (Binary tree)

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

Другое название – двоичное дерево. Иногда под Б.д. просто понимается ордерево, из каждой вершины которого исходит не более двух дуг. См. m -арное дерево.

Бихроматический граф (Bichromatic graph)

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

Величина потока (Value of a flow)

сумма дуговых потоков на дугах, исходящих из входа сети. Равна сумме дуговых потоков на дугах, заходящих в выход сети.

Величина разреза (Value of a cut)

сумма пропускных способностей дуг разреза. Другое название – пропускная способность разреза.

Вершина (Vertex)

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

Вершина, достижимая из a (Reachible from a vertex)

вершина в орграфе, для которой существует путь из a в нее.

Вершина изолированная (Isolated vertex)

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

Вершина, инцидентная ребру (Vertex incident to an edge)

одна из концевых вершин ребра.

Вершина конечная – см. Конечная вершина.

Вершина концевая (Terminal vertex)

одна из вершин a и b, соединенных ребром e = (a,b); для орграфа вершина b дуги e = (a,b); иногда концевые вершины ребра определяются с помощью инцидентора.

Вершина центральная (Central vertex)

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

Вес дуги (Weight of an arc)

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

Взвешенный граф (Weighted graph)

граф (орграф), ребрам (дугам) которого приписаны веса. Иногда изображается в виде пары (G,w), где w – весовая функция, определенная на множестве ребер графа.

Висячая вершина (Terminal(pendant) vertex)

1. В неориентированном графе вершина степени 1.

2. В орграфе вершина с полустепенью захода, равной 1, и полустепенью исхода, равной 0.

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

Внутренняя вершина (Inner vertex)

вершина дерева, имеющая сыновей, т.е. не являющаяся листом.

Высота вершины (в ордереве) (Height of vertex)

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

Высота дерева (Height of tree)

высота корня дерева (ордерева).

Гамильтонов граф (Hamiltonian graph)

граф, содержащий гамильтонов цикл или гамильтонову цепь, соединяющую некоторую пару вершин. К настоящему времени известны лишь достаточные условия гамильтоновости графов, принадлежащие В.Хваталу, О.Оре, Г.Дираку, Х.Уитни и др. Примерами гамильтоновых графов служат полные графы, графы каркасов, графы правильных многогранников. Слово "гамильтонов" в этом и других терминах связано с именем ирландского математика У.Гамильтона, который в 1859 г. предложил головоломку "Кругосветное путешествие", где требовалось обойти по ребрам все вершины додекаэдра.

Гамильтонов контур (Hamiltonian cycle)

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

Гамильтонов орграф (Hamiltonian directed graph)

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

Гамильтонов путь (Hamiltonian path)

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

Геодезическая цепь (Geodetic chain)

кратчайшая простая (v,w) -цепь. См. Кратчайший путь.

Гипотеза четырех красок (Graph colouring conjecture)

Каждый планарный граф 4-раскрашиваем. Первоначальная формулировка гипотезы гласит: любая карта на плоскости или на сфере может быть раскрашена четырьмя красками так, что никакие две смежные страны не были одного и того же цвета. Гипотеза имеет интересную историю, но в ее появлении остается много непонятного. Имеются сообщения, что Мебиус был знаком с этой проблемой в 1840 г., но точно известно лишь то, что о данной проблеме Гутри сообщал де Моргану примерно в 1850 г. Сформулировал гипотезу британский математик А.Кэли в 1879 г. в статье, посвященной проблеме раскраски карт в первом томе Трудов Лондонского географического общества. Первое из многих ошибочных "доказательств" было дано Кемпе в 1879г. Новую фазу в истории гипотезы открыло машинное доказательство Хакена и Апеля, появившееся в 1976г. Это доказательство не было принято математической общественностью и породило новую проблему – проблему методологии и корректности доказательств математических теорем с помощью ЭВМ.

Глубина вершины (Depth of a vertex)

длина пути из корня дерева в данную вершину.

Гомеоморфные графы (Homeomorphical graphs)

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

Грань (Face, facet)

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

Граф (неориентированный граф) (Graph (undirected graph)

1. Пара (V,E), где V – непустое множество объектов некоторой природы, называемых вершинами графа, а E – подмножество двухэлементных подмножеств множества V, называемых ребрами графа. Множества вершин и ребер графа G обозначают V(G) и E(G), соответственно. Если |V(G)| = n и |E(G)| = m, то говорят о (n,m) -графе G. 2. Пара (V,E), где V – множество вершин графа, а E – множество ребер – есть подмножество множества V / классов эквивалентности, на которые множество V = {(v,w) | v w } разбивается отношением эквивалентности:

(v ,w ) (v ,w ) (v ,w ) = (v ,w ) или (v ,w ) = (w ,v )

3. Тройка (V,E,P), где V – множество вершин, E – множество объектов некоторой природы, отличной от природы вершин, называемых ребрами, P – инцидентор, сопоставляющий каждому ребру e E пару граничных вершин v и w из V. 4. Общее название как для неориентированного, так и для ориентированного графов.

Графы Куратовского (Graphs of Kuratowski)

графы K и K .

Двудольный граф (Bipartite graph)

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

Декартово произведение графов (Cartesian product of graphs)

граф = H H ... H , множество вершин которого есть декартово произведение множеств вершин графов H и в существует ребро (v,w), где v = (v ,..., v ) и w = (w ,..., w ), тогда и только тогда, когда существует семейство ребер E = (v , w ),..., E = (v , w ), E H .

Дерево (Tree)

связный граф без циклов.

Диаметр (Diameter)

наибольшее расстояние между вершинами графа.

Длина цепи (Length of a chain)

(в невзвешенном графе) число ребер в цепи; (во взвешенном графе) сумма длин ребер.

Добавление ребра (Edge adding)

операция над графами, состоящая в соединении ребром e двух несмежных вершин графа G, порождая граф G + e.

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

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

Дополнение графа (Complementary graph)

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

Достижимая вершина (Reachable vertex)

вершина w достижима из вершины v, если в орграфе существует путь из v в w.
Достижимое множество (Reaching set)

множество вершин, достижимое из заданной вершины.

Достижимость (Reachability)

бинарное отношение R на множестве вершин графа такое, что aRb тогда и только тогда, когда в графе существует путь из a в b.

Дуга (Arc)

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

Задание графа (Graph representation)

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

Задача китайского почтальона (Chinese postman's problem)

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

Задача коммивояжера (Traveling salesman problem)

Коммивояжер должен посетить каждый из n городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти кратчайший маршрут, зная расстояния между каждой парой городов. Математическая постановка этой задачи состоит в следующем: в полном взвешенном графе требуется найти гамильтонов цикл (или цепь) наименьшего веса (длины).

Данная задача является NP-полной; для ее решения не существует эффективного алгоритма. Важность этой задачи связана с тем, что к ней сводятся многие другие задачи; в связи с чем она играет роль эталонной задачи.

Задача о кенигсбергских мостах (Koenigsberg's bridges problem)

задача обхода всех семи мостов города Кенигсберга (ныне Калининграда) таким образом, что каждый мост проходится в точности один раз. Задача была поставлена и решена Эйлером в 1736 г. в виде общей проблемы теории графов: при каких условиях связный граф содержит цикл, проходящий через каждое его ребро?

Замкнутый маршрут (Cycle)

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

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

Звездный граф (Starred graph)

полный двудольный граф K ; в случае n = 3 используются названия "лапа" и "гроздь".

Изоморфизм графов (Graph isomorphism)

биекция : V(G) V(H) множества вершин графа G на множество вершин графа H, сохраняющая отношение смежности; другими словами, для любых вершин u и v графа G их образы (u) и (v) смежны в H тогда и только тогда, когда u и v смежны в G.

Отношение изоморфизма графов является эквивалентностью, т.е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса изоморфны, а графы из разных классов не изоморфны. Задача установления изоморфизма графов есть NP-полная проблема.

Изоморфные графы (Isomorphic graphs)

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

Инцидентность (Incidenty)

отношение между ребром (дугой) и его концевыми вершинами, т.е. ребро e = (a,b) инцидентно вершинам a и b и вершины a, b инцидентны ребру e = (a,b).

Источник (Source)

1. То же, что и вход орграфа.

2. Вершина орграфа, из которой можно достичь все остальные вершины.

3. В теории потоков на сетях вершина, из которой потока выходит больше, чем заходит.

Каркас (Spanning tree)

для данного неориентированного графа суграф в виде дерева. Другие названия – остов, остовное дерево, скелет, стягивающее дерево.

Клика (Clique)

подмножество V' графа G, в котором любые две вершины смежны, т.е. порожденный ими подграф G(V') является полным.

Кликовое число (Clique number)

число (G) вершин в наибольшей клике.

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

Код дерева (Code of a tree)

слово в некотором алфавите, сформированное согласно заданному порядку обхода вершин дерева и составленное по определенному правилу из количественных характеристик и признаков вершин, а также ограничителей. Различают коды с дублированием номеров вершин, коды, свободные от повторений, коды с использованием ограничителей, уровневые коды, ротационные коды бинарных деревьев, коды Закса, Ли, Прюфера, Гапта и др.

Кодерево (Cotree)

а) для заданного каркаса T – суграф в G, содержащий только те ребра графа G, которые не принадлежат T;

б) для данного графа G кодерево некоторого каркаса T.

Корень (Root)

некоторая выделенная вершина в графе (чаще в дереве).

Корневое дерево (Rooted tree)

дерево с выделенной вершиной – корнем.

Кратность ребра (Multiplicity of edge)

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

Кратные дуги (Multiple arcs)

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

Кратные ребра (Multiple edges)

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

Кратчайший остов графа (Shortest spanning tree)

каркас (остов) взвешенного графа с наименьшей суммой весов ребер.

Кратчайший путь (Shortest path)

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

Кубический граф (Cubic graph)

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

Левостороннее дерево (Left linear tree)

бинарное дерево, определяемое рекурсивно следующим образом:

а) одновершинное дерево есть Л.Д.;

б) бинарное дерево, у которого правое поддерево является пустым, а левое – Л.Д., есть также Л.Д.

Лемма о рукопожатиях (Handshake's lemma)

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

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

Лес (Forest)

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

Лист (Leaf)

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

Маршрут (Sequence)

чередующаяся последовательность

a = v , e , v , e ,..., v , e , v = b

вершин и ребер графа такая, что e = (v ,v ), 1 i n. Говорят, что маршрут соединяет вершины a и b – концы маршрута. Очевидно, что маршрут можно задать перечислением лишь его вершин a = v , v ,..., v = b или его ребер e , e ,..., e . М. конечен, если число входящих в него ребер конечно, и бесконечен в противном случае. Бесконечный М., имеющий только одну концевую вершину (a или b), называется односторонне-бесконечным маршрутом; М. без концевых вершин называется двусторонне-бесконечным маршрутом.

Матрица весов (Weight matrix)

вариант матрицы смежности для взвешенного графа, представляет собой квадратную матрицу размером n n (n – число вершин), (i,j) -й элемент которой равен весу ребра / дуги (v , v ), если таковое имеется в графе; в противном случае (i,j) -й элемент полагается равным нулю или бесконечности в зависимости от решаемой задачи.

Матрица достижимости (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)

пара (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 = G G , множество вершин которого есть пересечение множеств вершин, а множество ребер – пересечение множеств ребер исходных графов.

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

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

Петля (Loop)

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

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

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

Плоский граф (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-нумерацией. Поиск в глубину в орграфе отличается тем, что при движении вперед дуги проходятся в соответствии с их ориентацией. При этом после завершения обхода дуги оказываются разбитыми на четыре класса: древесные, прямые, замыкающие какой-либо путь из древесных дуг, обратные, замыкающие контур, и поперечные, ведущие в ранее пройденные вершины и не замыкающие ни контур, ни путь из древесных дуг. Частичный орграф, порожденный древесными дугами, является либо корневым растущим ордеревом (дерево поиска в глубину), либо лесом, каждая компонента которого есть корневое растущее дерево. Поиск в глубину является основой многих алгоритмов исследования структуры графа. Другие названия - Возвратный ход, бектрекинг.

Поиск в ширину (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;

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)

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

Разрез (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.

Регулярный граф (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)

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

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

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

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

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

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

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

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

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

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

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

G + G = G G K(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)<