Введение в теорию графов

Задача о Кёнигсберских мостах:

Может ли пешеход обойти все мосты, пройдя

Задача четырёх красок:

Можно ли любую карту так раскрасить четырьмя красками, чтобы

Задача о домиках и колодцах:

Имеются три домика и три колодца. Можно

Понятие неориентированного графа

Граф – это система некоторых объектов вместе с некоторыми парами этих

Неориентированный граф – это система
состоящая из множества V с элементами

Если ребро , то говорят, что ребро e соединяет вершины u

Ребро e называют инцидентным вершине v, если она является одним из

Вершина, не инцидентная ни одному ребру, называется изолированной.

Вершина, инцидентная ровно одному ребру, называется концевой, а данное ребро концевым

Ребро с совпадающими концами называется петлёй

Две вершины, инцидентные одному и тому же ребру, называются смежными (соседними).

Ребра, которым поставлена в соответствие одна и та же пара вершин,

Понятие ориентированного графа

Ориентированный граф –
это система , состоящая из множества V с

Если - упорядоченная пара, т.е. , , то ребро e называют

Дугу (u,v) называют заходящей в вершину v и исходящей из вершины

Дугу называют инцидентной вершине v, если она заходит в v или

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

Дугу, начало и конец которой есть одна и та же вершина,

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

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

Способы задания графа (неориентированного)

1. Перечислением (или списком) рёбер с указанием их концов и добавлением

2. В виде геометрического объекта.

Вершинам соответствуют выделенные точки, рёбрам –

3. Матрицей инцидентности

Это матрица размером , в которой строкам поставлены

4. Матрицей смежности

Это матрица размером , в которой и строкам

Способы задания орграфа

1. Перечислением (или списком) дуг с указанием их концов и добавлением

2. В виде геометрического объекта

Вершинам соответствуют выделенные точки, дугам –

3. В виде матрицы инцидентности

Это матрица размером , в которой строкам

4. В виде матрицы смежности

Это матрица размером , в которой и

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

Граф называется подграфом графа , если ,
При этом очевидно, что

K1, K2, K3 — подграфы графа G

Подграф H, содержащий все вершины графа G называется суграфом.

Подграфом, порожденным множеством вершин A из V (натянутым на множество )

Объединение графов

Пересечение графов

Кольцевая сумма графов

Коммутативность операций
многоместность

Удаление вершины

Если хi -вершина графа G = (X, A), то G–хi -порожденный подграф графа G на множестве вершин X–хi , т. е. G-хi является графом,

Удаление ребра или удаление дуги

Если ai - дуга графа G = (X, A), то G-ai – подграф графа G,

Замыкание или отождествление

Говорят, что пара вершин хi и xj в графе G замыкается (или отождествляется), если они заменяются

Стягивание

Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его

Графы и бинарные отношения

Бинарным отношением на множестве A называется любое подмножество R множества A2,

В графе антирефлексивного и симметричного отношения нет петель и для каждой

Маршруты. Цепи. Циклы для неориентированных графов

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

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

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

Цикл, в котором все вершины, кроме первой и последней, попарно различны,

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

Вершина называется начальная, если нет ребер, предшествующих , - конечная, если

Связный неориентированный граф

Две вершины a и b называются связными, если существует маршрут с

Граф G называется связным, если любая его пара вершин связана

Отношение связности является отношением эквивалентности. Данное отношение эквивалентности разбивает множество вершин

Подграфы, порожденные (натянутые на) множеством , называются связными компонентами графа G.

Методика выделения компонент связности в графе

1. Первоначальная разметка
2. Разметка

Маршруты. Цепи. Циклы в ориентированном графе

Простой путь — это путь, все вершины которого, кроме, быть может,

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

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

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

Числа внутренней и внешней устойчивости

Внутренняя устойчивость графа

Алгоритм Магу

Шаг 1. Построить матрицу смежности вершин графа G.
Шаг 2.

Внешняя устойчивость графа

Число внутренней устойчивости – число равное наименьшей из мощностей множеств внешней