INTUIT.ru::Интернет-Университет Информационных Технологий

Интернет-Университет Информационных Технологий

http://www.INTUIT.ru

Графы и их применение

6. Лекция: Бесконечные графы
Бесконечные графы. Краткий обзор свойств бесконечных эйлеровых графов.

Бесконечные графы

В данной лекции мы обобщим некоторые определения на случай бесконечных графов. Бесконечным графом называется пара , где — бесконечное множество элементов, называемое вершинами, а — бесконечное семейство неупорядоченных пар элементов из , называемых ребрами.

Если оба множества и — счетны, то называется счетным графом. Заметим, что наши определения исключают те случаи, когда — бесконечно, а — конечно. Такие объекты являются всего лишь конечными графами с бесконечным множеством изолированных вершин. Когда — бесконечно, а — конечно, такие объекты являются конечными графами с бесконечным числом петель или кратных ребер.

Некоторые определения таких понятий, как "смежный", "инцидентный", "изоморфный", "подграф", "объединение", "связный", "компонента" переносятся на бесконечные графы. Степенью вершины бесконечного графа называется мощность множества ребер, инцидентных Степень вершины может быть конечной или бесконечной. Бесконечный граф, все вершины которого имеют конечные степени, называется локально конечным. Хорошо известным примером такого графа является бесконечная квадратная решетка, часть которой изображена на рисунке. Локально счетный бесконечный граф — это граф, все вершины которого имеют счетную степень. Под счетным множеством здесь и в дальнейшем понимается бесконечное множество, допускающее взаимно однозначное отображение на множество натуральных чисел.

Теорема Каждый связный локально счетный бесконечный граф является счетным.

Доказательство

Пусть — произвольная вершина такого бесконечного графа, и пусть $v_{1}$ — множество вершин, смежных , $v_{2}$ — множество всех вершин, смежных вершинам из $v_{1}$ , и т.д. По условию теоремы $v_{1}$ — счетно и, следовательно, множества $v_{2},v_{3},\ldots$ тоже счетны. Здесь используется тот факт, что объединение не более чем счетного множества счетных множеств счетно. Следовательно, $\{v\},v_{1},v_{2},\ldots$ — последовательность множеств, объединение которых счетно. Кроме того, эта последовательность содержит каждую вершину бесконечного графа в силу его связности. Отсюда и следует нужный результат.

Следствие Каждый связный локально конечный бесконечный граф является счетным.

Помимо этого, на бесконечный граф можно перенести понятие маршрута, причем тремя различными способами:

Конечный маршрут в определяется так. Маршрутом в данном графе называется конечная последовательность ребер вида $\{v_{0},v_{1}\}$ , $\{v_{1},v_{2}\} \dts \{v_{m-1},v_{m}\}$ . Маршрут можно обозначить и так: $v_{0} \to v_{1} \to v_{2} \to \ldots \to v_{m}$ .
Бесконечным в одну сторону маршрутом в сначальной вершиной $v_{0}$ называется бесконечная последовательность ребер вида $\{v_{0},v_{1}\}$ , $\{v_{1},v_{2}\}\ldots$ .
Бесконечным в обе стороны маршрутом в графе называется бесконечная последовательность ребер вида $\ldots,\{v_{-2},v_{-1}\},\{v_{-1},v_{0}\}$ , $\{v_{0}, v_{1}\},\{v_{1},v_{2}\},\ldots$

Бесконечные в одну сторону и в обе стороны цепи и простые цепи определяются очевидным образом, так же как и понятия длины цепи и расстояния между вершинами. Бесконечные простые цепи не так уж трудно обнаружить.

Теорема 6.1. (Кениг, 1936) Пусть — связный локально бесконечный граф, тогда для любой вершины существует бесконечная в одну сторону простая цепь с начальной вершиной .

Доказательство

Если — произвольная вершина графа , отличная от , то существует нетривиальная простая цепь от до , отсюда следует, что в имеется бесконечно много простых цепей с начальной вершиной . Поскольку степень конечна, то бесконечное множество таких простых цепей должно начинаться с одного и того же ребра. Если таким ребром является $\{ v,v_{1} \}$ , то, повторяя эту процедуру для вершины $v_{1}$ , получим новую вершину $v_{2}$ и соответствующее ей ребро $\{v_{1},v_{2}\}$ . Продолжая таким образом, получим бесконечную в одну сторону простую цепь $v\to v_{1} \to v_{2}\ldots$ .

Важное значение леммы Кенига состоит в том, что она позволяет получить результаты о бесконечных графах из соответствующих результатов для конечных графов. Типичным примером является следующая теорема.

Теорема 6.2. Пусть — счетный граф, каждый конечный подграф которого планарен, тогда и планарен.

