Файл: С. Д. Данилова С. С. Михайлова УланУдэ 2022дискретнаяматематика.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.12.2023
Просмотров: 284
Скачиваний: 10
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Тема 2.4. Синтез логических схем
2.4.1. Логическая схема и логические элементы
Одной из целей булевой алгебры является описание поведения и структуры логиче- ских схем. Логическая схема имеет вид «черного ящика», в котором вход – это набор буле- вых переменных, а выход – булева функция от этих переменных (рис. 2.1).
Рисунок 2.1 – Логическая схема
Метод «черного ящика» используется в тех случаях, когда предметом изучения явля- ется поведение сложных систем, а не их устройство. Исследователя интересуют лишь вход- ные и выходные сигналы, а не процессы, происходящие внутри самого устройства. Впер- вые понятие «черный ящик» ввел английский ученый У.Р. Эшби для изучения отношений между экспериментом и окружающей средой, когда предметом исследования служат по- токи информации.
Для того чтобы описать поведение «черного ящика», достаточно выразить выход в виде функции ????(????
1
, … , ????
????
) или построить истинные выражения, соответствующие логиче- ской связи между входными переменными, или минимизировать аналитическую формулу этих связей.
С развитием вычислительной техники математическая логика оказалась тем инстру- ментом, который дает возможность анализировать электрические цепи при проектирова- нии ЭВМ. Логическая схема устройства основывается на объединении электронных эле- ментов, реализующих конкретные логические операции.
Определение 2.37. Физическое устройство, реализующее одну из операций алгебры логики или простейшую логическую функцию, называется логическим элементом.
К основным типам логических элементов относятся:
1. Элемент НЕ (Инвертор) (рис. 2.2):
Рисунок 2.2 – Логический элемент НЕ
–
78 2. Элемент ИЛИ (Дизъюнктор) (рис. 2.3):
Рисунок 2.3 – Логический элемент
ИЛИ
3. Элемент И (Конъюнктор) (рис. 2.4):
Рисунок 2.4 – Логический элемент
ИЛИ
4. Элемент ИЛИ – НЕ (Дизъюнктор с отрицанием) (рис. 2.5):
Рисунок 2.5 – Логический элемент ИЛИ – НЕ
5. Элемент И – НЕ (Конъюнктор с отрицанием) (рис. 2.6):
Рисунок 2.6 – Логический элемент И – НЕ
79 6. Элемент Исключительное ИЛИ (рис. 2.7)
:
Рисунок 2.7 – Логический элемент
Исключительное
ИЛИ
7.
Элемент
Сумматор по модулю 2 (рис. 2.8):
Рисунок 2.8 – Логический элемент
Сумматор по модулю 2
Таким образом, любой логический элемент характеризуется:
1) наличием одного или нескольких входов, на которые подаются входные сигналы
(входные переменные);
2) наличием выхода, на котором формируется выходной сигнал (выходная перемен- ная);
3) определенной функцией, которая отображает зависимость выходного сигнала от входных.
Логические элементы 1, 2, 3 образуют булев базис (функционально-полную систему).
Логические элементы 1 и 2 или 1 и 3 образуют сокращенный (неполный) булев базис.
Логические элементы 4 или 5 образуют универсальный базис.
Логические элементы 3 и 7 образуют базис Жегалкина.
Функции логических элементов 6 и 7 совпадают при наличии только двух входов.
Определение 2.38. Схема, составленная из конечного числа логических элементов по определенным правилам, называется логической схемой.
Основным логическим функциям соответствуют выполняющие их схемные элементы.
Определение 2.39. Синтезом логической схемы называется процедура получения ло- гической схемы, реализующей заданную логическую функцию.
80
2.4.2. Построение логической схемы
Алгоритм построения логических схем:
1) определение числа переменных логической функции;
2) определение количества базовых логических операций и их порядок;
3) изображение каждой логической операции соответствующим ей логическим эле- ментом;
4) соединение логических элементов в порядке выполнения логических операций.
Пример
1. Построить логическую схему функции:
Имеем две переменные
x
1
и
x
2
, две логические операции – конъюнкция и дизъюнкция.
Строим схему (рис. 2.9):
Рисунок 2.9 – Логическая схема функции
2. Построить логическую схему функции:
Вычислить значения выражения для переменных
x
1
=1
и
x
2
=0
Схему строим слева направо в соответствии с порядком логических операций
(рис. 2.10):
81
Вычислим значение выражения:
2.4.3. Минимизация логической схемы
Целью минимизации логической схемы является уменьшение числа логических эле- ментов при аппаратной реализации логической функции, и, как следствие этого, повышение быстродействия, уменьшение размеров, стоимости и потребления энергии у проектируемой логической схемы.
Минимизация логической схемы состоит из следующих шагов:
1) составление логической формулы по данной логической схеме;
2) приведение полученной формулы к минимальной ДНФ одним из рассмотренных методов минимизации логической функции;
3) построение логической схемы по минимальной ДНФ.
Пример
Дана логическая схема (рис. 2.11):
&
1 0
1 0
1 1
0 0
82
Рисунок 2.11 – Исходная логическая схема
Составим по этой схеме логическую формулу:
f x x x
(
1
,
2
,
3
)
= x x
1
×
2
Ú x x
1
×
3
Ú x x
1
×
2.
Минимизация этой формулы даст следующую минимальную ДНФ (проверить самим):
Соответствующая полученной ДНФ логическая схема имеет вид (рис. 2.12):
Рисунок 2.11 – Минимизированная логическая схема
Контрольные вопросы
1. В каких случаях используется метод «черного ящика»?
2. Что представляет собой «черный ящик»?
83 3. Что такое логический элемент?
4. Какие основные логические элементы существуют, и как они изображаются?
5. Какие логические элементы образуют булев базис?
6. Какие логические элементы образуют сокращенный (неполный) булев базис?
7. Какие логические элементы образуют универсальный базис?
8. Какие логические элементы образуют базис Жегалкина?
9. Из чего состоит логическая схема?
10. Что такое синтез логической схемы?
11. В чем заключается метод минимизации логической схемы?
84
РАЗДЕЛ 3. ТЕОРИЯ ГРАФОВ
Множество самых разнообразных задач естественно формулируются в терминах гра- фов. Так, например, могут быть сформулированы задачи составления расписания, анализа связей в электротехнике, анализа цепей Маркова в теории вероятностей, в программирова- нии, в экономике, в социологии и т. д. Поэтому эффективные алгоритмы решения задач теории графов имеют большое практическое значение.
Тема 3.1. Основные понятия теории графов
3.1.1 Начальные определения
Определение 3.1. Неориентированным графом или просто графом называется пара множеств G =
(
????, ????
)
, где ???? – непустое конечное множество вершин, а
???? ∈ ????
– множество ребер.
Определение 3.2. Если ребра графа имеют направленность, то граф называется ориен-
тированным графом или просто орграфом. При этом ребра называются дугами. Если
(
????, ????) ∈ ????, то дуга
(
????, ????
)
называется исходящей из вершины
???? (начало дуги), и входящей в вершину????(конец дуги).
Геометрической интерпретацией графа является его представление на плоскости так, что вершины изображаются точками, а ребра – отрезками прямой или дугами, соединяю- щими их. В ориентированном графе для указания направленности дуг используются стрелки.
Пример
1. Дан неориентированный граф G =
(
????, ????
)
, где
???? =
{
1, 2, 3, 4, 5, 6};
???? = {(1,2), (2,3), (3,4), (1,5), (1,4), (3,1)}.
Геометрическая интерпретация графа
???? представлена на рисунке 3.1.
4
Рисунок 3.1 – Геометрическая интерпретация неориентированного графа
2 5
3 6
1
85 2. Дан ориентированный граф G =
(
????, ????
)
, где
???? =
{
1, 2, 3, 4, 5}
???? = {(3,1), (2,3), (3,5), (5,2), (4,5)}.
На графе, представленном на рисунке 3.2, к примеру, дуга (4,5) является исходящей из вершины 4 и входящей в вершину 5, соответственно, вершина 4 является началом, а вер- шина 5 – концом дуги (4,5).
5 3
Рисунок 3.2 – Геометрическая интерпретация ориентированного графа
Определение 3.2. Вершины ????, ???? ∈ ???? неориентированного графа G =
(
????, ????
)
называ- ются смежными, если существует ребро (????, ????)
∈
????; при этом каждая из вершин u и v назы- вается инцидентной ребру (????, ????), а ребро (????, ????) – инцидентным вершинам u и v.
Пример
В неориентированном графе (рис.2.1) вершины 2 и 3 являются смежными, они инци- дентны ребру (2,3); в свою очередь ребро (2,3) инцидентно вершинам 2 и 3.
Определение 3.3. Вершина ???? ∈ ???? ориентированного графа ???? =
(
????, ????
)
называется
смежной вершине ???? ∈ ???? , если существует дуга (????, ????)
∈
????; при этом каждая из вершин
????и
???? называется инцидентной дуге (????, ????), а дуга (????, ????) – инцидентной этим вершинам.
Пример
В ориентированном графе (рис.2.2), вершина 3 является смежной вершинам 1 и 5, но несмежной вершине 2. Вершины 1 и 3 инцидентны ребру (3,1); а дуга (3,1) инцидентна вершинам 1 и 2.
Определение 3.5. Если ребро инцидентно одной вершине ???? ∈ ????, т.е. (????, ????)
∈
????, то его называют петлей.
Определение 3.6. Граф, состоящий из единственной петли, называется граф-петлей.
Пример
4 2
1
86
На рисунке 3.3 а изображен граф, содержащий петлю (3,3); на рисунке 3.3б изображена граф-петля.
(а)
(б)
Рисунок 3.3 – (а) граф с петлей; (б) граф-петля
Определение 3.7. Различные ребра, инцидентные одной и той же паре вершин, назы- ваются кратными, причем их количество называется кратностью.
Пример
На рисунке 3.4 приведен граф, в котором кратность ребра (1,2) равна двум, а крат- ность ребра (1,5) – трем, кратность ребер (2,3), (1,3), (3,4), (1,4) – единице.
Рисунок 3.4 – Граф с кратными ребрами
Определение 3.8. Граф, содержащий петли и кратные ребра, называется мультигра-
фом.
Определение 3.9. Граф ???? =
(
????, ????
)
, |
????| = ????, без петель и кратных ребер называется
полным, если для любых вершин ????
????
, ????
????
∈ ????, ????, ???? = 1, … , ????,(????
????
, ????
????
) ∈ ????, т. е. если любые две вершины в нем смежные, обозначается ????
????
Заметим, что число ребер в полном графе вычисляется по формуле:
2 5
3 6
1 4
4 2
5 3
6 1
87
Пример
На рисунке 3.5 приведены примеры полных графов. Причем, в соответствии с приведенным замечанием имеем:
K
3
K
4
K
5
Рисунок 3.5 – Примеры полных графов
Определение 3.10. Графы ????
1
=
(
????
1
, ????
1
)
и ????
2
=
(
????
2
, ????
2
) называются изоморфными, если существует такое биективное (взаимно однозначное) отображение j:
Пример
На рисунке 3.6 приведены изоморфные графы ????
1 и ????
2 1
2 3
1'
2'
4 5
6 5'
4'
G
1
G
2
Рисунок 3.6 – Изоморфные графы
3 '
6 '
88
3.1.2. Машинные представления графов
Существует достаточно много способов машинного представления графов. Рассмот- рим две матричные формы и ряд других представлений, которые широко используются в алгоритмах на графах.
Определение 3.11. Матрица смежности ????(???? × ????)графа G =
(
????, ????
)
, |
????| = ????, опреде- ляется следующим образом:
Определение 3.12. Матрица инцидентности ????(???? × ????) графа ???? = (????, ????)
,
|????| =
????, |????| = ????, определяется следующим образом:
Определение 3.12. Список ребер графа – это представление графа G =
(
????, ????
)
, |
????| = ????,
|????| = ????, двумя массивами ???? = (????
1
… , ????
????
) и ???? =
(
????
1
… , ????
????
)
, в которых каждый элемент есть метка вершины графа: ????-е ребро графа выходит из вершины ????
????
и входит в вершину
????
????
Данное представление позволяет легко описать петли и кратные ребра. Определение
3.13. Структура смежности
????графа G =
(
????, ????
),
|
????| = ???? состоит из списков смежности
89 вершин графа
????
????
1
… , ????
????
????
Элементами списка смежности
????
????
????
,
???? = 1, … , ????
являются вершины, которые смежны вершине
????
????
Структуры смежности могут быть реализованы массивом из n линейно связанных списков. Хранение же списков смежности на сцепленной памяти желательно в алгоритмах, в основе которых лежат операции добавления и удаления вершин из списков. Таким обра- зом, граф G можем представить, как пару множеств:
Пример
Рассмотрим неориентированный граф G
1
(рис. 3.7 а) и ориентированный граф G
2
(рис. 3.7 б):
v
2
v
5
v
4
Рисунок 3.7 – (а) неориентированный граф; (б) ориентированный граф
Для этих графов построим описанные выше структуры их машинного представления.
Матрицы смежности:
v
1
v
3
v
4
v
5
v
6
v
1
v
2
v
3
а
(
)
( б )
e
1
e
2
e
3
e
4
e
5
e
6
e
1
e
2
e
3
e
4
e
5
90
Следует отметить, что во многих задачах на графах выбор представления является ре- шающим для эффективности алгоритмов.
3.1.3. Маршруты, пути, цепи, циклы
Определение 3.15. Маршрутом в графе ???? = (????, ????) называется конечная или бесконеч- ная последовательность ребер
(????
1
, … , ????
????
), такая, что каждые два соседних ребра ????
????−1
и
????
????i
инцидентны одной вершине.
Одно и то же ребро в маршруте может встречаться несколько раз.
В ориентированном графе маршрут определяется как путь.
Если маршрут является конечным, т. е. содержит конечное число ребер (????
1
, … , ????
????
), то в нем имеется первое ребро ????
1
и последнее ребро ????
????
Определение 3.16. Вершина v
0
, инцидентная ребру e
1
и не инцидентная ребру e
2
, назы- вается началом маршрута. Если же ребра e
1
и e
2
кратные, то необходимо специальное ука- зание, какое из них считать первым ребром маршрута.
Аналогично определяется конец маршрута v
n
Определение 3.17. Число ребер маршрута называется длиной маршрута.
91
Определение 3.18. Если в маршруте v
0
= v
n
, т. е. начало и конец маршрута совпадают, то такой маршрут называется циклическим.
Определение 3.19. Маршрут называется цепью, если все его ребра различны.
Определение 3.20. Цепь называется простой цепью, если любая вершина используется в ней не более одного раза.
Определение 3.21. Циклическая цепь называется циклом.
В ориентированном графе цикл называется контуром.
Определение 3.22. Простая циклическая цепь называется простым циклом.
Пример
В графе, изображенном на рисунке 3.8, определим маршруты, цепи, циклы.
Рисунок 3.8
Маршрут (1) – не цепь, так как ребро e
6
встречается в нем 2 раза.
Маршрут (2) – цепь, но не простая цепь, так как вершина v
5
используется дважды.
Маршрут (3) – простая цепь.
Маршрут (4) – циклический маршрут с началом и концом в вершине v
1
. Он не является цепью, так как ребро e
3
встречается в нем дважды и соответственно не является циклом.
Маршрут (5) – цикл, но не простой цикл, так как вершина v
2
используется дважды.
Маршрут (6) – простой цикл.
3.1.4. Часть графа, суграф, подграф
Определение 3.22. Граф ???? =
(
????′, ????′
)
, называется частью графа
???? =
(
????, ????
)
, если ????
′
⊆
???? и ????
′
⊆ ????. Если ????
′
= ????, то часть графа называется суграфом (остовным графом) графа ????.
v
2
v
3
v
4
v
6
v
5
v
1
e
1
e
2
e
3
e
4
e
5
e
6
e
7
e
8
e
9
e
10
2.4.1. Логическая схема и логические элементы
Одной из целей булевой алгебры является описание поведения и структуры логиче- ских схем. Логическая схема имеет вид «черного ящика», в котором вход – это набор буле- вых переменных, а выход – булева функция от этих переменных (рис. 2.1).
Рисунок 2.1 – Логическая схема
Метод «черного ящика» используется в тех случаях, когда предметом изучения явля- ется поведение сложных систем, а не их устройство. Исследователя интересуют лишь вход- ные и выходные сигналы, а не процессы, происходящие внутри самого устройства. Впер- вые понятие «черный ящик» ввел английский ученый У.Р. Эшби для изучения отношений между экспериментом и окружающей средой, когда предметом исследования служат по- токи информации.
Для того чтобы описать поведение «черного ящика», достаточно выразить выход в виде функции ????(????
1
, … , ????
????
) или построить истинные выражения, соответствующие логиче- ской связи между входными переменными, или минимизировать аналитическую формулу этих связей.
С развитием вычислительной техники математическая логика оказалась тем инстру- ментом, который дает возможность анализировать электрические цепи при проектирова- нии ЭВМ. Логическая схема устройства основывается на объединении электронных эле- ментов, реализующих конкретные логические операции.
Определение 2.37. Физическое устройство, реализующее одну из операций алгебры логики или простейшую логическую функцию, называется логическим элементом.
К основным типам логических элементов относятся:
1. Элемент НЕ (Инвертор) (рис. 2.2):
Рисунок 2.2 – Логический элемент НЕ
–
78 2. Элемент ИЛИ (Дизъюнктор) (рис. 2.3):
Рисунок 2.3 – Логический элемент
ИЛИ
3. Элемент И (Конъюнктор) (рис. 2.4):
Рисунок 2.4 – Логический элемент
ИЛИ
4. Элемент ИЛИ – НЕ (Дизъюнктор с отрицанием) (рис. 2.5):
Рисунок 2.5 – Логический элемент ИЛИ – НЕ
5. Элемент И – НЕ (Конъюнктор с отрицанием) (рис. 2.6):
Рисунок 2.6 – Логический элемент И – НЕ
79 6. Элемент Исключительное ИЛИ (рис. 2.7)
:
Рисунок 2.7 – Логический элемент
Исключительное
ИЛИ
7.
Элемент
Сумматор по модулю 2 (рис. 2.8):
Рисунок 2.8 – Логический элемент
Сумматор по модулю 2
Таким образом, любой логический элемент характеризуется:
1) наличием одного или нескольких входов, на которые подаются входные сигналы
(входные переменные);
2) наличием выхода, на котором формируется выходной сигнал (выходная перемен- ная);
3) определенной функцией, которая отображает зависимость выходного сигнала от входных.
Логические элементы 1, 2, 3 образуют булев базис (функционально-полную систему).
Логические элементы 1 и 2 или 1 и 3 образуют сокращенный (неполный) булев базис.
Логические элементы 4 или 5 образуют универсальный базис.
Логические элементы 3 и 7 образуют базис Жегалкина.
Функции логических элементов 6 и 7 совпадают при наличии только двух входов.
Определение 2.38. Схема, составленная из конечного числа логических элементов по определенным правилам, называется логической схемой.
Основным логическим функциям соответствуют выполняющие их схемные элементы.
Определение 2.39. Синтезом логической схемы называется процедура получения ло- гической схемы, реализующей заданную логическую функцию.
80
2.4.2. Построение логической схемы
Алгоритм построения логических схем:
1) определение числа переменных логической функции;
2) определение количества базовых логических операций и их порядок;
3) изображение каждой логической операции соответствующим ей логическим эле- ментом;
4) соединение логических элементов в порядке выполнения логических операций.
Пример
1. Построить логическую схему функции:
Имеем две переменные
x
1
и
x
2
, две логические операции – конъюнкция и дизъюнкция.
Строим схему (рис. 2.9):
Рисунок 2.9 – Логическая схема функции
2. Построить логическую схему функции:
Вычислить значения выражения для переменных
x
1
=1
и
x
2
=0
Схему строим слева направо в соответствии с порядком логических операций
(рис. 2.10):
81
Вычислим значение выражения:
2.4.3. Минимизация логической схемы
Целью минимизации логической схемы является уменьшение числа логических эле- ментов при аппаратной реализации логической функции, и, как следствие этого, повышение быстродействия, уменьшение размеров, стоимости и потребления энергии у проектируемой логической схемы.
Минимизация логической схемы состоит из следующих шагов:
1) составление логической формулы по данной логической схеме;
2) приведение полученной формулы к минимальной ДНФ одним из рассмотренных методов минимизации логической функции;
3) построение логической схемы по минимальной ДНФ.
Пример
Дана логическая схема (рис. 2.11):
&
1 0
1 0
1 1
0 0
82
Рисунок 2.11 – Исходная логическая схема
Составим по этой схеме логическую формулу:
f x x x
(
1
,
2
,
3
)
= x x
1
×
2
Ú x x
1
×
3
Ú x x
1
×
2.
Минимизация этой формулы даст следующую минимальную ДНФ (проверить самим):
Соответствующая полученной ДНФ логическая схема имеет вид (рис. 2.12):
Рисунок 2.11 – Минимизированная логическая схема
Контрольные вопросы
1. В каких случаях используется метод «черного ящика»?
2. Что представляет собой «черный ящик»?
83 3. Что такое логический элемент?
4. Какие основные логические элементы существуют, и как они изображаются?
5. Какие логические элементы образуют булев базис?
6. Какие логические элементы образуют сокращенный (неполный) булев базис?
7. Какие логические элементы образуют универсальный базис?
8. Какие логические элементы образуют базис Жегалкина?
9. Из чего состоит логическая схема?
10. Что такое синтез логической схемы?
11. В чем заключается метод минимизации логической схемы?
84
РАЗДЕЛ 3. ТЕОРИЯ ГРАФОВ
Множество самых разнообразных задач естественно формулируются в терминах гра- фов. Так, например, могут быть сформулированы задачи составления расписания, анализа связей в электротехнике, анализа цепей Маркова в теории вероятностей, в программирова- нии, в экономике, в социологии и т. д. Поэтому эффективные алгоритмы решения задач теории графов имеют большое практическое значение.
Тема 3.1. Основные понятия теории графов
3.1.1 Начальные определения
Определение 3.1. Неориентированным графом или просто графом называется пара множеств G =
(
????, ????
)
, где ???? – непустое конечное множество вершин, а
???? ∈ ????
– множество ребер.
Определение 3.2. Если ребра графа имеют направленность, то граф называется ориен-
тированным графом или просто орграфом. При этом ребра называются дугами. Если
(
????, ????) ∈ ????, то дуга
(
????, ????
)
называется исходящей из вершины
???? (начало дуги), и входящей в вершину????(конец дуги).
Геометрической интерпретацией графа является его представление на плоскости так, что вершины изображаются точками, а ребра – отрезками прямой или дугами, соединяю- щими их. В ориентированном графе для указания направленности дуг используются стрелки.
Пример
1. Дан неориентированный граф G =
(
????, ????
)
, где
???? =
{
1, 2, 3, 4, 5, 6};
???? = {(1,2), (2,3), (3,4), (1,5), (1,4), (3,1)}.
Геометрическая интерпретация графа
???? представлена на рисунке 3.1.
4
Рисунок 3.1 – Геометрическая интерпретация неориентированного графа
2 5
3 6
1
85 2. Дан ориентированный граф G =
(
????, ????
)
, где
???? =
{
1, 2, 3, 4, 5}
???? = {(3,1), (2,3), (3,5), (5,2), (4,5)}.
На графе, представленном на рисунке 3.2, к примеру, дуга (4,5) является исходящей из вершины 4 и входящей в вершину 5, соответственно, вершина 4 является началом, а вер- шина 5 – концом дуги (4,5).
5 3
Рисунок 3.2 – Геометрическая интерпретация ориентированного графа
Определение 3.2. Вершины ????, ???? ∈ ???? неориентированного графа G =
(
????, ????
)
называ- ются смежными, если существует ребро (????, ????)
∈
????; при этом каждая из вершин u и v назы- вается инцидентной ребру (????, ????), а ребро (????, ????) – инцидентным вершинам u и v.
Пример
В неориентированном графе (рис.2.1) вершины 2 и 3 являются смежными, они инци- дентны ребру (2,3); в свою очередь ребро (2,3) инцидентно вершинам 2 и 3.
Определение 3.3. Вершина ???? ∈ ???? ориентированного графа ???? =
(
????, ????
)
называется
смежной вершине ???? ∈ ???? , если существует дуга (????, ????)
∈
????; при этом каждая из вершин
????и
???? называется инцидентной дуге (????, ????), а дуга (????, ????) – инцидентной этим вершинам.
Пример
В ориентированном графе (рис.2.2), вершина 3 является смежной вершинам 1 и 5, но несмежной вершине 2. Вершины 1 и 3 инцидентны ребру (3,1); а дуга (3,1) инцидентна вершинам 1 и 2.
Определение 3.5. Если ребро инцидентно одной вершине ???? ∈ ????, т.е. (????, ????)
∈
????, то его называют петлей.
Определение 3.6. Граф, состоящий из единственной петли, называется граф-петлей.
Пример
4 2
1
86
На рисунке 3.3 а изображен граф, содержащий петлю (3,3); на рисунке 3.3б изображена граф-петля.
(а)
(б)
Рисунок 3.3 – (а) граф с петлей; (б) граф-петля
Определение 3.7. Различные ребра, инцидентные одной и той же паре вершин, назы- ваются кратными, причем их количество называется кратностью.
Пример
На рисунке 3.4 приведен граф, в котором кратность ребра (1,2) равна двум, а крат- ность ребра (1,5) – трем, кратность ребер (2,3), (1,3), (3,4), (1,4) – единице.
Рисунок 3.4 – Граф с кратными ребрами
Определение 3.8. Граф, содержащий петли и кратные ребра, называется мультигра-
фом.
Определение 3.9. Граф ???? =
(
????, ????
)
, |
????| = ????, без петель и кратных ребер называется
полным, если для любых вершин ????
????
, ????
????
∈ ????, ????, ???? = 1, … , ????,(????
????
, ????
????
) ∈ ????, т. е. если любые две вершины в нем смежные, обозначается ????
????
Заметим, что число ребер в полном графе вычисляется по формуле:
2 5
3 6
1 4
4 2
5 3
6 1
87
Пример
На рисунке 3.5 приведены примеры полных графов. Причем, в соответствии с приведенным замечанием имеем:
K
3
K
4
K
5
Рисунок 3.5 – Примеры полных графов
Определение 3.10. Графы ????
1
=
(
????
1
, ????
1
)
и ????
2
=
(
????
2
, ????
2
) называются изоморфными, если существует такое биективное (взаимно однозначное) отображение j:
Пример
На рисунке 3.6 приведены изоморфные графы ????
1 и ????
2 1
2 3
1'
2'
4 5
6 5'
4'
G
1
G
2
Рисунок 3.6 – Изоморфные графы
3 '
6 '
88
3.1.2. Машинные представления графов
Существует достаточно много способов машинного представления графов. Рассмот- рим две матричные формы и ряд других представлений, которые широко используются в алгоритмах на графах.
Определение 3.11. Матрица смежности ????(???? × ????)графа G =
(
????, ????
)
, |
????| = ????, опреде- ляется следующим образом:
Определение 3.12. Матрица инцидентности ????(???? × ????) графа ???? = (????, ????)
,
|????| =
????, |????| = ????, определяется следующим образом:
Определение 3.12. Список ребер графа – это представление графа G =
(
????, ????
)
, |
????| = ????,
|????| = ????, двумя массивами ???? = (????
1
… , ????
????
) и ???? =
(
????
1
… , ????
????
)
, в которых каждый элемент есть метка вершины графа: ????-е ребро графа выходит из вершины ????
????
и входит в вершину
????
????
Данное представление позволяет легко описать петли и кратные ребра. Определение
3.13. Структура смежности
????графа G =
(
????, ????
),
|
????| = ???? состоит из списков смежности
89 вершин графа
????
????
1
… , ????
????
????
Элементами списка смежности
????
????
????
,
???? = 1, … , ????
являются вершины, которые смежны вершине
????
????
Структуры смежности могут быть реализованы массивом из n линейно связанных списков. Хранение же списков смежности на сцепленной памяти желательно в алгоритмах, в основе которых лежат операции добавления и удаления вершин из списков. Таким обра- зом, граф G можем представить, как пару множеств:
Пример
Рассмотрим неориентированный граф G
1
(рис. 3.7 а) и ориентированный граф G
2
(рис. 3.7 б):
v
2
v
5
v
4
Рисунок 3.7 – (а) неориентированный граф; (б) ориентированный граф
Для этих графов построим описанные выше структуры их машинного представления.
Матрицы смежности:
v
1
v
3
v
4
v
5
v
6
v
1
v
2
v
3
а
(
)
( б )
e
1
e
2
e
3
e
4
e
5
e
6
e
1
e
2
e
3
e
4
e
5
90
Следует отметить, что во многих задачах на графах выбор представления является ре- шающим для эффективности алгоритмов.
3.1.3. Маршруты, пути, цепи, циклы
Определение 3.15. Маршрутом в графе ???? = (????, ????) называется конечная или бесконеч- ная последовательность ребер
(????
1
, … , ????
????
), такая, что каждые два соседних ребра ????
????−1
и
????
????i
инцидентны одной вершине.
Одно и то же ребро в маршруте может встречаться несколько раз.
В ориентированном графе маршрут определяется как путь.
Если маршрут является конечным, т. е. содержит конечное число ребер (????
1
, … , ????
????
), то в нем имеется первое ребро ????
1
и последнее ребро ????
????
Определение 3.16. Вершина v
0
, инцидентная ребру e
1
и не инцидентная ребру e
2
, назы- вается началом маршрута. Если же ребра e
1
и e
2
кратные, то необходимо специальное ука- зание, какое из них считать первым ребром маршрута.
Аналогично определяется конец маршрута v
n
Определение 3.17. Число ребер маршрута называется длиной маршрута.
91
Определение 3.18. Если в маршруте v
0
= v
n
, т. е. начало и конец маршрута совпадают, то такой маршрут называется циклическим.
Определение 3.19. Маршрут называется цепью, если все его ребра различны.
Определение 3.20. Цепь называется простой цепью, если любая вершина используется в ней не более одного раза.
Определение 3.21. Циклическая цепь называется циклом.
В ориентированном графе цикл называется контуром.
Определение 3.22. Простая циклическая цепь называется простым циклом.
Пример
В графе, изображенном на рисунке 3.8, определим маршруты, цепи, циклы.
Рисунок 3.8
Маршрут (1) – не цепь, так как ребро e
6
встречается в нем 2 раза.
Маршрут (2) – цепь, но не простая цепь, так как вершина v
5
используется дважды.
Маршрут (3) – простая цепь.
Маршрут (4) – циклический маршрут с началом и концом в вершине v
1
. Он не является цепью, так как ребро e
3
встречается в нем дважды и соответственно не является циклом.
Маршрут (5) – цикл, но не простой цикл, так как вершина v
2
используется дважды.
Маршрут (6) – простой цикл.
3.1.4. Часть графа, суграф, подграф
Определение 3.22. Граф ???? =
(
????′, ????′
)
, называется частью графа
???? =
(
????, ????
)
, если ????
′
⊆
???? и ????
′
⊆ ????. Если ????
′
= ????, то часть графа называется суграфом (остовным графом) графа ????.
v
2
v
3
v
4
v
6
v
5
v
1
e
1
e
2
e
3
e
4
e
5
e
6
e
7
e
8
e
9
e
10