Лекция 1-2. Комбинаторная оптимизация. Необходимые элементы теории графов (1162198), страница 2

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

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

По индуктивномупредположению последняя матрица после вычеркивания первой строкидает невырожденную матрицу. Последняя совпадает с матрицей, котораяполучается при вычеркивании первого столбца и первых двух строкматрицы D, что доказывает теорему.13 / 2314 / 23Теорема 6.Если Ḡ – (n, m)-мультиорграф без изолированных вершин, имеющий kкомпонент связности, то ранг его матрицы инцидентности равен n − k.Доказательство. Путем переименования вершин и ребер в графе, чтосоответствует перестановкам строк и столбцов, матрицу инцидентности Dможно привести к блочно-диагональному виду, на главной диагоналиматрицы D будут находиться матрицы Di , номер i соответствует i–ойкомпоненте связности, i = 1, 2, .

. . k. Каждая из компонент – дерево, поусловию содержащее хотя бы одну дугу, в силу связности каждой изкомпонент, для каждого i существует остовное дерево, содержащее всевершины компоненты. По теореме 5 ранг матрицы инцидентности неменее ni − 1, т.е. на 1 менее числа вершин в i-ой компоненте. С другойстороны, в каждом столбце матрицы Di ровно два ненулевых элемента: 1и -1, поэтому сумма строк Di равна 0, следовательно, ранг Di не болееni − 1. Следовательно, на главной диагонали блочно-диагональнойматрицы D находятся матрицы Di , ранг каждой из матриц Di равенni − 1.

Ранг всей матрицы D в таком случае равен n − k. Теорема доказана.15 / 23Пусть как и ранее, Ḡ – связный (n, m)-мультиорграф с матрицейинцидентности D. Обозначим через D(j1 , j2 , ..., jn−1 ) подматрицу сномерами столбцов j1 , j2 , ..., jn−1 матрицы D :. . .D(j1 , j2 , ..., jn−1 ) = (dj1 ..dj2 .......djn−1 ).Теорема 7.Ранг подматрицы D(j1 , j2 , ..., jn−1 ) равен n − 1 тогда и только тогда, когдаребра ejl , l = 1, 2, ..., n − 1 порождают дерево.Доказательство. Необходимость следует из теоремы 6.

Достаточностьследует из того факта, что если мультиорграф, в данном случаепорожденный указанными ребрами, связен, но деревом не является, то онсодержит циклы. Процесс удаления дуг из циклов без нарушениясвязности приводит порожденный граф к дереву с не более n − 2 дугами,что противоречит связности. Следовательно, в данном мультиорграфе покрайней мере 2 компоненты связности и по теореме 6 ранг матрицы непревосходит n − 2.

Теорема доказана.16 / 23ОпределениеЧисло остовов, т.е. остовных деревьев в графе называется его сложностью(древесной сложностью графа) и обозначается как k(G).Задание ориентации ребер в графе G не меняет его древесной сложности.Теорема 8.Пусть G – (n, m)-мультиграф, n > 1, m > 0, Ḡ – мультиорграф,полученный из G заданием ориентации ребер, D – матрица инцидентностиḠ, D(i; j1 , j2 , ..., jn−1 ) – ее квадратная (n − 1) · (n − 1) подматрица состолбцами j1 , j2 , ..., jn−1 и строками матрицы D, кроме i-ой.

ТогдаXk(G) =| det D(i;j1 , j2 , ..., jn−1 )|1≤j1 <j2 <...<jn−1 ≤m17 / 23Доказательство Теоремы 8. По теореме 7 матрица D(i; j1 , j2 , ..., jn−1 )невырождена в том и только в том случае, когда дуги ej1 , ej2 , ..., ejn−1порождают дерево. Следовательно, | det D(i; j1 , j2 , ..., jn−1 )| = 1 тогда итолько тогда, когда дуги ej1 , ej2 , ..., ejn−1 порождают дерево.Каждому дереву, таким образом, однозначно соответствует такой набориндексов j1 , j2 , ..., jn−1 , для которого | det D(i; j1 , j2 , ..., jn−1 )| = 1.