Доказательство Так как — счетный граф, его вершины можно занумеровать в последовательность $v_{1},v_{2},v_{3},\ldots$ . Исходя из нее, построим строго возрастающую последовательность $G_{1} \subset G_{2} \subset G_{3} \ldots$ подграфов графа , выбирая в качестве $G_{k}$ подграф с вершинами $v_{1}\dts v_{k}$ и ребрами графа , соединяющими только эти вершины между собой. Далее, примем на веру тот факт, что графы $G_{i}$ могут быть уложены на плоскости конечным числом, скажем , топологически различных способов, и построим еще один бесконечный граф . Его вершины $w_{ij} ({i\ge 1}$ , ${1\le j\le m(i))}$ пусть соответствуют различным укладкам графов $\{G_{i}\}$ , а его ребра соединяют те из вершин $w_{ij}$ и $w_{kl}$ , для которых и плоская укладка, соответствующей $w_{ij}$ . Мы видим, что граф связен и локально конечен, поэтому, как следует из леммы Кенига, он содержит бесконечную в одну сторону простую цепь. А так как граф является счетным, то эта бесконечная простая цепь и дает требуемую плоскую укладку графа .

Стоит подчеркнуть, что если принять дальнейшие аксиомы теории множеств, в частности, аксиому выбора для несчетных множеств, то многие результаты можно перенести и на такие бесконечные графы, которые необязательно являются счетными.

Краткий обзор свойств бесконечных эйлеровых графов

Связный бесконечный граф называется эйлеровым, если в нем существует бесконечная в обе стороны цепь, содержащая каждое ребро графа . Такая бесконечная цепь называется (двусторонней) эйлеровой цепью. Назовем граф полуэйлеровым, если в нем существует бесконечная (в одну или в обе стороны) цепь, содержащая каждое ребро графа .

Теорема 6.3. Пусть — связный счетный граф, являющийся эйлеровым. Тогда:

В графе нет вершин нечетной степени.
Для каждого конечного подграфа графа бесконечный граф $\bar{H}$ (полученный путем удаления из ребер графа ) имеет не более двух бесконечных связных компонент.
Если, кроме того, степень любой вершины из четна, то $\bar{H}$ имеет ровно одну бесконечную связную компоненту.

Доказательство

Предположим, что — эйлерова цепь в графе . Тогда при всяком прохождении цепи через любую из вершин графа степень этой вершины увеличивается на два. А так как каждое ребро встречается в ровно один раз, то каждая вершина должна иметь четную степень. Получим, что степень любой вершины из должна быть либо четной, либо бесконечной.
Разобьем цепь на три подцепи $P_{-},\,P_{0},\,P_{+}$ так, что $P_{0}$ — конечная цепь, содержащая все ребра графа (и, быть может, другие ребра), а $P_{-}, P_{+}$ — две бесконечные в одну сторону цепи. Тогда бесконечный граф , образованный ребрами цепей $P_{-},P_{+}$ (а также инцидентными вершинами), имеет не более двух бесконечных компонент. Так как $\bar{H}$ получается из присоединением лишь конечного множества ребер, то отсюда и следует нужный результат.
Пусть — начальная и конечная вершины цепи $P_{0}$ . Покажем, что $v,\,w$ связаны в $\bar{H}$ . Если , то это очевидно. Если $v\ne w$ , то применяя следствие (связный графявляется полуэйлеровымтогда и только тогда, если в нем не более двух вершин имеют нечетные степени) к графу, полученному из $P_{0}$ путем удаления ребер графа предполагаем , что в этом(графе ровно две вершины, а именно , имеют нечетные степени), получим требуемый результат.

Можно получить соответствующие необходимые условия для полуэйлеровых бесконечных графов.

Теорема 6.4. Пусть — связный счетный граф, являющийся полуэйлеровым, но не эйлеровым. Тогда:

содержит либо не более одной вершины нечетной степени, либо не менее одной вершины бесконечной степени.
Для каждого конечного подграфа графа бесконечный граф $\overline{H}$ (описанный ранее) содержит ровно одну бесконечную компоненту.

Оказывается, условие двух предыдущих теорем является не только необходимым, но и достаточным. Этот результат сформулируем в виде следующий теоремы, доказательство которой выходит за рамки данных лекций, его можно найти у Оре (Оре О., Теория графов, "Наука". М.: 1968).

Теорема 6.5. Пусть — связный счетный граф. является эйлеровым графом тогда и только тогда, когда выполнены следующие условия:

В графе нет вершин нечетной степени;
для каждого конечного подграфа графа бесконечный граф $\overline{H}$ (полученный путем удаления из ребер графа ) имеет не более двух бесконечных связных компонент;
если, кроме того, степень любой вершины из четна, то $\overline{H}$ имеет ровно одну бесконечную связную компоненту.

Более того, является полуэйлеровым тогда и только тогда, если выполнены либо эти условия, либо следующие условия:

содержит либо не более одной вершины нечетной степени, либо не менее одной вершины бесконечной степени;
для каждого конечного подграфа графа бесконечный граф $\overline{H}$ (описанный ранее) содержит ровно одну бесконечную компоненту.

В графе нет вершин нечетной степени.
Для каждого конечного подграфа графа бесконечный граф $\overline{H}$ (полученный удалением из ребер графа ) имеет не более двух бесконечных связных компонент.
Если, кроме того, степень любой вершины из четна, то $\overline{H}$ имеет ровно одну бесконечную связную компоненту.