- •Введение
- •Предисловие
- •1. Теория множеств
- •1.1. Понятие множества
- •1.2. Операции над множествами
- •1.3. Основные тождества алгебры множеств
- •1.4. Кортежи и декартово произведение множеств
- •1.5. Бинарные отношения. Свойства отношений
- •1.6. Соответствия. Отображения. Функции
- •Вопросы для самопроверки
- •2. Элементы комбинаторики
- •Вопросы для самопроверки
- •3. Логические операции
- •3.1. Основные понятия
- •3.2. Простейшие связки (операции)
- •3.3. Другие связки (операции)
- •3.4. Основные законы, определяющие свойства введенных логических операций.
- •4. Булевы функции
- •4.1. Основные понятия
- •4.2. Свойства элементарных булевых функций
- •4.3. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний
- •4.4. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
- •Задачи по теме «Булевы функции.»
- •Вопросы для самопроверки
- •5. Теория графов
- •5.1. Ориентированные графы
- •5.2. Неориентированные графы
- •5.3. Матричное задание ориентированных графов
- •5.4. Матричное задание неориентированных графов
- •5.5. Изоморфизм графов
- •5.6. Операции над графами
- •5.7. Пути, контуры, маршруты, цепи, циклы
- •5.8. Расстояние в графах
- •5.9. Связность в неориентированных графах
- •5.10. Связность в ориентированных графах
- •5.11. Эйлеровы графы
- •5.12. Гамильтоновы графы
- •5.13. Деревья
- •5.14. Остовные деревья
- •5.15 Взвешенные графы. Экстремальные остовы графов
- •5.16 Поиск кратчайшего пути между вершинами. Алгоритм Дейкстры
- •5.17 Раскраска графов. Раскраска вершин графа
- •Вопросы для самопроверки
- •Библиографический список
- •Оглавление
- •Подписано к изданию «8» октября 2014.
- •394026 Воронеж, Московский просп., 14
5.4. Матричное задание неориентированных графов
Неориентированный граф G(V, Q), где V={ ,..., } может быть задан квадратной матрицей смежности A = размерности , где – это число ребер, соединяющих вершины и , причем петли, "соединяющие" вершину с самой собой, считаются дважды.
Матрица смежности неориентированного графа симметрична относительно главной диагонали, т.е. A = . По главной диагонали для простых графов стоят нули, однако, если в вершине псевдографа находятся р петель, то на главной диагонали в строчке с номером k стоит число р. Если вершина i связана с вершиной j одним ребром, то элемент матрицы смежности aij равен единице, если эти вершины связаны s ребрами в мультиграфе, то аij= s.
Можно заметить, что матрица D = = АА составлена из целых чисел , которые равны числу путей длины 2, соединяющих вершины и . Матрица будет составлена из чисел, равных числу путей длины 3 (т. е. путей из 3-х ребер) из вершины в вершину .
Для простого неориентированного графа, изображенного на рис. 11, матрица смежности будет иметь вид
.
Неориентированный граф G(V, Q), где V={ ,..., }; Q={ ,..., } может быть задан матрицей инцидентности размерности n m, где n – число вершин, а m – число ребер графа. Элементы матрицы инцидентности B= равны 1, если ребро qj инцидентно вершине i и не является ее петлей; равны 2, если qj – петля при вершине vi, равны 0, если ребро qj неинцидентно вершине vi.
В матрице инцидентности сумма единиц в строке указывает на степень вершины .
В каждом столбце матрицы инциденций всегда ровно две единицы, остальные элементы равны нулю. Если ребра графа, изображенного на рис. 11, расположены в порядке нумерации следующим образом: , , , , , , то матрица инцидентности будет иметь вид
5.5. Изоморфизм графов
Два графа и называются изоморфными, если между множествами их вершин существует биективное (взаимно-однозначное) соответствие, такое, что в одном из графов вершины соединены ребрами в том и только в том случае, когда соответствующие им вершины соединены в другом графе. Два графа G1 и G2 называются изоморфными, если существует взаимно-однозначное отображение между множествами их вершин, сохраняющее смежность. Если ребра графа ориентированы, то их направление в изоморфных графах должно совпадать. Изоморфизм графов есть отношение эквивалентности, так как обладает свойствами рефлексивности, симметричности, транзитивности. Для того чтобы граф был изоморфен графу , необходимо и достаточно существования такой подстановки, которая бы установила взаимно-однозначное соответствие между вершинами графа, а также между их ребрами. Изоморфные графы можно отождествлять, т. е. их можно изобразить одним рисунком.
При замене графа любым ему изоморфным все свойства графа сохраняются. Графы, отличающиеся только нумерацией вершин, являются изоморфными.
Например, три графа, представленные на рис. 12, изоморфны, а графы на рис. 13 не изоморфны. Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается сложным.