§ 3. Примеры приложений теории графов
Транспортные задачи. В таких задачах вершинами графов являются пункты, а ребрами – транспортные маршруты, например, автомобильные или железные дороги, авиационные маршруты, линии электропередач, газо- или нефтепроводы. При этом решаются задачи оптимизации потоков, пунктов производства и потребления, построения потоков минимальной стоимости и др.
Технологические задачи. В задачах этого типа вершинами являются производственные элементы: предприятия, заводы, цеха, станки, конвейерные узлы и т. д., ребрами – потоки сырья, материалов и продукции между ними. При этом решаются задачи оптимальной нагрузки производственных элементов и оптимизации потоков сырья.
Управление проектами. Отдельные операции проекта рассматриваются как вершины, ребрами являются связи между ними, например, проект строительства некоторого объекта. При этом решаются задачи оптимизации (по времени, затратам, рискам или иным критериям) последовательности выполнения операций и распределения ресурсов между ними.
§ 4. Изоморфизм графов
Графы можно изображать по-разному. Вершины их можно располагать на плоскости произвольным образом, а ребра не обязательно представлять прямыми линиями. Таким образом, возникает вопрос: в каком случае разные диаграммы изображают по сути один и тот же граф? Для ответа на этот вопрос введем понятие изоморфизма графов.
Определение 1.9.
Говорят, что два графа
и
изоморфны,
и обозначают их
,
если существует взаимно однозначное
соответствие между вершинами графов
(
),
сохраняющее смежность, т. е. если в первом
графе имеется дуга
,
то ее образом является дуга из второго
графа:
,
и наоборот.
Рис. 1.10. Диаграммы одного и того же графа (или изоморфных графов).
Рис. 1.11. Диаграммы изоморфных графов.
Числовые характеристики, одинаковые для всех изоморфных графов, называют инвариантами графа. Например, число вершин n и число ребер m являются инвариантами графа. Заметим, что никакой набор инвариантов не определяет граф с точностью до изоморфизма.
На рис. 1.12 изображены графы, у которых число вершин и число ребер совпадают, но графы не являются изоморфными:
Рис. 1.12. Графы, не являющиеся изоморфными.
§ 5. Степень вершины
Определение 1.10. Степенью или валентностью вершины v называется число ребер, инцидентных этой вершине, обозначается deg(v).
Если
то вершина называется изолированной.
Если
то вершина называется концевой,
или висячей.
Если степени всех вершин графа равны некоторому числу k, то граф называется регулярным степени k. Степень регулярности является его инвариантом.
На рис. 1.13 представлена
диаграмма графа, у которого вершина
является изолированной, вершины
и
–
висячими, а вершина
имеет степень 2:
Рис. 1.13. Граф с изолированной и висячими вершинами.
На рис. 1.14 представлены диаграммы регулярных графов степени 2 и 3:
Рис. 1.14. Диаграммы регулярных графов степени 2 и 3.
Свойства степени.
Для любой вершины
степень
Степень вершины совпадает с числом смежных с ней вершин:
.Обозначим
число вершин, не смежных с вершиной v.
Тогда для любой вершины
верно
.Сумма степеней вершин графа равна удвоенному числу ребер (теорема Эйлера):
.
Доказательство. Каждое ребро соединяет две вершины, поэтому подсчитывая сумму степеней вершин графа, оно будет учтено дважды. ■
5. Число вершин нечетной степени четно.
Доказательство. По теореме Эйлера сумма степеней всех вершин – четное число. Сумма степеней вершин четной степени четна, следовательно, сумма степеней вершин нечетной степени также четна. Отсюда имеем, что число вершин нечетной степени четно. ■
Определение
1.11. Для
орграфа полустепенью
исхода
называется число дуг, исходящих из узла
х,
а полустепенью
захода –
число входящих дуг, обозначаются эти
числа
и
,
соответственно.
Свойства полустепеней исхода и захода.
1.
.
2.
.
3.
.
Доказательство следует из теоремы Эйлера, так как сумма полустепеней узлов орграфа равна сумме степеней вершин его основания. ■