![]() |
1. Здесь мы будем рассматривать подграфы, может быть, несвязные, содержащие все вершины графа. Пусть G - граф, содержащий р занумерованных ребер е1,е2,.....,еp. Каждому подграфу Н G поставим в соответствие р-мерный вектор (а1, а2,..., ар) из нулей и единиц: аi = 1, если еi Н; аi = 0, если еi
Н (характеристический вектор подграфа Н). Это соответствие, очевидно, взаимнооднозначное. Более того, сумме по модулю 2 подграфов Н, и Н2 - Н1
Н2 - соответствует (поразрядная) сумма по модулю 2 их характеристических векторов. Над множеством коэффициентов {0, 1} множество всех подграфов образует линейное пространство: умножение любого подграфа Н на 1 дает Н, умножение на 0- пустой подграф, т.е. подграф, не содержащий ребер и состоящий из одних изолированных вершин графа G. Нетрудно видеть, что пространство подграфов графа G и пространство характеристических векторов его подграфов изоморфны и имеют размерность р. Базисом может служить множество всех однореберных подграфов. Характеристический вектор каждого такого подграфа содержит ровно одну единицу, причем для разных подграфов - на разных местах.
2. Назовем граф четным, если степени всех его вершин - четные числа. Любую элементарную цепь (кроме цикла) в четном графе можно продлить ребром, не принадлежащим цепи, так как конец цепи имеет степень 1 в цепи и степень не меньше 2 в графе. Если граф конечен, то, продолжая цепь, мы через конечное число шагов вторично придем в уже пройденную вершину, т.е. часть полученной (уже не элементарной) цепи образует элементарный цикл, после удаления которого остается четный граф, так как все степени изменяются на четное число (2 - для вершин цикла и 0 - для вершин, не принадлежащих циклу). В этом графе можно снова выделить некоторый элементарный цикл и т.д., пока в графе не останется ни одного ребра. Таким образом, каждый конечный четный граф можно представить в виде суммы попарно не пересекающихся (по ребрам) элементарных циклов, откуда, в частности, следует, что каждое его ребро циклическое.
Если конечный четный граф связен, то нетрудно показать (например, индукцией по числу его элементарных циклов), что в нем существует, простой (т.е. не самопересекающийся по ребрам) цикл, содержащий все ребра графа. Такой цикл называется эйлеровым циклом, а обладающий им граф называется эйлеровым графом. Поскольку каждая вершина простого цикла имеет в нем четную степень (каждое прохождение через вершину по циклу использует два ребра инцидентных этой вершине), то доказана следующая теорема.)
Теорема Эйлера. Для того чтобы конечный связный граф был эйлеровым, необходимо и достаточно, чтобы он был четным.
В конечном несвязном четном графе все компоненты связности - эйлеровы графы.
Будем называть вершину ориентированного графа равновесной, если число дуг, входящих в вершину, равно числу дуг, исходящих из нее.
Ориентированный граф назовем равновесным, если все его-; вершины равновесные. Обход (неориентированного) эйлерова графа по эйлерову циклу; ориентирует каждое ребро графа в направлении обхода. Ясно, что при такой ориентации эйлеров граф является равновесным. Пусть теперь дан равновесный граф. Повторяя предыдущее рассуждение (вместо циклов надо говорить о контурах), легко показать, что каждый конечный равновесный граф можно представить в виде суммы элементарных контуров, попарно не пересекающихся по ребрам (а также то, что в конечном связном равновесном графе существует простой контур, содержащий все ребра графа).
Другими словами, теорема Эйлера означает, что четность всех вершин графа есть необходимое и достаточное условие существования обхода графа, при котором каждое ребро проходится ровно один раз.
Из теоремы Эйлера можно вывести интересное следствие. В произвольном связном графе G раздвоим каждое ребро е = (V1,V2), т.е. заменим его парой кратных ребер е', е" с теми же вершинами. Степень каждой вершины удвоится и станет четной. В полученном четном графе G1 существует эйлеров цикл (а если ребра е', е" ориентировать в противоположных направлениях, то каждая вершина будет равновесной и существует эйлеров контур). Если рассмотреть его как обход графа G1, снова склеить пары е', е" в одно ребро, то в первоначальном графе G эта траектория будет (уже не простым) циклом, проходящим через каждое свое ребро ровно два раза (причем в противоположных направлениях). Итак, в каждом связном графе существует цикл, содержащий ровно 2 раза каждое ребро графа, что можно трактовать как соответствующий обход лабиринта с возвращением в начало обхода.
![]() |
3. Элементарный путь, проходящий через все вершины графа, называется гамильтоновым; если совпадают его начало и конец, то это гамильтонов цикл.
Известная задача о коммивояжере формулируется так: имеется n городов, попарные расстояния между которыми заданы. Коммивояжер желает посетить все города так, чтобы суммарная длина пути была минимальной. Это означает, что нужно найти гамильтонов путь минимальной длины в полном графе Кn, ребрам которого приписаны положительные числа - длины ребер (для варианта задачи - обхода с возвращением в начало пути - ищется минимальный гамильтонов цикл).
Последовательность перестановок, описанная ранее, может быть интерпретирована следующим образом. Рассмотрим граф Gn, вершины которого соответствуют всем (n!) перестановкам множества {1, 2,..., n},-а ребра связывают пары вершин, отличающиеся транспозицией соседних элементов (таким образом, каждая вершина соединена с (n - 1) другими вершинами). Тогда указанная последовательность соответствует гамильтонову пути в графе Gn. На рисунке 10 а,б - соответствующие иллюстрации для n = 3 и n = 4.
4. Сумма двух четных подграфов любого графа есть также четный подграф. Если s1 и s2- степени некоторой вершины в подграфах H1 и H2 соответственно, a s12- ее степень в пересечении Н1 Н2, то степень s(
) вершины
в подграфе Н1
Н2 равна (s1 - s12) + (s2 - s12) = s1 + s2 - 2S12 (кстати, это пример применения комбинаторной формулы включения- исключения). Если s1 и s2 - четные, то s(
) также четное. Поэтому четные подграфы образуют подпространство в пространстве всех подграфов, которое совпадает с подпространством, натянутым на множество всех элементарных
Перейдем к выяснению размерности v этого подпространства. Пусть G - связный граф с р ребрами и b вершинами., D - некоторый его остов. Число хорд равно (р - b + 1). Каждая хорда (, β) вместе c единственной элементарной цепью [
, β]
D образует элементарный цикл, причем векторы всех таких циклов (для разных хорд) образуют независимую систему
, так как каждый из циклов содержит ребро (свою хорду), не принадлежащее ни одному из остальных циклов системы. Отсюда v > р - b + 1.
С другой стороны, каждый четный подграф, в частности любой простой цикл выражается через циклы системы . Действительно, прибавим к четному подграфу Н те циклы из Z, которые содержат хорды графа, принадлежащие Н. Полученная сумма не будет содержать ни одной хорды (каждая хорда входит в сумму дважды: в подграф Н и в один из циклов системы
), т.е. будет некоторым подграфом дерева D, откуда следует, что это пустой подграф, так как в противном случае четный подграф (сумма Н и циклов), имеющий элементарные циклы, содержался бы в дереве D. Таким образом, v = р - b + 1.
Для несвязного графа с k компонентами связности базис пространства четных подграфов получается объединением базисов его связных компонент, а число ребер и вершин суммируется. Поэтому,
если i-я компонента содержит рi ребер и bi вершин, то v = р - b + k, где
,
.
Число v называется цикломатическим числом графа. Ввиду того, что v
0, для любого графа справедливо неравенство k
b - р. Деревья - это связные графы с цикломатическим числом, равным 0
1) Для полного графа К5 (5 вершин, C52=10 ребер) 2) Для графа на рисунке 7 имеем р=18, b = 11, k = 1, откуда v= 18 - 11 + 1 =8. 3) Рассмотрим соотнесенный неориентированный граф для графа на рисунке 106. Число его вершин равно числу перестановок из 4 элементов: 4! = 24. Степени всех вершин равны 3. Поэтому число ребер графа р = 24 ∙ 3 / 2 = 36. Граф связен, т.е. k = 1. Цикломатическое число равно v = 36 -24+ 1 = 13. |
![]() |
Практические задания |
![]() |
Tест для самоконтроля |