В.А. Носов - Комбинаторика и теория графов (1023552), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

i p  называется определитель подматрицы, поj2 ... j p лученный из А строками i1, … , ip и столбцами j1, … , jp .Факт 5. Миноры матрицы инциденций А равны + 1, - 1 или 0.♦ По определению, каждый столбец матрицы А имеет один элемент +1 и один i1-1, остальные элементы 0. Рассмотрим произвольную подматрицу A j1i 2 ... i p .j2 ... j p Если имеется столбец из нулей, то ее определитель равен нулю. Если имеется столбец,содержащий один ненулевой элемент (+ 1 или - 1), то утверждение следует по индукции,т.к.

оно верно для размера p = 1.Если все столбцы содержат оба элемента + 1 и - 1, то суммированием всех строкполучаем нулевую строку и, значит, определитель равен нулю.iФакт 6. Минор A 1 j1i 2 ... i n −1  матрицы инциденций А ориентированногоj2 ... j n −1 графа G(V, E) отличен от нуля (т.е. равен + 1 или - 1) тогда и только тогда, когда соот~ветствующий скелетный граф G реберного подграфа, определенного E′ = { e j1 ,K , e jn−1 }является деревом.94~♦ Пусть G не является деревом.

Тогда, поскольку число ребер равно~n - 1, то по теореме 1 G должен содержать цикл. Если взять сумму столбцов, которые~соответствуют ребрам простого цикла в G , то получим нулевой столбец. Минор в этом~~случае равен нулю. Обратно, пусть G дерево. Если n = 2, то G состоит из одного ребра.Соответствующая матрица А имеет размер 2×1, а ее миноры равны + 1 и - 1. Предполо~жим, что если G дерево с k - 1 вершинами, то соответствующий минор ненулевой, и~пусть G имеет k вершин. Пусть E′ ={ e j1 , e j2 ,K , e jk−1 }- соответствующий ему наборребер, а {v i1 , v i 2 ,K , v i k−1 , v i k } - набор вершин.

Поскольку каждое дерево имеет по крайней мере 2 конечные вершины, то среди k - 1 вершин v i1 , v i 2 ,K , v i k−1 имеется одна конечная, скажем vt. Разложим минор по строке t. Ясно, что эта строка содержит единственный, отличный от нуля элемент (+ 1 или - 1) и k - 2 нулей. Значит, с точностью до~~знака, минор равен минору, который соответствует дереву G ′, полученному из G удалением вершины vt и всех ребер, смежных с ней. По индуктивному предположениюданный минор отличен от нуля.

♦Нам понадобится известная формула Бинэ-Коши из линейной алгебры.Пусть А - (n × m)- матрица и B - (m × n)- матрица, где n ≤ m. Тогда справедливоследующее тождествоdet(A⋅B) =1A1≤ j 1< j2 <K< jn ≤ m  j12∑j2... n   j1 B... j n   1j22... j n ... n Теперь мы в состоянии доказать теорему Кирхгофа.Теорема 7. Пусть М - ((n - 1) × m)-матрица, полученная из матрицы инциденцийА ориентированного графа G(V, E) вычеркиванием некоторой строки.

Тогда det(М⋅М′)равен числу остовных деревьев соответствующего скелетного графа. (Здесь М′ - транспонированная матрица М).По формуле Бинэ-Коши имеемdet(М⋅М′) =1M j11≤ j 1< j2 <K< jn−1 ≤ m∑ 1= M∑1≤ j 1< j2 <K< jn−1 ≤ m   j12j22j2... n − 1  j1 M′... j n−1   1... n − 1 ... j n−1  j22... j n−1 =... n − 1295поскольку1M j1... n − 1 j1 = M ′j2 ... j n −1 12j2 ... j n −1 2 ... n − 1Далее, на основе факта 6 скелетный граф реберного подграфа, определенногоребрами E′ = { e j 1 , e j2 ,K , e j n − 1 } является остовным деревом тогда и только тогда, когда 1M   j12j22...

n − 1   = 1. Суммирование распространено по всем Е′ и каждое Е′ по... j n −1  является точно один раз. Каждое Е′, соответствующее дереву, дает 1, не соответствующее дереву, дает 0. ♦Если дан произвольный неориентированный граф G(V, E), то нет необходимости приписывать ребрам ориентацию, определять матрицы М и М′ и перемножать их.Можно вычислить М⋅М′ непосредственно, исходя из графа G(V, E). ПустьV = {v1, v2, ... , vn}. Пусть вычеркиваемая строка в матрице инциденций А соответствуетvn . Нетрудно заметить, что элемент (М⋅М′)ii - это степень вершины vi , а элемент (М⋅М′)ijпри i ≠ j- это число ребер, соединяющих vi с vj , взятое со знаком минус.Пример. Рассмотрим граф G:Тогда 2 −1 0 М⋅М′ =  −1 2 −1 0 −1 2 и значит det(М⋅М′) = 4.Значительный интерес имеет случай полного неориентированного графа на nвершинах. Число покрывающих деревьев такого графа найдено Кэли.Теорема 8.

