Связность графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
?идентного и (в противном случае удаление некоторого ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит (ii)).
6. Гамильтоновы графы
Рис 1 Рис. 2
Рис. 3Рис. 4
граф связанность цепь дерево
В предыдущем параграфе мы обсудили проблему существования замкнутой цепи, проходящей через каждое ребро заданного связного графа G. Можно рассмотреть аналогичную проблему существования замкнутой цепи, проходящей ровно один раз через каждую вершину графа G. Ясно, что такая цепь должна быть циклом (исключая тривиальный случай, когда G является графом N1); если такой цикл существует, то он называется гамильтоновым циклом, а G называется гамильтоновым графом. Граф, который содержит простую цепь, проходящую через каждую его вершину, называется полугамильтоновым; заметим, что всякий гамильтонов граф является полугамильтоновым. На Рис. 1, 2 и 3 изображены соответственно не гамильтонов, полугамильтонов и гамильтонов графы.
Название гамильтонов цикл возникло в связи с тем, что сэр Уильям Гамильтон занимался исследованием существования таких циклов в графе, соответствующем додекаэдру; на Рис. 4 показан такой цикл (его ребра изображены сплошными линиями).
В теореме 6В получили необходимое и достаточное условие для того, чтобы связный граф был эйлеровым. Естественно было бы надеяться, что и для гамильтоновых графов удастся получить аналогичный критерий. Однако поиск такого критерия стал одной из главных нерешенных задач теории графов! О гамильтоновых графах в общем-то известно очень мало. Большинство известных теорем имеет вид: если G имеет достаточное число ребер, то G является гамильтоновым графом; вероятно, самой знаменитой из них является следующая теорема, принадлежащая Г. Э. Дираку и потому известная как теорема Дирака.
Теорема 7А (Дирак 1952). Если в простом графе с n (? 3) вершинами р(v) ? n/2 для любой вершины v, то граф G является гамильтоновым.
Замечание. Существует несколько доказательств этой широко известной теоремы; здесь приведем доказательство, принадлежащее Д. Дж. Ньюману.
Доказательство. Добавим к графу k новых вершин, соединяя каждую из них с каждой вершиной из G. Будем предполагать, что k - наименьшее число вершин, нужных для того, чтобы полученный граф G' стал гамильтоновым. Затем, считая, что k > 0, придем к противоречию.
Пусть v>p>w>…>v- гамильтонов цикл в G', где v и w - вершины из G, а р - одна из новых вершин. Тогда w не является смежной с v, так как в противном случае могли бы не использовать вершину р, что противоречит минимальности k. Более того, вершина (скажем w'), смежная вершине w, не может непосредственно следовать за вершиной v, смежной вершине v, потому что тогда могли бы заменить v>p>w>…>v>w>…>v на v>v>…>w>w>…> v, перевернув часть цикла, заключенную между w и v'. Отсюда следует, что число вершин графа G', не являющихся смежными с v, не меньше числа вершин, смежных с v (т. е. равно по меньшей мере n/2 + k); с другой стороны, очевидно, что число вершин графа G', смежных с w, тоже равно по меньшей мере n/2 + k. А так как ни одна вершина графа G' не может быть одновременно смежной и не смежной вершине w, то общее число вершин графа G', равное n +k, не меньше, чем n + 2k. Это и есть искомое противоречие. //
7. Бесконечные графы
В этом параграфе покажу, как можно обобщить некоторые определения, данные в предыдущих параграфах, на случай бесконечных графов. Напомним читателю, что бесконечным графом называется пара (V(G), Е(G))> где V(G)- бесконечное множество элементов, называемых вершинами, а Е(G) - бесконечное семейство неупорядоченных пар элементов из V(G) у называемых ребрами. Если оба множества V(G) и Е(G) счетны, то G называется счетным графом. Заметим, что наши определения исключают те случаи, когда V(G) бесконечно, а Е(G) конечно (такие объекты являются всего лишь конечными графами с бесконечным множеством изолированных вершин), или когда Е(G) бесконечно, а V(G) конечно (такие объекты являются конечными графами с бесконечным числом петель или кратных ребер).
Рис. 1
Некоторые определения, данные в гл. 2 (таких понятий, как смежный, инцидентный, изоморфный, подграф, объединение, связный, компонента), сразу переносятся на бесконечные графы. Степенью вершины v бесконечного графа называется мощность множества ребер, инцидентных v степень вершины может быть конечной или бесконечной. Бесконечный граф, все вершины которого имеют конечные степени, называется локально конечным; хорошо известным примером такого графа является бесконечная квадратная решетка, часть которой изображена на Рис. 1. Аналогичным образом можно определить локально счетный бесконечный граф - как граф, все вершины которого имеют счетную степень). Пользуясь этими определениями, докажем сейчас простой, но важный результат.
Теорема 8А. Каждый связный локально счетный бесконечный граф является счетным.
Доказательство. Пусть v - произвольная вершина такого бесконечного графа, и пусть А1 - множество вершин, смежных v, A2 - множество всех вершин, смежных вершинам из А1 и т. д. По условию теоремы А1 - счетно и, следовательно, множества A2, A3, ... тоже счетны (здесь используем тот факт, что объединение не более чем счетного множества счетных множеств счетно); следовательно, {v}, А1, А2,…- последовательность множеств, объединение которых счетно. Кроме того, эта последовательность содержит каждую вершину бесконечного графа в силу его связности. Отсю