Комбинаторика и теория графов

1. Комбинаторика и теория графов

Лекции – 16 часов
Практические занятия /
Лабораторные работы – 16 часов
Самостоятельная работа – 76 часов
Экзамен – 4 семестр

2. Лекция 1. Основные понятия теории графов

1. Граф, основные понятия
Графом G=(X, A) называется совокупность двух множеств: X = (x1, x2, …, xn)
множества вершин и A = (a1, a2, …, am) множества ребер. Ребро ak есть пара вершин (xi,
xj). Неоринтированный граф.
Если (xi, xj) – упорядоченная пара, то называется дугой, xi – начальная, xj – конечная
вершина, при этом граф называется ориентированным (орграфом).
Если (xi, xj) – ребро (дуга), то вершины xi, xj называются смежными, а ребро (дуга)
ak называется инцидентным вершинам xi, xj .
Ребро (xi, xj) называется петлей.
Вершина xi не инцидентная никакому ребру (дуге) называется изолированной.
Если xi, xj соединяются несколькими ребрами (дугами), то ребра (дуги) называются
кратными.
Граф без петель и кратных ребер называется простым графом.
Мультиграф – обобщение понятия графа, может содержать петли и кратные ребра.
Курс «Комбинаторика и теория графов»
1

3. 1. Граф, основные понятия

2
1. Граф, основные понятия
Маршрутом в графе называется чередующаяся последовательность вершин и ребер,
в которой любые два соседних элемента инцидентны.
Если все ребра различны, то маршрут называется цепью.
Замкнутая цепь называется циклом.
Если все вершины (а значит, и ребра) различны, то
маршрут называется простой цепью.
Замкнутая простая цепь называется простым циклом.
Для орграфов цепь называется путем, а цикл – контуром.
1)
2)
3)
4)
5)
В графе на рис.1:
x1, x3, x1, x4 –
x1, x3, x5, x2, x3, x4 –
x1, x4, x3, x2, x5 –
x1, x3, x5, x2, x3, x4, x1 –
x1, x3, x4, x1 –
x1
x2
x3
x4
x5
рис.1
маршрут, но не цепь;
цепь, но не простая цепь;
простая цепь;
цикл, но не простой цикл;
простой цикл.
Граф называется полным, если любые две различные вершины связаны ребром
(Орграф - называется турниром).
Граф называется двудольным, если ребра соединяют только вершины разных
непересекающихся множеств.
Деревом называется связный граф без циклов.
Лекция 1. Основные понятия теории графов

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

3
2. Способы задания графа
Известны различные способы представления графов в памяти компьютера, которые
различаются объемом занимаемой памяти и скоростью выполнения операций над
графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее
приведены четыре наиболее часто используемых представления с указанием
характеристики n(p,q) – объема памяти для каждого представления. Здесь p – число
вершин, а q – число ребер.
Матрица смежности
Представление графа с помощью квадратной булевой матрицы M, отражающей
смежность вершин, называется матрицей смежности, где
1, если вершина xi смежна с вершиной x j
M i, j
0, если вершины xi и x j не смежны.
Для матрицы смежности n(p,q) = O(p2).
0
2
4
0
0
a1
a4
a7
M
a3
a6
0
0
a2
a5
a8
0
1
3
5
Лекция 1. Основные понятия теории графов
6
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
1
0
0
0
1
0
0

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

4
2. Способы задания графа
Матрица инцидентности
Представление графа с помощью матрицы H, отражающей инцидентность вершин и
ребер, называется матрицей инцидентности, где для неориентированного графа
1, если вершина xi инцидентна ребру a j ,
H i, j
0, в противном случае,
а для орграфа
1, если дуга a j выходит из вершины xi ,
H i, j 1, если дуга a j входит в вершину xi ,
0, если вдуга a j не инцидентна вершине xi .
Для матрицы инцидентности n(p,q) = O(pq).
2
a1
a3
1
a2
3
4
a4
a5
a6
5
a7
a8
6
Лекция 1. Основные понятия теории графов
1 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 1 1 1 1 0 0 0
H
0
0
0
1
0
1
1
0
0 0 0 0 1 1 0 1
0
0
0
0
0
0
1
1

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

