§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 -- произвольная вершина такого бесконечного графа, и пусть А₁ -- множество вершин, смежных v, A₂ -- множество всех вершин, смежных вершинам из А₁ и т. д. По условию теоремы А₁ -- счетно и, следовательно, множества A₂, A₃, ... тоже счетны (здесь используем тот факт, что объединение не более чем счетного множества счетных множеств счетно); следовательно, {v}, А₁, А₂,…-- последовательность множеств, объединение которых счетно. Кроме того, эта последовательность содержит каждую вершину бесконечного графа в силу его связности. Отсюда и следует нужный результат. //

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

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

(i) конечный маршрут в G определяется так же, как и в §5;

(ii) бесконечным в одну сторону маршрутом в G (с начальной вершиной v₀,) называется бесконечная последовательность ребер вида {v₀, v₁}, {v₁, v₂}, ... ;

(iii) бесконечным в обе стороны маршрутом в G называется бесконечная последовательность ребер вида ..., {v_-2, v_-1 }, { v_-2, v₀}, { v₀, v₁},{ v₁, v₂} ,... .

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

Теорема 8С (Кёниг 1936). Пусть G -- связный локально конечный бесконечный граф; тогда для любой его вершины v существует бесконечная в одну сторону простая цепь с начальной вершиной v.

Доказательство. Если z -- произвольная вершина графа G, отличная от v, то существует нетривиальная простая цепь от v до z; отсюда следует, что в G имеется бесконечно много простых цепей с начальной вершиной v. Поскольку степень v конечна, то бесконечное множество таких простых цепей должно начинаться с одного и того же ребра. Если таким ребром является {v, v₁}, то, повторяя эту процедуру для вершины v₁, получим новую вершину v₂ и соответствующее ей ребро {v₁, v₂}. Продолжая таким образом, получим бесконечную в одну сторону простую цепь v>v₁>v₂… .

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

Теорема 8D. Пусть G -- счетный граф, каждый конечный подграф которого планарен; тогда и G планарен.

Доказательство. Так как G-- счетный граф, то его вершины можно занумеровать в последовательность v₁, v₂, v₃,.... Исходя из нее, построим строго возрастающую последовательность G₁ G₂ G₃ ... подграфов графа G, выбирая в качестве G_k подграф с вершинами v₁, ..., v_k и ребрами графа G, соединяющими только эти вершины между собой. Далее, примем на веру тот факт, что графы G_i могут быть уложены на плоскости конечным числом (скажем m(i)) топологически различных способов, и построим еще один бесконечный граф H. Его вершины w_ij (i?1, 1 ? j ? m(i)) пусть соответствуют различным укладкам графов {G_i}, а его ребра соединяют те из вершин w_ij и w_kl, для которых k = i + 1 и плоская укладка, соответствующая w_kl «расширяется» (очевидным образом) до укладки, соответствующей w_ij. Легко видеть, что граф H связен и локально конечен, поэтому, как следует из леммы Кёнига, он содержит бесконечную в одну сторону простую цепь. А так как граф G является счетным, то эта бесконечная простая цепь и дает требуемую плоскую укладку графа G. //

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

В заключение этого небольшого отступления в область бесконечных графов дадим краткий обзор свойств бесконечных эйлеровых графов. Естественно назвать связный бесконечный граф (эйлеровым, если в нем существует бесконечная в обе стороны цепь, содержащая каждое ребро графа G; такая бесконечная цепь называется (двусторонней) эйлеровой цепью. Далее, назовем граф G полуэйлеровым, если в нем существует бесконечная (в одну или в обе стороны) цепь, содержащая каждое ребро графа G. Заметим, что эти определения требуют счетности графа G. В следующих теоремах даны условия, необходимые для того, чтобы бесконечный граф был эйлеровым или полуэйлеровым.

Теорема 8Е. Пусть G -- связный счетный граф, являющийся эйлеровым. Тогда (i) в графе G нет вершин нечетной степени; (ii) для каждого конечного подграфа Н графа G бесконечный граф Н (полученный удалением из G ребер графа Н) имеет не более двух бесконечных, связных компонент; (iii) если, кроме того, степень любой вершины из Н четна, то Н имеет ровно одну бесконечную связную компоненту.

Доказательство. (i) Предположим, что Р -- эйлерова цепь; тогда, рассуждая так же, как и в доказательстве теоремы 6В, получим, что степень любой вершины из G должна быть либо четной, либо бесконечной.

(ii) Разобьем цепь Р на три подцепи Р_, Р₀ и Р₊ так, что Р₀ -- конечная цепь, содержащая все ребра графа Н (и, быть может, другие ребра), а Р_- и Р₊ -- две бесконечные в одну сторону цепи. Тогда бесконечный граф /С, образованный ребрами цепей Р_ и Р₊(а также инцидентными им вершинами) имеет не более двух бесконечных компонент. Так как H получается из K присоединением лишь конечного множества ребер, то отсюда и следует нужный результат.

(iii) Пусть v и w -- начальная и конечная вершины цепи Р₀; v и w связаны в Н. Если v = w, то это очевидно; если v ?w, то, применяя следствие 6D к графу, полученному из Р₀ удалением ребер графа Н (по предположению в этом графе ровно две вершины, а именно v и w, имеют нечетные степени), получим требуемый результат. //

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

Теорема 8F. Пусть G -- связный счетный граф, являющийся полуэйлеровым, но не эйлеровым; тогда (i) G содержит либо не более одной вершины нечетной степени, либо не менее одной вершины бесконечной степени; (ii) для каждого конечного подграфа Н графа G бесконечный граф Н (описанный ранее) содержит ровно одну бесконечную компоненту. //

Теорема 8G. Пусть G-- связный счетный граф; G является эйлеровым графом тогда и только тогда, когда выполнены условия (i), (ii) и (iii) теоремы 8Е. Более того, G является полуэйлеровым тогда и только тогда, когда выполнены либо эти условия, либо условия (i) и (ii) теоремы 8F.