Теория графов. Тезаурус

ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

Множество состоит из элементов, если a является элементом множества

ДВА МНОЖЕСТВА
Если каждый элемент множества A является элементом множества B, то

ЧЕТЫРЕ ДЕЙСТВИЯ, ПРОВОДИМЫЕ НАД МНОЖЕСТВАМИ

1.Объединение. Так называется множество C, которое строится

КЛАССИФИКАЦИЯ ГРАФОВ

Графы делятся на два класса: ориентированные и неориентированные. Применительно к

ОПРЕДЕЛЕНИЕ НЕОРИЕНТИРОВАННОГО ГРАФА

Неориентированным графом G(X,U) называется пара множеств X, U, где

ОПРЕДЕЛЕНИЕ ИНЦИДЕНТНОСТИ И СМЕЖНОСТИ

Если в некотором графе G(X,U) , где

СТЕПЕНЬ ВЕРШИНЫ

Количество ребер, инцидентных данной вершине x называется ее степенью или

ГРАФ И ЕГО СТЕПЕНИ ВЕРШИН

Граф G(X,U)

1

2

3

4

5

4
1
2
2 3

ПОДГРАФЫ И СУГРАФЫ

Пусть теперь - два графа таких, что и ;

МАТРИЦА СМЕЖНОСТИ ВЕРШИН

Применительно к некоторому графу G(X,U) построим квадратную матрицу М,

ПРИМЕР 1

Граф G(X,U) Матрица смежности вершин

1

2

3

4

5

МАТРИЦА ИНЦИДЕНЦИЙ ГРАФА

Поставим в соответствие графу G(X,U) еще одну матрицу N,

ПРИМЕР 2

Граф G(X,U) Матрица инциденций

1

2

3

4

5

МАРШРУТЫ НА ГРАФАХ

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

СВЯЗНОСТЬ ГРАФА

Вершины в приведенных выше обозначениях называются концами маршрута и связанными

ТРИ ОПЕРАЦИИ НА ГРАФАХ

«Стягивание» ребра.
Удаление вершины.
Удаление ребра.

ДЕРЕВЬЯ НА ГРАФАХ

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

ЭЙЛЕРОВЫ ЦИКЛЫ

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

ПРИМЕР ЭЙЛЕРОВА ГРАФА

1

2

3

4

5

ГАМИЛЬТОНОВЫ ГРАФЫ

Граф G(X,U) называется гамильтоновым, если в нем существует простой цикл,

ПРИМЕРЫ ГАМИЛЬТОНОВА ГРАФА

1

2

3

4

5

1

2

3

4

БИХРОМАТИЧЕСКИЕ ГРАФЫ

Граф G(X,U) называется двудольным или бихроматическим (см. часть 1, главу

САМОСТОЯТЕЛЬНО

Определить вид следующих графов:

2

4

1

3

1

2

4

3

5

4

1

3

2

а) б)
в) г)

1

2

3

ПРИМЕР БИХРОМАТИЧЕСКОГО ГРАФА

2

4

1

3

5

6

САМОСТОЯТЕЛЬНО

Определить вид следующих графов:

2

4

1

3

1

2

4

3

а) б)

5

4

1

3

2

в)

5

ВЗВЕШЕННЫЕ ОРГРАФЫ

Ориентированный граф Смешанный граф

1

2

4

5

3

1

2

3

4

5

3 7 2 9
1
8 12
10

ПРЕДСТАВЛЕНИЕ ОРГРАФА В КОМПЬЮТЕРЕ

Орграф G(X,U)

1

2

4

5

3

3 7 2 9

ОПРЕДЕЛЕНИЯ 1

Граф G(X,U) называется ориентированным или орграфом, если на всех

ПРИМЕРЫ

Орграф G(X,U)

1

2

4

5

3

3 7 2 9
1
8 12
10
а)

ОПРЕДЕЛЕНИЯ 2

Замкнутый путь L(p,р) называется контуром, причем по аналогии с циклами,

САМОСТОЯТЕЛЬНО

Выделить на графе G(X,U):
простые пути;
сложные пути;
простые контуры;
сложные контуры;
Гамильтоновы контуры;
Является ли

ВЫДЕЛЕНИЕ ВСЕХ КОНТУРОВ И ПУТЕЙ НА ОРГРАФЕ

Выделение всех путей и контуров

ПУТИ И КОНТУРЫ, СОДЕРЖАЩИЕ ДВЕ И ТРИ ДУГИ
M*M =
M*M*M =

*

=

*

=

=