Отсюдаи из условия det D(i; j1 , j2 , ..., jn−1 ) ∈ {0, ±1} сумма по всем возможнымнаборам дает k(G). Теорема доказана.18 / 23Матричная теорема о древесной сложности (т. Кирхгофа,сформулирована в 1847 г., доказана в 1940 г.)Теорема 9 (Кирхгофа)Пусть G –связный (n, m) – мультиграф с матрицей смежности A иматрицей степеней δ. Тогда число остовов в G равно алгебраическомудополнению любого из элементов матрицы δ − A.Доказательство. Зададим направление ребер G, сделав их дугами,получим связный мультиорграф с m > n − 2 дугами (в силу связности G).В его матрице инцидентности D удалим последнюю строку с номером n,полученную матрицу обозначим Dn .X1, 2, ..., n − 1Tdet(Dn · Dn ) =det Dn·j1 , j2 , ..., jn−11≤j1 <j2 <...<jn−1 ≤m· det DnT=2Xj1 , j2 , ..., jn−11, 2, ..., n − 1=det Dn=1, 2, ..., n − 1j1 , j2 , ..., jn−11≤j1 <...<jn−1 ≤mX|det D(n̄, j1 , j2 , ..., jn−1 )|1≤j1 <j2 <...<jn−1 ≤m19 / 23Последнее выражение равно k(G) по теореме о представлении древеснойсложности.

Для матрицыd1D =  ...  ⇒ Dn · DnT = {(di , dj )}, i, j = 1, 2, ..., n − 1dnОтсюда det(Dn · DnT ) = k(G) = (D · DT )n,n = (δ − A)n,n . Здесь через Ci,jобозначено алгебраическое дополнение элемента (i, j) матрицы C. Заменанумерации строк приводит к тому, что величина k(G) равна (δ − A)i,i , т.е.алгебраическому дополнению элемента (i, i) матрицы δ − A. Длязавершения доказательства осталось показать, что при любыхi, j : i ≤ i 6= j ≤ n имеет место равенство (δ − A)i,j = det(Di DiT ). Докажемсоотношениеdet(Di · Dj ) = (−1)j−i det(Di · Di ), i < j.20 / 23Для этого в Dj прибавим все строки (т.е. все кроме j-ой, вычеркнутой изисходной матрицы) к строке с номером i. Тогда вместо строки di получимстроку −dj , посколькусумма строк матрицы D равна 0. В результатеj1 , j2 , ..., jn−1Tвеличина det Djне изменится.

Cделаем j − i − 11, 2, ..., n − 1последовательных замен в матрице Dj :......... di = −dj di+1di+1di+1di+2 →  di = −dj  → ... → ......... dj−1 dj−1 di = −dj dj+1dj+1dj+1В результате получим матрицу, совпадающую с Di всюду кроме строки j,которая равна −dj .21 / 23В результате таких преобразований каждый множитель видаj1 , j2 , ..., jn−1Tdet Dj1, 2, ....n − 1будет умножен на коэффициент (−1)j−i . Отсюда следует, чтоdet(Di · DjT ) = (−1)j−i det(Di · DiT ) = (−1)j+i · (δ − A)i,i = (−1)j+i · k(G)С другой стороны,(δ − A)i,j = (−1)i+j det(Di · DjT ) ⇒ (δ − A)i,j = k(G)Полученное равенство доказывает теорему.22 / 23Теорема 10 (Кэли).Пусть G = Kn – полный n-граф.

Число остовов в нем равно nn−2 .Доказательство.δ−A=n−1−1−1−1n−1−1−1−1−1−1−1−1n−1...−1−1.........−1−1−1... n − 1...−1−1−1−1−1n−1По теореме 9 величина k(G) равна алгебраическому дополнению любогоэлемента этой матрицы. Возьмем в качестве такого элемента (n, n). Тогда23 / 23(δ − A)(nn)= = n−1−1−1n−1......−1−111...10 ... 0n ...

0... ... ...0 ... n...−1...−1......... n − 1 = nn−2 = 1−1...1 n − 1 ............1−1...−1−1...n−1=На первом шаге все столбцы прибавили к 1–му. На втором шаге первыйстолбец прибавлен к каждому из других. Теорема доказана.24 / 23.

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

Список файлов лекций