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

3.1 Абстрактный граф

Граф можно определить как совокупность двух множеств: G = (V, E), где

Само понятие графа подразумевает графическое представление данного объекта. Вершины изображаются

Примеры графов
а) неориентированный;
б) ориентированный

Вершины неориентированного графа, связываемые ребром, считаются концами этого ребра. Принято

Между вершинами и ребрами неориентированного графа так же, как

Граф может содержать петли, т. е. ребра, концы которых совпадают, или

В ориентированном графе с некоторой вершиной v подобным образом связаны

Можно говорить об окрестности N(v) и
степени d(v) вершины

Для ориентированного графа с
множеством дуг А имеем
В практических

Граф G = (V, E), у которого множество
ребер пусто, т. е. Е = ∅,

Граф называется двудольным, если
множество его вершин V разбито

3.2 Графическое представление бинарного отношения
Графическое представление отношения между элементами множеств А

3.3 Матричные представления графа

Поскольку граф можно рассматривать как графическое представление

Графы
имеют следующие матрицы смежности:

Ориентированный граф можно задать
также матрицей инцидентности,
которая

Матрицы инцидентности этиз графов
будут иметь следующий вид:

Заметим, что при матричном представ-
лении графа его вершины, а

3.4 Части графа

Граф Н = (W, F) называется подграфом графа G = (V, E),

Любая последовательность вида v1, e1, v2, e2, … , ek, vk+1, где v1, v2, … , vk+1
– вершины некоторого

Маршрут, все ребра которого различны, называется цепью. Цепь, все вершины

3.5 Достижимость и связность

Граф является связным, если между любыми двумя его

В ориентированном графе маршрутом называется последовательность вида v1, а1, v2, а2, … , аk, vk+1, где для

Вершина vj в ориентированном графе
является достижимой из вершины

Алгоритм Кристофидеса.

Множество R(xi) получается последова-тельным выполнением (слева направо) операций объединения

Пусть через Г-1(xi) обозначено множество вершин, из которых
можно достичь

Пример: Построить матрицы достижимостей и контрадостижимостей для графа G.

Матрица смежности C = (Cij)=

Матрица достижимостей R = (rij)

Матрица контрдостижимостей Q = (qij)

3.6 Доминирующие множества графа

Подмножество S множества вершин V графа G называется

Если S является доминирующим множест-
вом некоторого графа G, то

Задача о наименьшем доминирующем множестве сводится к известной задаче о

Наименьшими доминирующими множествами графа G
являются {v3, v7}, {v5, v7}

Его матрица смежности, дополненная единицами на главной диагонали, имеет
вид
Каждое

3.7 Независимые множества графа

Подмножество S множества вершин V графа G

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

3.8 Раскраска графа

Раскраской некоторого графа G = (V, Е) называется такое разбиение множества

Иногда ставится задача раскраски
ребер графа G = (V, Е), где

Иногда можно получить раскраску графа, минимальную или близкую к минималь-

Рассмотрим неограниченную последовательность деревьев Т1, Т2, … , Тi. Дерево Т1 состоит из

Деревья, раскрашиваемые «жадным» алгоритмом

Бихроматические графы

Граф G называется
k-хроматическим, если γ(G) = k. Очевидно,

Т е о р е м а К ё н и г а

Непустой граф является бихроматическим тогда и только тогда,

3.9 Планарность графов

Количество граней можно найти
для плоского связного