Диссертация (1145311), страница 25
Текст из файла (страница 25)
Столбцы матрицы B, соответствующие наименьшему реберному покрытию M , линейно независимы над GF (2).Доказательство. Очевидно, что наименьшее реберное покрытие не содержит никакого пути с четырьмя или более вершинами. Кроме того, ясно,что любые два столбца матрицы B линейно независимы. Предположим.
чтостолбцы B, соответствующие M , линейно зависимы. Это значит, что уравнениеBX = 0 имеет ненулевое решение. Цикл (или сумма циклов), соответствующийэтому решению, содержит три или более ребер. Это противоречит тому, что Mявляется наименьшим покрытием и доказывает теорему.179Обозначим через M подматрицу матрицы B, состоящую из столбцов, соответствующих ребрам, которые входят в наибольшее паросочетание M . Обозначим через P подматрицу матрицы B, состоящую из столбцов, соответствующих ребрам, которые входят в наименьшее реберное покрытие P .
Очевидно,что каждая строка M содержит не более одного ненулевого элемента (единицы). Также каждая строка P содержит не менее одного ненулевого элемента.Кроме того, для любого столбца B` матрицы B, не входящего в M, существуетстолбец Bi в M такой, что скалярное произведение (B` , Bi ) равно 1. Также длякаждого столбца B` матрицы B, не входящего в P, существуют два столбца Bi1и Bi2 из P, такие что скалярные произведения (B` , Bi1 ) = (B` , Bi2 ) = 1.Приведем доказательство следующей теоремы [96], использующее методылинейной алгебры.Теорема 64. Для любого нетривиального связного графа G выполняется равенствоα(G) + β(G) = n.Доказательство.
Сначала рассмотрим наибольшее паросочетание графа G. Пусть подматрица M содержит столбцы B1 , B2 , . . . , Bα , соответствующие ребрам, входящим в это паросочетание. Каждый такой столбец содержитровно две единицы. Следовательно, M содержит 2α единиц. Очевидно, чтобыполучить реберное покрытие, мы должны добавить к этим ребрам n−2α ребер.И это покрытие не обязательно будет наименьшим.
Таким образом, получаем,что β ≤ α + (n − 2α), и α + β ≤ n.Теперь рассмотрим наименьшее реберное покрытие графа G, содержащееβ ребер, и соответствующую подматрицу P, состоящую из столбцов матрицыB. Выберем строки P, содержащие более одной единицы. Разобьем эти строкиP на группы таким образом, что i-я группа (i ∈ {1, 2, . . . , n}) содержит всестолбцы, у которых в i-й строке стоят единицы. Каждый оставшийся столбецпоместим в свою группу.
Предположим, что всего имеем γ групп. Ясно, что180β + γ = n. В самом деле, каждый столбец принадлежит только одной группе,каждая строка содержит по крайней мере одну единицу, и в каждой группе число единиц в различных строках больше числа столбцов в этой группе. Возьмемиз каждой группы по одному столбцу. Составим из всех этих столбцов матрицу M.
Очевидно, что эта матрица соответствует паросочетанию, поскольку вкаждой ее строке содержится одна и только одна единица. Это паросочетаниеможет не быть наибольшим. В матрице M всего γ столбцов, и γ ≤ α. Получаемβ + γ = n. Таким образом, β + α ≥ n.Следующая теорема [142] связывает наименьшее реберное покрытие и наибольшее паросочетание. Она также может быть доказана с помощью линейноалгебраического подхода.Теорема 65.
Для связного графа G с n вершинами каждое наименьшее реберное покрытие содержит наибольшее паросочетание, и каждое наибольшеепаросочетание содержит наименьшее покрытие.3.4. Распознавание реберного графаЗдесь мы рассмотрим задачу распознавания реберного графа и построенияего корневого графа.Определение 32. Реберным графом обыкновенного графа H называется графG = L(H) такой, что каждая вершина L(H) соответствует ребру H, и двевершины L(H) смежны тогда и только тогда, когда соответствующие ребраH имеют общую вершину.
Граф H называется корневым графом графа G.3.4.1. Необходимые сведения из теории графовБудем предполагать, что данный граф не является полным графом на трехвершинах (в этом исключительном случае существуют два неизоморфных кор-181невых графа). Во всех остальных случаях, если реберные графы двух связныхграфов изоморфны, то и их корневые графы также изоморфны [177].Известны три алгоритма, позволяющих определить, является ли данныйграф реберным графом какого-либо графа [78, 124, 155]. Недавно был предложен новый эффективный алгоритм распознавания реберного графа [127].
Рассмотрим линейно-алгебраический подход к данной задаче. Предлагаемый алгоритм основан на следующей теореме [96]:Теорема 66. Граф G является реберным графом тогда и только тогда, когдаребра G могут быть разбиты на клики таким образом, чтобы каждая вершина принадлежала в точности двум таким кликам, и никакие две вершиныG не находились в двух одинаковых кликах.Замечание 34. Заметим, что клика может состоять только из одной вершины. Очевидно, в такой клике нет ребер.Пусть имеется указанное разбиение на клики. Тогда корневой граф H, длякоторого граф G является реберным графом, может быть построен следующимобразом.
Каждой клике сопоставляется вершина графа H, и каждое ребро Hсопоставляется каждой вершине графа G, так что концы ребра принадлежатдвум кликам, содержащим данную вершину G.Задача распознавания реберного графа связана с задачей факторизацииматрицы. В самом деле, пусть D — матрица смежности данного графа G с mвершинами. Справедлива следующая теорема:Теорема 67. Граф G является реберным графом некоторого графа H тогдаи только тогда, когда существует (0, 1)-матрица B, содержащая в каждомсвоем столбце ровно две единицы, такая, что D = B T B. Более того, даннаяматрица B является матрицей инцидентности графа H.182Доказательство. Необходимость. По теореме 66, мы можем разбить всеребра графа G на n клик C1 , C2 , .
. . , Cn . Каждой клике Ck поставим в соответствие столбец Bk ∈ Gm такой что элемент этого столбца, стоящий в i-й строке,равен 1 тогда и только тогда, когда i-я вершина графа принадлежит клике Ck .Рассмотрим матрицу B T = (B1 , B2 , . . . , Bn ) размерности m × n.Так как каждая вершина G принадлежит в точности двум кликам, толюбой столбец Bi (i ∈ {1, 2, . . .
, m}) матрицы B содержит ровно две единицы.Так как любые две различные клики имеют не более одной общей вершины, всестолбцы матрицы B различны. Таким образом, матрицу B можно рассматривать как матрицу инцидентности некоторого графа H с n вершинами, которыйи будет являться корневым графом графа G.
В самом деле, k-я строка матрицыB соответствует клике Ck . Вершины с номерами j и k графа G смежны тогда итолько тогда, когда скалярное произведение соответствующих строк матрицыB равно 1.Достаточность. Пусть B — матрица инцидентности данного графа H, а D— матрица смежности соответствующего реберного графа G = L(H). Известносоотношение D = B T B [148].
Оно может быть доказано непосредственным вычислением правой части равенства.Следствие 20. Пусть граф G с матрицей смежности D является реберным графом некоторого графа H с матрицей инцидентности B, D = B T B.Тогда существует разбиение строк матрицы B T на группы так, что соответствующие подграфы графа G = L(H) с матрицей D являются кликами,удовлетворяющими условию теоремы 66.Доказательство.
Обозначим через Nk (k = 1, 2, . . . , n) множество строкматрицы B T , в которых в k-м столбце стоят единицы. Очевидно, что такимобразом мы получим разбиение строк матрицы B T .1833.4.2. Описание алгоритмаПриведем здесь алгоритм, позволяющий распознать реберный граф, который основан на подходе, описанном в статье [124]. Согласно теореме 67, для данного графа G с матрицей смежности D = [dij ]m×m , требуется найти (0, 1)-матрицуB, для которой выполнено условие D = B T B. Кроме того, в каждом столбцематрицы B должно быть ровно две единицы.Рассмотрим первую вершину графа G. Поместим эту вершину в две кликис номерами 1 и 2. Таким образом, первая строка матрицы B T имеет вид (номерстолбца данной матрицы соответствует номеру клики, номер строки — номерувершины графа, единица в i-й строке j-м столбце обоначает, что i-я вершинапринадлежит j-й клике)(1, 1, 0, . .
. , 0).Отметим, что мы пока не знаем, сколько столбцов содержит матрица B T , однакоочевидно, что это число столбцов не превосходит m + 1.Если вершины 1 и 2 смежные (это соответствует случаю d12 = 1), то вершину 2 поместим в клики 1 и 3. В противном случае (если d12 = 0), поместимвершину 2 в клики 3 и 4.Каждая вершина графа G должна быть помещена в две клики. Распределение вершин по кликам возможно единственным образом за единственнымисключением. Неоднозначность возникает, когда в графе имеются три попарносмежные вершины.
В этом случае нам понадобится дополнительное условие.Используя его, мы докажем теорему 68, которая позволит однозначно распределить вершины по кликам.Определение 33. Двум смежным вершинам графа G соответствуют дваребра графа H, имеющих общую вершину. Предположим, что две другие вершины, принадлежащие этим ребрам, соединены ребром.
Тогда вершина графаG, соответствующая этому ребру, называется вершиной пересечения (crossnode) [124].184Не умаляя общности, предположим, что попарно смежными являются вершины 1, 2, и 3. Тогда поместим вершину 1 в клики 1 и 2, а вершину 2 — в клики1 и 3. Если вершина 3 смежна рассмотренным вершинам, она может быть помещена в клики 1 и 4 или в клики 2 и 3. Выбор одной из этих двух возможностейопределяется элементами матрицы D.Определение 34. Мы будем говорить, что выполнено условие четности, еслив первых трех строках матрицы D в каждом столбце имеется четное числоединиц.Другими словами, условие четности выполнено тогда и только тогда, когдатреугольник с вершинами 1, 2 и 3 четный, т. е.
каждая вершина графа G смежначетному количеству из данных трех вершин.Теорема 68. Условие четности выполнено тогда и только тогда, когда существует вершина пересечения.Доказательство. Обозначим через I, II, III, IV, и так далее, ребра графаH, соответствующие вершинам G с номерами 1, 2, 3, 4 и так далее, соответственно.Необходимость.
Предположим, что условие четности выполнено. Докажем,что в этом случае существует вершина пересечения.Напомним, что мы не рассматриваем исключительный случай, когда графсодержит только три вершины 1, 2 и 3, хоnя условие четности при этом очевидновыполнено. Рассмотрим одно из ребер графа H, которое имеет общую вершинус двумя из трех ребер I, II, III. Не умаляя общности, предположим, что реброIV имеет общие вершины с ребрами I и II. Предположим, что вершина 3 неявляется вершиной пересечения, так что ребра I, II и III имеют общую вершину.Из этого сразу же следует, что вершина 4 является вершиной пересечения.Достаточность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
