Решение: Построим граф G(V) c множеством вершин V={vi | i=1,..,6}, причем две вершины vi и vj соединяются ребром тогда и только тогда, когда vi + vj 
7. Поскольку отношение «x + y 7» симметрично, граф G(V) неориентированный.
Построим матрицу смежности (вершин).
A = 
Здесь элемент аij обозначает число ребер, идущих из вершины vi в вершину vj.
Поскольку наш граф неориентированный, матрица смежности симметрична.
Построим матрицу инциденций (ребер).
R = 
Здесь элемент rij равен 1, если вершина vi инцидентна ребру gj и 0 иначе.
Зададим неориентированный граф списком ребер:
| vi | v1 | v1 | v1 | v1 | v1 | v1 | v2 | v2 | v2 | v2 | v3 | v3 |
| vj | v1 | v2 | v3 | v4 | v5 | v6 | v2 | v3 | v4 | v5 | v3 | v4 |
Зададим неориентированный граф структурой смежности:
| Вершины | Последователи |
| v1 | v1, v2, v3, v4, v5, v6 |
| v2 | v1, v2, v3, v4, v5 |
| v3 | v1, v2, v3, v4 |
| v4 | v1, v2, v3 |
| v5 | v1, v2 |
| v6 | v1 |
Построим матрицу расстояний.
D = 
Здесь элемент dij обозначает длину кратчайшего пути из вершины vi в вершину vj
Поскольку наш граф неориентированный, матрица расстояний симметрична.
Определим эксцентриситет каждой из вершин, как максимальное из расстояний:
ε(v1) = 1, ε(v2) = ε(v3) = ε(v4) = ε(v5) = ε(v6) =2.
Диаметр графа равен 2, радиус 1, центр образует вершина v1.
Хроматическое число графа равно 4, это минимальное число цветов краски, необходимое для раскрашивания вершин графа таким образом, что никакие две смежные вершины не окрашены в один цвет.
Задача 2
Найти максимальный поток и минимальный разрез в транспортной сети, используя алгоритм Форда–Фалкерсона (алгоритм расстановки пометок). Проверить выполнение условия максимальности построенного полного потока. Источник – вершина 1, сток – вершина 8.
|
|
Решение: С помощью алгоритма Форда – Фалкерсона найдем наибольший поток из 1 в 8.
Шаг 1. Выбираем произвольный поток, например, 1 – 3 – 6 – 7 – 8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 6. Уменьшаем пропускные способности дуг этого потока на 6, насыщенную дугу 3 – 6 вычеркиваем.
Шаг 2. Выбираем произвольный поток, например, 1 – 4 – 5 – 8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 24. Уменьшаем пропускные способности дуг этого потока на 24, насыщенную дугу 4 – 5 вычеркиваем.
Шаг 3. Выбираем произвольный поток, например, 1 – 5 – 8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 57. Уменьшаем пропускные способности дуг этого потока на 57, насыщенную дугу 1 – 5 вычеркиваем.
Шаг 4. Выбираем произвольный поток, например, 1 – 2 – 8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 16. Уменьшаем пропускные способности дуг этого потока на 16, насыщенную дугу 2 – 8 вычеркиваем.
Шаг 5. Выбираем произвольный поток, например, 1 – 2 – 5 – 8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 13. Уменьшаем пропускные способности дуг этого потока на 13, насыщенную дугу 5 – 8 вычеркиваем.
Шаг 6. Выбираем произвольный поток, например, 1 – 2 – 5 – 7 – 8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 3. Уменьшаем пропускные способности дуг этого потока на 3, насыщенную дугу 1 – 2 вычеркиваем.
|
|
Шаг 7. Выбираем произвольный поток, например, 1 – 4 – 6 – 7 – 8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 1. Уменьшаем пропускные способности дуг этого потока на 1, насыщенную дугу 6 – 7 вычеркиваем.
Шаг 8. Выбираем произвольный поток, например, 1 – 4 – 6 – 5 – 7 – 8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 8. Уменьшаем пропускные способности дуг этого потока на 8, насыщенную дугу 4 – 6 вычеркиваем.
Больше путей нет. Суммарный поток 6 + 24 + 57 + 16 + 13 + 3 + 1 + 8 = 128.
Начинаем расстановку пометок. Начальная вершина (источник) 1 имеет пометку 0. Из этой вершины в вершины 3 и 4 ведут ненасыщенные дуги (см. рисунок), поэтому присваиваем им пометки соответственно, +3 и +4. Больше пометки расставить нельзя. Значит, максимальный поток найден, причем A = {2,5,6,7,8} (непомеченные вершины) образует разрез. Величина разреза 6+9+24+57+32=128.
Задача 3