13. Определение графа. Ориентированный и неориентированный граф. Мультиграф. Способы задания графа.

Граф, или неориентированный граф  — это упорядоченная пара  , для которой выполнены следующие условия:

•  — это непустое множество вершин, или узлов,

•  — это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

Ориентированный граф (сокращённо орграф)   — это упорядоченная пара  , для которой выполнены следующие условия:

•  — это непустое множество вершин или узлов,

•  — это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

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

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

1. Явное задание графа как алгебраической системы

<{ a,b,c,d } ; {( a,b ), ( b,a ),( b,c ),( c,b ),( a,c ),( c,a ),( c,d ),( d,c )}>

2. Геометрический

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

	a	b	c	d
a	0	1	1	0
b	1	0	1	0
c	1	1	0	1
d	0	0	1	0

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

	u	v	w	x
a	1	0	1	0
b	1	1	0	0
c	0	1	1	1
d	0	0	0	1

• В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

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

• В каждом столбце должны стоять две единицы, а все остальные символы - нули.

14. Полный граф. Дополнение графа. Операции с графами.

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

• Полный граф с  вершинами имеет   рёбер и обозначается  .

• Является регулярным графом степени  .

• Графы с   по  являются планарными. 

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

Граф Петерсена (слева) и его дополнение (справа):

Операции с графами:

1. Бинарные:

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

• пересечение графов

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

• декартово произведение графов

2. Унарные:

добавление вершины

удаление несвязной вершины

добавление ребра

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

разбиение ребра

расщепление вершины

склейка вершин

возведение графа в степень

15. Характеристики вершин графа.

16. Маршрут, путь и цикл.

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

Путь — последовательность рёбер (в неориентированном графе) и/или дуг (в ориентированном графе), такая, что конец одной дуги (ребра) является началом другой дуги (ребра). Или последовательность вершин и дуг (рёбер) в которой каждый элемент инцидентен предыдущему и последующему. Может рассматриваться как частный случай маршрута.

Цикл — замкнутая цепь.

Цепь в графе — маршрут, все рёбра которого различны.

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

17. Связность в неориентированных графах.

18. Связность в ориентированных графах. Нахождение компонентов связности.

19. Изоморфизм графов. Мост.

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

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

20. Дерево и его свойства о наличие моста, пути и о количестве ребер.

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

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

где   — число вершин,   — число рёбер графа.

Между любой парой вершин существует путь.

Каждое ребро дерева - мост.

21. Свойства дерева о концевых и корневых вершинах.

• Степень узла — количество исходящих дуг (или, иначе, количество поддеревьев узла).

• Концевой узел (лист) — узел со степенью 1 (то есть узел, в который ведёт только одно ребро; в случае ориентированного дерева — узел, в который ведёт только одна дуга и не исходит ни одной дуги).

• Узел ветвления — неконцевой узел.

• Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:

1. уровень корня дерева   равен 0;

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

• Дерево с отмеченной вершиной называется корневым деревом.

  • -й ярус дерева   — множество узлов дерева, на уровне   от корня дерева.

  • частичный порядок на вершинах:  , если вершины   и   различны и вершина   лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной  .

  • корневое поддерево с корнем   — подграф  .

• Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордамиграфа относительно остова.

• Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.