Операции над графами

Объединением графов иназывается граф, множество вершин которого есть объединение множеств вершин графови, а множество ребер является объединением множеств ребер этих графов.

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

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

Рисунок 4.

На рис. 4 изображены графы ,.

Эйлеровы и гамильтоновы графы

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

Теорема 4. Граф G обладает эйлеровым циклом с концами итогда и только тогда, когда G – связный и,– единственные его вершины нечетной степени.

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

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

Рисунок 5. Рисунок 6.

На рис. 5 граф G не является эйлеровым (вершина инцидентна только одному ребру) и не является гамильтоновым, но обладает эйлеровым путемс концевыми вершинамии. Граф изображенный на рис. 6 является эйлеровым (последовательность реберобразует эйлеров цикл).

Матрицы графов

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

Определение. Матрица смежности простого графа ,

, где

Свойства матрицы смежности:

Симметричность.

Элементы главной диагонали .

Число единиц в строке (столбце) равно.

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

Определение. Матрица инциденций простого графа

Свойства матрицы инциденций:

В каждом столбце ровно 2 единицы.

Число единиц в строке равно степени вершины.

Пример: Матрица смежности для графа на рис. 7

Матрица инциденций для графа на рис. 7

Потоки в сетях

Сетью называется граф, элементам которого поставлены в соответствие некоторые параметры. Далее элементы множества R будем называть узлами, а множества –дугами. Пусть каждой дуге некоторой сетипоставлено в соответствие неотрицательное (действительное) число, называемоепропускной способностью дуги . Функция, отображающая множествов множество неотрицательных чисел, называетсяфункцией пропускной способности. Пусть s и t – два различных узла из R. Стационарный поток величины v из s в t в сети есть функцияf, отображающая множество А в множество неотрицательных чисел, удовлетворяющая линейным уравнениям и неравенствам

(14.4)

(14.5)

где («послеx»), («передх»).

Будем называть узел s – источником, узел t – стоком, а остальные узлы – промежуточными.

Если дан поток f, то число называетсядуговым потоком илипотоком по дуге . Посколькуиудовлетворяют условиям (14.4) и (14.5), вопрос о существовании потока не возникает. Система уравнений (14.4) избыточна, так как складывая все строки ее матрицы, мы получаем нулевой вектор. Таким образом, не нарушая общности, можно отбросить одно из уравнений системы.

Потоком в сети назовем функциюf, сопоставляющую каждому ребру сети целое числои обладающую следующими свойствами:

(косо симметрия), (допустимость).