- •Оглавление
- •Предисловие
- •1. Теоретико‑множественные основания дисциплины
- •1.1. Понятия и аксиомы теории множеств
- •1.2. Декартовы произведения, отношения и отношение эквивалентности
- •1.3. Понятия образа, прообраза, функции и отображения на конечном множестве. Аксиома выделения.
- •1.4. Аксиомы степени и бесконечности. Мощности и кардинальные числа множеств
- •1.5. Счетные и континуальные множества
- •1.6. Ординалы и трансфиниты. Аксиома выбора и континуум‑гипотеза
- •2. Основы математической логики
- •2.1. Высказывания и функции на высказываниях
- •2.2. Операции математической логики
- •2.3. Понятие формулы и свойства операций
- •2.4. Разложения булевых функций. Принцип двойственности. Совершенные нормальные формы.
- •2.5. Понятие полноты системы булевых функций
- •2.5. Исчисление предикатов
- •2.6. Введение в методы теории доказательств
- •1 Если X a,
- •0 Если X a.
- •1 Если X a,
- •0 Если X a.
- •3. Комбинаторика
- •3.1. Размещения
- •3.2. Размещения без повторений
- •3.3. Перестановки, подстановки и их свойства
- •3.4. Сочетания, структура соединений
- •3.5. Свойства биномиальных коэффициентов
- •Структура соединений
- •3.6. Понятие производящей функции
- •3.7. Соединения с повторениями
- •3.8. Разбиения множеств
- •3.9. Разбиения чисел
- •3.10. Композиции чисел
- •4. Основы теории графов
- •4.1. Основные понятия и определения
- •4.2. Графы и бинарные отношения
- •4.3. Понятие изоморфизма и изоморфизм плоских графов
- •4.4. Степени вершин графа
- •4.5. Представление графов матрицами
- •4.6. Представление графов списками инцидентности. Оценка пространственной сложности алгоритмов.
- •4.7. Маршруты, цепи, циклы и связность
- •4.7. Эйлеровы циклы и цепи
- •4.9. Гамильтоновы циклы. Оценка временной сложности алгоритмов
- •4.10. Деревья
- •4.11. Раскраска вершин и теорема Шеннона об информационной емкости графа
- •4.12. Раскраска ребер графа и теоремы о хроматическом классе
- •Ответы и решения
- •Список литературы
4.4. Степени вершин графа
Пусть G — неориентированный граф.
Локальной степенью (степенью) вершины v в графе G без петель называется число ребер (v), инцидентных этой вершине.
Теорема 4.3 Сумма степеней всех вершин графа без петель равна удвоенному числу m его ребер:
in = 1 (vi) = 2m (4.1)
Доказательство. Подсчет всех степеней вершин графа можно вести по вершинам. Количество ребер, инцидентных вершине v, равно (v). Но при этом каждое ребро считается дважды: в начальной и конечной вершинах. Следовательно, имеет место (4.1).
Теорема 4.4 Число вершин, имеющих нечетную степень, четно.
Доказательство. Обозначим 1 и 2 — количество всех вершин графа, имеющих нечетную и соответственно — четную степень. По теореме 4.3 имеем 1 + 2 = 2m. Следовательно, 1 = 2m - 2. Правая часть этого соотношения четна. Поэтому четна и левая. Теорема доказана.
Граф G называется однородным степени r, если локальные степени всех его вершин равны r. Примерами таких графов являются правильные многогранники: куб, октаэдр и т.д..
Из формулы (4.1) следует, что в однородном графе степени r число ребер равно:
m = nr / 2. (4.2)
Рассмотрим теперь случай ориентированного графа G.
Обозначим через (v) и *(v) числа ребер выходящих из вершины v и соответственно входящих в вершину v. Эти числа называются локальными степенями вершины v.
Для числа ребер в G, аналогично (4.1) имеем:
m = in = 1 (vi) = in = 1 *(vi) (4.3)
Ориентированный граф называется однородным степени n, если все его локальные степени имеют одно и тоже значение
(v) = *(v) = n (4.4)
для любой вершины из G.
Для однородного ориентированного графа имеет место соотношение, аналогичное (4.2):
m = nr (4.5)
4.5. Представление графов матрицами
Матричные представления графов используются при решении прикладных задач, особенно в тех случаях, когда при моделирование предметной области применяются алгебраические доказательства.
Пусть имеем граф G(V, U). Его матрицей смежности называется квадратная матрица (aij) порядка n2, где n — число вершин, а aij — число ребер, инцидентных вершинам vi и vj. Если граф не имеет кратных ребер, то aij = 1, когда vi и vj смежные и aij = 0, когда vi и vj не смежные. Если граф не имеет петель, то все его диагональные элементы равны нулю.
Рассмотрим примеры. На рисунке 4.8 изображены три неориентированных графа.
а)v1 б) v1 в) v1
v3 v2 v4 v3 v2 v4 v3 v2 v4
Рисунок 4.8
В первом случае (рисунок 4.8 а) имеем граф без петель и без кратных ребер. Во втором случае (рисунок 4.8 б) имеем кратные ребра. В третьем случае (рисунок 4.8 в) в вершинах v1 и v4 имеются петли. Соответствующие этим трем случаям матрицы смежности представлены ниже:
а) 0 1 0 1 б) 0 2 0 3 в) 0 1 0 1
1 0 1 1 2 0 1 1 1 0 1 1
0 1 0 0 0 1 0 0 0 1 0 0
1 1 0 0 3 1 0 0 1 1 0 2
Для неориентированного графа матрица смежности является симметрической: для любых i, j ≤ n имеем ai,j = aj,i. Для ориентированного графа матрица смежности симметрической, вообще говоря, не является.
Матрицей инциденций неориентированного графа называется матрица (aij) размера n m, где n — число вершин, а m — число ребер, построенная по правилу:
1, если i‑тая вершина инцидентна j‑тому ребру,
аij =
0 — в противном случае.
Так, соответствующая рисунку 4.8 б матрица инциденций представлена ниже:
Примечание.
Для графа на
рисунке 4.8 б приняты следующие обозначения
ребер:
a1
= (v1,v2)1,
a2
= (v1,v2)2,
a3
= (v1,v4)1,
a4
= (v1,v4)2,
a5
= (v1,v4)3,
a6
= (v2,v4),
a7
= (v2,v3).
1 1 1 1 1 0 0
1 1 0 0 0 1 1
0 0 0 0 0 0 1
0 0 1 1 1 1 0 .
Матрица инциденций неориентированного графа обладает следующими очевидными свойствами:
в графе без петель каждый столбец этой матрицы имеет в точности две единицы, соответствующие паре вершин ребра,
если в графе имеются петли, то в столбцах, соответствующих петлям, имеется по одной единице, а в остальных — по две.
Матрицей инциденций ориентированного графа называется матрица (аij) размера n m , где n — число вершин, а m — число ребер, построенная по правилу:
1, если i‑тая вершина начальная для j‑того ребра,
аij = -1, если i‑тая вершина конечная для j‑того ребра,
0, в случае, когда вершина и ребро не инцидентны.
Рассмотрим, например, граф, изображенный на рисунке 4.9.
v5
v2
v4
v3 v6
v1
Рисунок 4.9
Построенная, в соответствии с описанным правилом, матрица инциденций этого графа имеет вид:
Примечание.
Для графа на
рисунке 4.9 приняты следующие обозначения
дуг:
a1
= (v1,v2),
a2
= (v1,v3),
a3
= (v3,v2),
a4
= (v3,v4),
a5
= (v5,v4),
a6
= (v5,v6),
a7
= (v6,v5).
1 1 0 0 0 0 0
-1 0 -1 0 0 0 0
0 -1 1 1 0 0 0
0 0 0 -1-1 0 0
0 0 0 0 1 1 1
0 0 0 0 0 0 -1 .
Ориентированный граф, как правило, петель не содержит. Его матрица инциденций имеет в каждом столбце +1 и -1, которые отвечают началу и концу каждого ребра.