V’ включается в V

E’ включается в E

Тогда этот граф будет Частью графа G

Подграф – часть графа, где вершины, связанные между собой ребром в исходном графе, также связаны между собой.

Покрывающий граф. Это часть графа, в котором каждой вершине инцидентно хотя бы одно ребро.

Суграф. Покрывающий граф, это такой граф, где V’ == V (тождественно)

Маршрут.

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

Цикл – это маршрут, в котором начальные и конечные вершины совпадают

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

d(x,y) – длина простой цепи из Х в У (минимальной, самой короткой)

1. d(x,y) = 0  x=y

2. d(x,y) >= 0

3. d(x,y) = d(y,x)

4. d(x,y) <= d(x,z) + d(y,z)

d(G) = max d(x,y)

x,y принадлежит V

две вершины связаны, если между ними есть маршрут.

Граф называется связным, если каждая пара вершин связана

Несвязный граф разбивается на компоненты связности

Эйлеров цикл – простой цикл, который обходит все ребра графа.

Гамильтонов цикл – простой цикл, который обходит все вершины графа.

С гамильтоновым циклом связаны многие задачи дискретной оптимизации (напр. Найти самый короткий).

Планарный граф – изображаемый на плоскости без пересечения ребер.

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

Соотношение |V| + |E| + |R| = 2 для планарных графов, где R – число областей Деревья.

Связанные ациклические графы - дерево.

Любые две вершины связаны единственной простой цепью

Корень – любая вершина

Концевая вершина (лист) – имеет степень 1

Вершины-братья имеют общую вершину.

Лекция 6

Среди деревьев выделяются 2 класса деревьев.

1. N-арные деревья. У каждой вершины не более, чем n потомков. Бинарные. У каждой вершины – не более, чем 2 потомка.

Цикломатическое число графа

γ (G) = |E| - |V| + N n – число связных компонентов. (кусков графа)

Цикломатическое число равно количеству элементарных циклов.

Для дерева оно равно 0.

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

3

Ориентированный граф – отношение, но уже не симметричное.

Граф Орграф

Степень вершины Входящие/выходящие степени

Ребро Дуга

Маршрут Путь

Цикл Контур

В матрице инцидентности есть отличие

	1	2	3
а	А	-1	1
б	-1	1
в

Для орграфов есть различия в связности

В вершину 3 мы не попадем никак.

Орграф СЛАБОсвязан, если связан его соотнесенный граф (без направлений)

Орграф односторонне связан, если для любой пары вершин Х,У существует путь из х в у, либо из у в х

Орграф сильно связан, если для любых Х,У существует путь из х в у И из у в х

Вершина У достижима из вершины Х, если существует ориентированный путь из Х в У

Множество достижимости – множество всех вершин, которые из нее достижимы.

G(x)

Граф называется К-раскрашенным, если G(x) = объединение V_i таких, что ребра в графе соединяют вершины из разных классов V_i (например, если вершины имеют цвет, то ребра соединяют 2 вершины разных цветов)

Min k(G) <= p+1, где p – точная верхняя грань степеней вершин

Разделяющие ребра – после их удаления граф становится несвязанным.

Дз

Докажите формулу для дерева E = V – 1

Определить цикломат число для графа на дом

На том графе сделать его орграфом и определить достижимость любой вершины.

Лекция 7