Множества. Комбинаторика. Отношения (стр. 22 )

ТЕОРЕМА. Ранг матрицы инцидентности графа, имеющего компонент связности и n вершин, равен n –.

Доказательство. Достаточно доказать, что ранг матрицы М связанного графа c n вершинами равен n-1. Так как в каждой строке матрицы по две единицы, то сумма всех столбцов по модулю 2 нулевая < n. Если один столбец матрицы удалить, то в некоторых строках останется по одной единице. Если предположить, что r(M) < n–1, то в столбцах должно быть чётное число единиц, а это противоречит только что сказанному. <

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

3.1.6 Геометрическая реализация графа

Рассмотрим в трёхмерном пространстве или на плоскости геометрические фигуры, состоящие из точек-вершин и кривых-дуг, каждая из которых соединяет некоторые пары вершин. Эти кривые не имеют общих точек, кроме вершин. Фигура Г называется геометрической реализацией графа G, если Г»G. Фигура Г на плоскости называется плоским графом.

ТЕОРЕМА. Каждый конечный граф имеет геометрическую реализацию в трёхмерном пространстве.

Доказательство. Пусть граф G содержит n вершин и h рёбер. Проведём через произвольную прямую h плоскостей. На прямой выберем n точек, которые сопоставим вершинам графа. Каждому ребру графа G сопоставим плоскость из данного пучка плоскостей и в ней проведём соответствующую дугу. <

Граф называется планарным, если существует его геометрическая реализация на плоскости. Введём операцию подразбиения ребра графа G. Пусть – произвольное ребро графа, . Операция подразбиения ребра заключается в построении нового графа с множеством вершин и множеством рёбер .

Граф G2 называется подразбиением графа G1, если он может быть получен из G1 путём применения конечного числа раз операции подразбиения рёбер. Графы G1 и G2 называются гомеоморфными, если существуют их изоморфные подразбиения.

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

3.1.7 Эйлерова характеристика

Эйлеровой характеристикой связного плоского графа G называется число

,

где n – число вершин графа G;

h – число его рёбер;

– число областей, на которые G делит плоскость, включая и бесконечную область. Например, для графа, изображённого на рис.1, имеем

Пусть даны два графа G и пусть – части, на которые дуги графа делят дугу графа G, определены аналогично. Граф G с рёбрами называется наложением графов G и .

Лемма 1. Пусть связный плоский граф получен из связного плоского графа G наложением ребра с несовпадающими концами. Тогда .

Доказательство. Очевидно, что пересечение графа G и ребра не пусто, иначе не мог бы быть связным. Пусть a,b – концы отрезка , а - точки пересечения и G.

Случай 1. Ни одна из точек не совпадает ни с одной из вершин графа G. Тогда число вершин в графе равно . Если на граф G наложить отрезок , то число рёбер увеличится на 2, а число областей не изменится (рис.2).

При последовательном наложении отрезков число рёбер увеличивается с каждым шагом на 2, а число областей на 1 (см. рис.3). При добавлении же отрезка число рёбер увеличивается на 1, а число областей не изменяется (см. рис.4), т. е. имеем:

.

Случай 2. Пусть некоторые из точек являются вершинами графа G. И пусть число таких точек k . Тогда

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

Лемма 2. Пусть связной граф G получен наложением графа на граф G. Тогда .

Доказательство. Проведём индукцию по числу рёбер h графа . Лемма 1 даёт базис индукции. Предположим, что утверждение верно для графа с числом рёбер h. Рассмотрим теперь граф с h+1 ребром.

Случай 1. В графе найдутся два ребра, которые пересекаются с рёбрами графа G. Удаляя ребро графа , не являющееся перешейком, получим граф с h рёбрами такой, что наложение графа на граф G связно. По индукционному предположению .

Добавляя удалённое ребро по лемме 1, получим .

Случай 2. Граф пересекается с графом G по одному ребру . Если граф не дерево, то в нём есть цикл. Удаляя ребро этого цикла, не совпадающее с и аналогично случаю 1, получим . Если же – дерево, то в нем имеются по крайней мере два концевых ребра тупика. Удаляя не совпадающий с тупик, с помощью тех же рассуждений получим, что эйлеровы характеристики графов G и совпадают.