Булатов Константин Станиславович

Казахский Национальный Университет имени Аль-Фараби

Безразмерные графы

Безразмерным графом называется пара (V(G), E(G)), где V(G) – бесконечное множество элементов, называемых вершинами,

рис. 1

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

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

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

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

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

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

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

Пусть G – связный локально конечный бесконечный граф; тогда для любой его вершины v существует бесконечная в одну сторону простая цепь с начальной вершиной v.

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

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

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

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

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

Теорема 2. Пусть G – связный счетный граф, являющийся эйлеровым. Тогда в графе G нет вершин нечетной степени; для каждого конечного подграфа N графа G безразмерный граф Ñ ( полученный удалением из G ребер графа N) имеет не более двух бесконечных связных компонент; если, кроме того, степень любой вершины из N четна, то Ñ имеет ровно одну бесконечную связную компоненту.

Доказательство. Преположим, что Р – эйлерова цепь; тогда степень любой вершины из G должна быть либо четной, либо бесконечной.

Разобьем цепь P на три подцепи P_- , P₀, P₊ так , что P₀ – конечная цепь, содержащая все ребра графа N (и, быть может, другие ребра), а P_- и P₊ - две бесконечные в одну сторону цепи. Тогда бесконечный граф К, образованный ребрами цепей P_- и P₊ (а также инцидентными им вершинами), имеет не более двух бесконечных компонент. Так как Ñ получается из К присоединением лишь конечного множества ребер, то отсюда и следут нужный результат.

Пусть v и w – начальная и конечная вершины цепи P₀ удалением ребер N (по предположению в этом графе ровно две вершины, а именно v и w, имеют нечетные степени), получим требуемый результат.

Теорема 3. Пусть G – связный счетный граф, является полуэйлеровым; тогда G содержит либо не более одной вершины нечетной степени, либо не менее одной вершины бесконечной степени; для каждого конечного подграфа N графа G бесконечный граф Ñ содержит ровно одну бесконечную компоненту.

Теорема 4.Пусть G – связный счетный граф; G является эйлеровым графом, тогда и только тогда, когда выполнены теоремы2. Более того, G является полуэйлеровым тогда и только тогда, когда выполнены эти условия, либо условия теоремы 3.