Списки смежности
Представление графа с помощью списочной структуры, отражающей смежность
вершин и состоящей из массива указателей на списки смежных вершин.
Структура смежности состоит из списков Dots[x] вершин графа, смежных с
вершиной x. Списки Dots[x] составляются для каждой вершины графа.
В случае представления неориентированных графов списками смежности n(p,q) =
O(p+2q), а в случае ориентированных графов n(p,q) = O(p+q).
ai: (xi , xj)
2
4
xi: Dots[xi]
1: (1, 2)
1: 2, 3
2: (1, 3)
a1
2: -1, 3
a4
a7
3: (2, 3)
a3
a6
3: -1, -2, 4, 5
4: (3, 4)
4: -3, 5, 6
5: (3, 5)
5:
-3,
-4,
-6
a2
a5
a8
6: (4, 5)
1
6
3
5
6: -4, 5
7: (4, 6)
8: (6, 5)
Массив ребер (массив дуг)
Представление графа с помощью массива структур отражающего список пар
смежных вершин, называется массивом ребер (или, для орграфов, массивом дуг).
Для массива ребер (или дуг) n(p,q) = O(2q).
Лекция 1. Основные понятия теории графов
5

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

6
2. Способы задания графа
Структуры для представления графов
Наиболее часто применяется два способа представления графа: в виде списков
смежных вершин и матрицы смежности.
Первый способ предпочтительнее для разреженных графов, в которых количество
ребер E намного меньше квадрата количества вершин V2. Для хранения данных
используются массивы или списки.
const int Nv = 6;
int[][] Adj = new int[Nv+1][];
Adj[1] = new int[2] {2, 3};
Adj[2] = new int[2] {-1, 3};
Adj[3] = new int[4] {-1, -2, 4, 5};
Adj[4] = new int[3] { -3, 5, 6 };
Adj[5] = new int[3] {-3, -4, -6};
Adj[6] = new int[2] {-4, 5};
const int Nv = 6;
int [ , ] M = new int[Nv, Nv]
{ {0, 1, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 1, 1},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0}};
При использовании матрицы смежности мы нумеруем вершины графа числами
1,2,...,V и рассматриваем матрицу A, в которой a[i,j]=1 если есть ребро между
вершинами i и j и a[i,j]=0 в противном случае. В случае взвешенного графа, вместо
единицы в a[i,j] удобно хранить вес ребра.
Минус этого метода заключается в том, что матрица занимает объем памяти порядка
V2 независимо от количества ребер в графе.
Лекция 1. Основные понятия теории графов

8. 3. Обзор задач теории графов

Графы нашли применение практически во всех отраслях научных знаний.
Наибольшей популярностью теоретико-графовые модели используются при
исследовании коммуникационных сетей, систем информатики, химических и
генетических структур, электрических цепей и других систем сетевой структуры.
Далее перечислим некоторые типовые задачи теории графов и их приложения:
Задача о кратчайшей цепи (кратчайшем пути)
•замена оборудования
•составление расписания движения транспортных средств
•размещение пунктов скорой помощи, телефонных станций и др.
Задача о максимальном потоке
•анализ пропускной способности коммуникационной сети
•организация движения в динамической сети
•оптимальный подбор интенсивностей выполнения работ
•синтез двухполюсной сети с заданной структурной надежностью
•задача о распределении работ
Связность графов и сетей
•проектирование кратчайшей коммуникационной сети
•синтез структурно-надежной сети циркуляционной связи
Лекция 1. Основные понятия теории графов
7

9. Контрольные вопросы

1. Основные понятия теории графов.
2. Некоторые основные типы графов.
3. Маршруты на графе.
4. Типы структур графов.
5. Способы представления графов.
6. Программные структуры представления графов.
7. Задачи теории графов.
Лекция 1. Основные понятия теории графов
8