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

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

Текст из файла

Методы дискретной оптимизацииЧасть 1. Комбинаторная оптимизацияНеобходимые элементы теории графовОпределениеV – произвольное счетное множество, E – произвольное подмножество егодвухэлементых подмножеств.Пара G = (V, E) называется графом (неориентированным графом).1 / 23Матрица смежности (n, m)-мультиграфа (мультиорграфа) GA = (aij ), i, j ∈ Nn , aij =0, (i, j) ∈/ E ∀j = 1, 2, ..., n,l, ∃K ⊆ Nn , |K| = l : (i, jk ) = (i, j) ∈ E ∀k ∈ K.Матрица инцидентности (n, m)-мультиграфа GB = (bij ), i ∈ Nn , j ∈ Nm , bij =0, i ∈/ ej ,1, i ∈ ejМатрица инцидентности (n, m)-мультиорграфа GD = (dij ), i ∈ Nn , j ∈ Nm , dij =0, i ∈/ ej ,1, ej = (i, k), k ∈ Nn ,−1, ej = (k, i), k ∈ NnСтепень исхода вершины i – число выходящих из вершины дуг: δ + (i).Степень захода вершины i – число входящих в вершину дуг: δ − (i).Степень вершины i: δ + (i) + δ − (i) = δ(i). Матрица степеней δмультиорграфа G – диагональная матрица, на главной диагонали которойнаходятся степени соответствующих вершин.2 / 23Теорема 1.Если G – (n, m)-мультиграф, n > 1, m > 0 с матрицей смежности A,матрицей инцидентности B и матрицей степеней δ, тоB · B T = A + δ.Доказательство.Ti 6= j ⇒ (B · B ) =mXbik bjk , bik , bjk ∈ {0, 1}k=1bik bjk = 1 ⇔ 1 = bik = bjk ⇔ i, j ∈ ek ⇔ ek = (i, j)Следовательно, суммирование производится по тем ребрам k, которыесоставляют пару (i, j).

При суммировании получается значение l какчисло параллельных ребер, связывающих i и j, т.е. значение aij .i = j ⇒ bik bjk = b2ik = 1 ⇔ bik = 1 ⇔ i ∈ ekСуммируя по всем индексам k таким, что вершина i инцидентна ребру k,получаем степень вершины i: (BB T )ii = δ(i). Теорема доказана.3 / 23Пример:11B=⇒ B T = (11), BB T =1111=0110+1001Замечание. Задавая каждому из ребер множества E ориентацию,получим из мультиграфа мультиорграф, при этом матрица смежностибудет определяться поэлементно как0, (i, j) ∈/ E,āij =1, (i, j) ∈ EОтсюда следует, что при любом выборе ориентации ребер матрицы A и Āсвязаны равенством A = Ā + ĀT .

Для ориентированного случаясправедливаТеорема 2.Пусть G – (n, m)-мультиорграф, n > 1, m > 0 с матрицей смежности Ā,матрицей инцидентности D, матрицей степеней δ. ТогдаD · DT = δ − Ā − ĀT4 / 23PmДоказательство Теоремы 2. (D · DT )ij = k=1 dik djk . Как и вдоказательстве теоремы 1, рассмотрим случаи: ek = (i, p), p ∈ V,⇒i=j ek = (j, q), q ∈ V1) i 6= j ⇒ dik · djk = 1 ⇔ ek = (p, i), p ∈ V,⇒i=jek = (q, j), q ∈ V ek = (i, p), p ∈ V,⇒ ek = (i, j) ek = (q, j), q ∈ V2) dik · djk = −1 ⇔ ⇒ek = (p, i), p ∈ V,⇒ ek = (j, i)ek = (j, q), q ∈ V⇒mPPdik · djk =k=1(−1)k:ek =(i,j)∨ek =(j,i)2i = j ⇒ dik · djk = (dik ) = 1 ⇔ dik = ±1 ⇔⇒mXk=1dik · djk =X∃p ∈ Nn : ek = (i, p)⇒∃q ∈ Nn : ek = (q, i)(+1) = δ(i)k:ek =(i,p)∨ek =(q,i)5 / 23Суммирование по всем k в случае несовпадения i и j дает (сотрицательным знаком) число дуг, связывающих эти вершины, т.е.−(Ā + ĀT )ij .Суммирование по всем k в случае совпадения i и j дает число дуг,инцидентных вершине i, т.е.

δ(i). Это окончательно доказывает теорему.Замечание. Правая часть равенства в утверждении теоремы 2 не зависитот выбора ориентации ребер графа, если мультиорграф получен измультиграфа назначением направления ребер. При этом Ā + ĀT = A, гдеA – матрица инцидентности исходного мультиграфа.6 / 23Теоремы 1 и 2 касались представления матриц B · B T и D · DT длямультиграфа и мультиорграфа соответственно. Рассмотрим представлениепроизведения B · B T .

