- •Раздел IV. Теория графов
- •1. Основные понятия теории графов. Примеры её применения
- •1.1. Псевдографы, графы, способы их задания
- •1.2. Деревья
- •1. Полное бинарное дерево.
- •2.1. Семантические деревья.
- •2.2. Деревья резолютивного вывода.
- •В) Из вершин второго уровня проводим ребра, соответству-ющие объектам {c1, c2}. Полученные вершины третьего уровня описывают все искомое множество размещений.
- •1.3. Полные графы
- •1.4. Двудольные графы
- •1.5. Единичные n – мерные кубы
- •1. Комбинаторика и алгебра логики.
- •2. Теория кодирования.
- •1.6. Сети
- •1. Однополюсные сети - корневые деревья.
- •2. Сетевое планирование.
- •3. Моделирование релейных и функциональных схем.
- •2. Операции и отображения на графах
- •2.1. Изоморфизм и гомеоморфизм графов
- •2.2. Обходы в графах
- •2. 3. Раскраски графов
- •2.4. Планарность графов
1.3. Полные графы
Определение. Пусть граф имеет n вершин. Если каж-дые две различные вершины графа соединены ребром, то граф называется полным. Полный граф, содержащий n вершин, обозначается Kn. Примеры полных графов с коли-чеством вершин n=1,2,3,4,5 показаны на Рис.4.10.
Рис. 4.10
Матрица смежности полного графа Kn является еди-ничной с нулевой диагональю – все элементы, кроме нуле-вых диагональных, равны 1.
С помощью полных графов изображают системы, в ко-торых все элементы связаны между собой, т.е. присутст-вуют все возможные связи. Такие системы называют турни-рами, поскольку в них каждый элемент связан со всеми остальными.
Задачи.
1. Найти число рёбер в полном графе Кn .
2. Найти общее число всех попарно различных простых циклов в полном графе Кn с пронумерованными вершинами.
3. Все рёбра полного графа Кn пронумерованы. Им присваи-вается ориентация. Сколько существует попарно различных вариантов ориентирования рёбер в Кn ?
1.4. Двудольные графы
Определение. Двудольным называется граф G = (V, X), множество вершин V которого можно разделить на две части V = V1 V2 таким образом, чтобы рёбра соединяли вершины только из разных частей. Обозначается как G = (V1, V2 ,Х).
257
Определение. Полным называется двудольный граф G = (V1, V2 ,Х), (V1=k,V2=l), у которого проведены все возможные ребра между вершинами V1 и V2 . Обозначается такой граф как Kk,l .
На Рис.4.11 показаны примеры полных двудольных графов K1,4 , K3,3 , K3,5 .
Рис. 4.11
Двудольные графы используют для изучения свойств таких систем, в которых объекты разбиты на две группы, внутри которых запрещены связи между объектами. Как правило, это характерно для групп разнородных объектов, между которыми необходимо ввести некоторые связи. Рассмотрим примеры задач данного типа.
1. Задачи о расписаниях .
Для выполнения некоторого заказа необходимо изго-товить комплект деталей А1, А2, …, А10, трудоемкости из-готовления которых составляют, соответственно, 15, 18, 20, 20, 26, 30, 33, 36, 40 и 60 мин. Требуется распределить данные детали между тремя рабочими В1, В2, В3 таким обра-зом, чтобы минимизировать общее время изготовления все-го комплекта деталей.
Каждый вариант распределения деталей может быть представлен в виде взвешенного двудольного графа. Один из оптимальных вариантов распределения показан на Рис.4.12.
2. Распределение ресурсов .
Задано множество некоторых заказов А1,А2, …, А5, сто-имости которых в одинаковых единицах измерения равны, соответственно, 1;1; 1; 2,6; 4. Также задано множество пред-
258
Рис.4.12
приятий В1, В2 , …, В6 – потенциальных изготовителей данных заказов, производственные мощности которых со-
относятся как 1 : 1,2 : 1,4 : 1,5: 2 : 2,4. Каждое предприятие может участвовать в выполнении любого числа заказов и
каждый заказ может выполняться любым числом предпри-ятий.
Требуется найти оптимальное распределение заказов по предприятиям, при котором будет минимизировано общее время их выполнения.
Каждый вариант распределения заказов может быть представлен в виде некоторого взвешенного двудольного графа. Один из оптимальных вариантов распределения дан на Рис. 4.13.
Задачи.
1. Найти число рёбер в полном двудольном графе Kk,l .
2. При каком соотношении чисел вершин k и l в полном дву-дольном графе Kk,l возможно построение простого цикла?
259
Рис.4.13