Число остовных деревьев полного неориентированного графа на nвершинах равно nn-2 .♦ Матрица М⋅М′ в этом случае имеет вид:96 n − 1 −1 −1 n − 1−1 −1... −1 ... −1 ...... n − 1Отнимем первый столбец от остальных и получим n − 1 −nn −10 −1... − n... 0 ...... n Теперь прибавим все строки к первой строке, получаем 1 0 ...

0 −1 n ... 0...  −1 0 ... nЯсно, что определитель последней матрицы есть nn-2. ♦4. Вернемся еще раз к вопросу о порождении подстановок транспозициями, рассмотренному в главе I. Пусть Sn - группа всех подстановок степени n, Тn - множествовсех транспозиций. Напомним, что некоторое множество элементов М из группы G является системой образующих для G или порождает G, если множество 〈М〉 произведенийс конечным числом сомножителей элементов из М, взятых с положительными и отрицательными степенями, совпадают с группой G.Поставим теперь вопрос, когда произвольное множество транспозиций Rn из Tnявляется системой образующих для Sn? Пусть Rn = {t1, ...

, tr} . Поставим множеству Rn всоответствие граф Г(Rn), называемый графом Пойа и определяемый следующим образом:Вершинами графа Г(Rn) являются элементы 1, 2, … , n. Каждой ti ∈ Rn, еслиti = (p, q) в Г(Rn) соответствует ребро, инцидентное вершинам p и q. Может быть доказанаТеорема 9. Множество транспозиций Rn = {t1, … , tr}, (r ≥ n - 1) тогда и толькотогда порождает симметрическую группу Sn, когда соответствующий граф Пойа Г(Rn)связен.Следствие 1.

Множество из n - 1 транспозиций Rn порождает Sn тогда и толькотогда, когда соответствующий граф Пойа Г(Rn) является деревом.97Следствие 2. Число систем образующих симметрической группы Sn, состоящихиз n - 1 транспозиций, равно nn-2.98§ 6. Планарные графы1. В некоторых случаях требуется, чтобы изображение графа удовлетворяло определенным условиям. Будем изображать графы так, что его вершинам соответствуютточки плоскости, а ребрам непрерывные, спрямляемые линии без самопересечений, причем ребра не должны иметь общих точек кроме инцидентных им вершин.Такое изображение будем называть плоским графом, а граф, изоморфный плоскому, назовем планарным. Легко указываются примеры планарных графов. Например,K2, 3, K4.

В то же время не удается установить планарность графов K3, 3, K5. Ниже будетдоказано, что графы K3, 3, K5 не являются планарными. Отметим, что справедлив факт,приводимый без доказательства.Теорема 1. Почти все графы не являются планарными.Рассмотрим сначала укладку графов в действительном трехмерном пространстве R3.Теорема 2. Каждый граф укладывается в R3. Все вершины произвольного графа G помещаем в различных точках координатной оси х. Рассмотрим пучок плоскостей, проходящих через ось х, и зафиксируем |E|различных таких плоскостей.

Теперь каждое ребро (u, v) изобразим полуокружностью,проходящей в соответствующей плоскости через вершины u, v. Ясно, что различныеребра не будут пересекаться кроме как в общих вершинах. 2. Пусть G – плоский граф. Определим отношение эквивалентности на множестве точек плоскости: объявим две точки u и v эквивалентными, если их можно соединитьнепрерывной, спрямляемой, без самопересечений кривой, не пересекающей ребра графа.Легко проверить данное отношение есть отношение эквивалентности.

Поэтомувся плоскость разбивается на классы эквивалентных точек. Класс эквивалентных точекплоскости называется гранью плоского графа.Пример. Приведенный ниже граф имеет 4 грани.314299Пусть G = (V, E) – плоский граф, такой, что n = |V|, m = |E|, f – число граней.Теорема 3 (Эйлер). Для всякого плоского связного графа G справедливо соотношениеn – m+f = 2 Доказываем индукцией по m при фиксированном n. Поскольку G связен, тоm ≥ n – 1.

Пусть m = n – 1. В силу связности G он является деревом. Значит в G нет циклов и потому f = 1 и теорема справедлива для этого случая.Пусть она справедлива для всех m, таких, что n – 1 ≤ m < m1. Докажем ее для m1.Пусть G – связный граф, плоский с n вершинами и m1 ребрами, имеющий f граней.Поскольку m1 > n – 1, то G содержит цикл С. Пусть е – ребро, принадлежащеециклу. Тогда е принадлежит разным граням. Удалим ребро е из графа G. Тогда эти двеграни сливаются в одну, при этом граф G11 полученный из G удалением е, связен, поскольку е лежит на цикле.Граф G1 имеет n вершин, m1 – 1 ребер, f – 1 граней. По предположению индукции справедливо соотношениеn – (m1 – 1)+(f – 1) = 2Отсюда n – m1+f = 2, что и доказывает утверждение. Следовательно, число граней планарного графа определяется соотношениемf = m – n+23.

Характеристики

Список файлов книги