Для этой цели введем следующее понятие.ОпределениеПусть G – (n, m)-мультиграф. Реберным мультиграфом мультиграфа Gназывается мультиграф L(G), у которого в качестве множества вершинвыступают ребра исходного мультиграфа G, т.е. элементы множества E, амножество ребер строится следующим образом:Вершины ei , ej мультиграфа L(G) соединены ребром тогда и толькотогда, когда ребра ei , ej мультиграфа G смежны, т.е. имеют общуювершину.Если ребра ei , ej мультиграфа G не параллельны, то вершины ei , ejмультиграфа L(G) соединены единственным ребром.Если ребра ei , ej мультиграфа G параллельны, то вершины ei , ejмультиграфа L(G) соединены парой параллельных ребер.7 / 23Теорема 3.Для матрицы инцидентности B мультиграфа G справедливо равенствоB T · B = AL(G) + 2 · Im ,где AL(G) , Im – соответственно матрица смежности мультиграфа L(G) иединичная матрица порядка m.Доказательство.

(B T · B)ij = (bi , bj ) =nPbli · blj , где bi – i–ый столбецl=1матрицы B, bli ∈ {0, 1}, при этом в каждом столбце матрицы B ровно 2единицы, остальные элементы нули. Рассмотрим случаи:nPb2li = 2, следовательно, на главной диагонали матрицыi=j⇒l=1стоят двойки: (B T · B)ii = 2, i = 1, 2, ..., n.i 6= j, при этом ребра ei , ej в мультиграфе G смежны, но непараллельны, т.е. в L(G) вершины ei , ej соединены единственнымребром. Тогдаei = (k, p) ⇒ bki = 1,∃!k, ∃(p, q), p 6= q :⇒ ∃!k : bki · bkj = 1.ej = (k, q) ⇒ bkj = 1TСледовательно, в этом случае (B · B)ij = 1.8 / 23i 6= j, при этом ребра ei , ej в мультиграфе G параллельны, т.е.

в L(G)вершины ei , ej соединены парой параллельных ребер. Тогдаei = (k1 , k2 ) ⇒ bk1 i = 1 = bk2 i ,⇒∃!(k1 , k2 ) :ej = (k1 , k2 ) ⇒ bk1 j = 1 = bk2 j⇒ ∃!(k1 , k2 ) :bk1 i · bk1 j = 1Следовательно, в этом случае (B T · B)ij = 2.i 6= j, при этом ребра ei , ej в мультиграфе G не смежны, т.е. в L(G)bki = 0,вершины ei , ej не соединены ребром.

Тогда ∀k = 1, 2, ..., n :bkj = 0Следовательно, в этом случае (B T · B)ij = 0. Совокупность выводов врассмотренных случаях доказывает теорему.9 / 23ОпределениеМатрица называется вполне унимодулярной, если определитель любой ееквадратной подматрицы равен 0 или ±1.Теорема 4.Если D = D(Ḡ) матрица инцидентности мультиорграфа Ḡ, то D – вполнеунимодулярна.Доказательство. Рассмотрим произвольную квадратную подматрицуразмера k. Если k = 1, то утверждение справедливо по определениюматрицы инцидентности. Если предположить справедливость дляквадратных подматриц размера не более k, то при переходе к размерностиk + 1 возможны случаи:10 / 23В квадратной подматрице размера k + 1 cуществует нулевой столбец.В таком случае утверждение тривиально.В квадратной подматрице размера k + 1 каждый столбец содержиткак -1, так и +1.

Прибавляя к первой строке остальные строки,получим равенство нулю определителя этой подматрицы.В квадратной подматрице размера k + 1 существует столбец,содержащий только один ненулевой элемент, т.е. 1 или -1. Разлагаяопределитель по данному столбцу, делаем индуктивный переход изавершаем доказательство теоремы.ОпределениеДеревом называется связный ациклический граф, содержащий не менеедвух вершин.

Число вершин в дереве на 1 превосходит числа ребер в нем.11 / 23Теорема 5.Если D = D(Ḡ) – n-вершинное ориентированное дерево (n > 1), то всякаяквадратная подматрица порядка n − 1 матрицы D невырождена.Доказательство. Поскольку рассматривается дерево, то число строк вматрице равно n, число столбцов – n − 1. Поэтому квадратная подматрицапорядка n − 1 может возникнуть лишь при вычеркивании одной из строкматрицыD. Применяя индукцию по n, рассмотрим случай n = 2, тогдаT..(1.−1), в обоих случаях утверждение очевидно.D=..

T(−1.1)Предположим, что утверждение справедливо для n = 1, 2, . . . , k ирассмотрим n = k + 1. Вычеркнем произвольную строку с номером i. Этойстроке соответствует вершина i степени l. Перенумеруем строки истолбцы так, чтобы строка с номером i оказалась на месте первой и приэтом первые l ее элементов оказались отличными от 0. Эта операциясоответствует переименованию вершин и ребер в графе. Далее, умножимпри необходимости столбцы из числа первых l, чтобы первые l элементовпервого столбца оказались равными +1.

Эта операция, возможно, изменитзнак определителя подматрицы.12 / 23Таким образом можно считать, что матрица D имеет вид111 ... 1 0 ... 0 −1 000 0 −1 00 ... ... ... ... ...D= 000 ... −1 000 ... 0 ... ... ... ... ...000 ... 0У правого дерева матрица инцидентности, как у исходного, тольконумерация строк и столбцов начинается с 2.

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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