Лабораторный практикум № 1. дискретка. Отображения. Обратные отображения эта тема является очень важной, терминами из этой темы мы будем пользоваться во многих других вопросах
 Скачать 86.29 Kb.
|
|
42. ДОСТАТОЧНОЕ УСЛОВИЕ СУЩЕСТВОВАНИЯ ЦИКЛОВ ГАМИЛЬТОНА Элементарный цикл в графе называется циклом Гамильтона, если он проходит через все вершины графа. Возьмём, например, следующий граф: В нём более жирным цветом выделены те рёбра, по которым нужно двигаться так, чтобы пройти через каждую вершину по одному разу. Это и есть циклы Гамильтона (здесь их можно выделить немало). Можно сказать, что цикл Гамильтона – это некоторая последовательность вершин, по которой нужно двигаться, чтобы в итоге получился цикл, проходящий через все вершины графа по одному разу. Здесь можно выделить, например, такую циклическую последовательность: 𝑎1 → 𝑎8 → 𝑎7 → 𝑎2 → 𝑎3 → 𝑎6 → 𝑎5 → 𝑎4 → 𝑎1 (только с 𝑎4 нужно стрелку сразу в начало рисовать), или, например, 𝑎8 → 𝑎1 → 𝑎4 → 𝑎5 → 𝑎6 → 𝑎3 → 𝑎2 → 𝑎7 → 𝑎8. А, например, последовательность вершин 𝑎1 → 𝑎2 → 𝑎3 → 𝑎4 → 𝑎5 → 𝑎8 → 𝑎7 → 𝑎6 - это не цикл Гамильтона, да и вообще не цикл (так как начинается и заканчивается в разных вершинах). Это просто путь из вершины 𝑎1 в вершину 𝑎6. Представление цикла Гамильтона в виде циклической последовательности вершин понадобится в доказательстве достаточного условия существования циклов Гамильтона в графе. ТЕОРЕМА. Пусть 𝐺 = (𝑉, 𝑈) – неориентированный связный граф без петель. Если ∀ 𝑎, 𝑏 ∈ 𝑉 (𝑑(𝑎) + 𝑑(𝑏) ≥ |𝑉|), то в графе 𝐺 есть цикл Гамильтона. ДОКАЗАТЕЛЬСТВО. Степень вершины – это число, которое показывает количество рёбер, началом (ну или концом) которых является эта вершина. |𝑉| - это мощность множества вершин графа (по-другому – количество вершин в графе). Выпишем циклическую последовательность всех вершин графа: Наши стрелки нарисованы здесь, как будто для любых двух соседних вершин существует ребро. Но нам самом деле ребра между ними может не быть, и это нужно понимать (но всё же для вида они пусть будут нарисованы). Но мы в общем случае не знаем, между какими вершинами есть рёбра, а между какими нет ребёр. Поэтому введём для себя понятие разрыва между вершинами (оно используется только в рамках этой теоремы). Будем говорить, что в циклической последовательности между вершинами 𝑣𝑖 и 𝑣𝑖+1 имеется разрыв, если (𝑣𝑖 , 𝑣𝑖+1) не принадлежит 𝑈. В общем случае разрывы между соседними вершинами могут быть. Но если мы гарантированно знаем, что 𝑑(𝑎) + 𝑑(𝑏) ≥ |𝑉|, то мы сможем из этой циклической последовательности (которая с разрывами) составить новую циклическую последовательность без разрывов, а это и будет цикл Гамильтона, так как мы сможем выстроить вершины в определённой последовательности, чтобы его получить (но только зная условие теоремы). Отсутствие разрыва между соседними вершинами будет означать, что у нас есть возможность пройти из одной вершины в соседнюю по ребру, чтобы, собственно говоря, идти по циклу. Осталось предъявить этот алгоритм. Сразу скажем, что если перед нами граф, в котором для такой последовательности (которая выше нарисована) разрывов нет, то утверждение теоремы верно и мы нашли цикл Гамильтона (даже, наверное, не пользуясь соотношением в условии теоремы). Теперь предположим, что разрывы в такой последовательности есть. Так как все вершины равноправны, то будем считать, что разрыв имеется, например, между вершинами 𝑣1 и 𝑣2. Нам понадобится одно вспомогательное утверждение, которое нужно будет доказать. Утверждение: среди вершин 𝑣3,…, 𝑣𝑛 (то есть оставшихся) найдутся две соседние вершины 𝑣𝑖 и 𝑣𝑖+1 такие, что (𝑣1, 𝑣𝑖 ) ∈ 𝑈 и (𝑣2, 𝑣𝑖+1) ∈ 𝑈. То есть две соседние вершины, одна из которых соединяется с 𝑣1, а другая – с 𝑣2, обязательно найдутся. Докажем это методом от противного. Предположим, что такие две соседние вершины не нашлись. Пусть не нашлись две соседние вершины 𝑣𝑖 и 𝑣𝑖+1 такие, что (𝑣1, 𝑣𝑖 ) ∈ 𝑈 и (𝑣2, 𝑣𝑖+1) ∈ 𝑈. Тогда мы можем сказать, что, для любой пары 𝑣𝑖 и 𝑣𝑖+1 из множества вершин 𝑣3,…, 𝑣𝑛, для которых (𝑣1, 𝑣𝑖 ) ∈ 𝑈, вершины 𝑣𝑖+1 и 𝑣2 не будут соединены ребром (то есть (𝑣2, 𝑣𝑖+1) не ∈ 𝑼). То есть для любых пар вершин из 𝑣3,…, 𝑣𝑛 верно, что если какая-то из них (например, 𝑣3) является соседней с 𝑣1 (ну или то же самое – соединены ребром), то следующая за ней вершина (𝑣4) не будет соседней с 𝑣2 (их не будет соединять ребро). Теперь оценим количество вершин, которые не являются соседними с 𝑣2. Во-первых, их столько же, сколько вершин, соседних с 𝑣1, а это число – степень вершины 𝑣1, то есть равно 𝑑(𝑣1) (все вершины, соседние с 𝑣1, находятся среди вершин 𝑣3,…, 𝑣𝑛). Но есть один нюанс. А что, если 𝑣𝑛 соседняя с 𝑣1? Тогда вершина, следующая за 𝑣𝑛 - 𝑣1. А вершина 𝑣1 не является соседней с 𝑣2 (так как мы предположили, что там разрыв), поэтому мы этот случай тоже учли. Во-вторых, вершина 𝑣2 не является соседней с самой собой (как бы это странно не звучало). Поэтому общее количество вершин, не соседних с 𝑣2 хотя бы 𝑑(𝑣1 ) + 1 (их может быть и больше, но мы установили, что их число не меньше такого выражения). Последний штрих. Каждая вершина в графе - либо соседняя с 𝑣2 (таких вершин 𝑑(𝑣2 )), либо не соседняя с 𝑣2 (мы только что установили, что их хотя бы 𝑑(𝑣1 ) + 1). Поэтому количество вершин в графе не меньше, чем 𝑑(𝑣2 ) + 𝑑(𝑣1 ) + 1, то есть |𝑉| ≥ 𝑑(𝑣2 ) + 𝑑(𝑣1 ) + 1, или можно записать как 𝑑(𝑣2 ) + 𝑑(𝑣1 ) ≤ |𝑉| − 1. Но у нас есть условие теоремы, которое как раз нам здесь и пригодится, что 𝑑(𝑣1 ) + 𝑑(𝑣2 ) ≥ |𝑉| (это условие выполняется по условию теоремы для всех пар вершин). Здесь и получаем противоречие. Но это, к сожалению, мы доказали только вспомогательное утверждение. То есть мы теперь знаем только, что всегда найдутся две соседние вершины 𝑣𝑖 и 𝑣𝑖+1 такие, что (𝑣1, 𝑣𝑖 ) ∈ 𝑈 и (𝑣2, 𝑣𝑖+1) ∈ 𝑈. Этот факт позволяет нам составить новую циклическую последовательность, которая выглядит так: Причём нам неважно, есть ли ребро между вершинами 𝑣𝑖 или 𝑣𝑖+1 или нет. Выглядит непривычно, но это немного можно перерисовать для удобства и наглядности: Надеюсь, так лучше видно. В этой последовательности у нас теперь меньше разрывов, чем было раньше. Если получившаяся последовательность не содержит разрывов, то цикл Гамильтона построен. Если содержит – применяем по новой для тех вершин, для которых есть разрыв. Естественно, количество разрывов конечное число, поэтому процесс закончится и будет получена последовательность без разрывов, а значит, и цикл Гамильтона. Всё доказано. 43. СУММЫ ГРАФОВ Тема очень простая. Здесь просто нужно вспомнить одну функцию из алгебры логики, а именно сумма по модулю 2. Пусть у нас есть граф 𝐺 = (𝑉, 𝑈) и 𝑈 = {𝑢1, … , 𝑢𝑚} (то есть мы просто объявили граф и перечислили все его рёбра, рёбер m штук). Будем рассматривать подграфы с таким же числом вершин, как и у исходного графа, но своим количеством рёбер; будем представлять такие подграфы в виде двоичных наборов (нули и единицы будем сопоставлять рёбрам), где 1 будет означать, что такое ребро в подграфе есть, а 0 – что такого ребра в подграфе нет. Так как рёбер m штук и на каждую позицию можно поставить либо 0, либо 1, то всего подграфов 2 ∗ 2 ∗ … ∗ 2 (𝑚 раз) = 2 𝑚. Определение. Граф 𝐺3 = (𝑉, 𝑈3) является суммой графов 𝐺1 = (𝑉, 𝑈1) и 𝐺2 = (𝑉,𝑈2), если 𝛼 𝐺3 = 𝛼 𝐺1 + 𝛼 𝐺2 . 𝛼 𝐺1 - двоичный набор графа 𝐺1, который говорит о наличии или отсутствии тех или иных рёбер. Например, пусть у нас есть двоичные наборы двух графов 1001 и 1100. Применяем к ним сумму по модулю 2. Тогда двоичный набор нового графа будет 0101. Несмотря на то, что в обоих графах было первое ребро, в новом графе этого ребра нет, как если бы в двух графах не было этого ребра. ТЕОРЕМА. Сумма чётных графов есть чётный граф. ДОКАЗАТЕЛЬСТВО. Пусть у нас есть графы 𝐺1 = (𝑉, 𝑈1) и 𝐺2 = (𝑉,𝑈2). Возьмём в них произвольную вершину v. Пусть степень вершины v в 𝐺1 равна 2p (она чётная по определению чётного графа), а в 𝐺2 - 2q. В двух этих графах могут присутствовать одновременно одно и то же ребро, которое прилегает к вершине v. Пусть общих рёбер s штук. Посчитаем степень этой вершины в новом графе: 𝑑(𝑣) = 2𝑝 + 2𝑞 − 2𝑠. Для того, чтобы понять, почему вычитается удвоенное число, разберём пример. Пусть у нас в первом круге находятся те рёбра, которые содержат вершину v в графе 𝐺1, во втором – те рёбра, которые содержат вершину v в графе 𝐺2. Тогда те рёбра, к которым будет прилегать вершина v в новом графе (сумме графов 𝐺1 и 𝐺2) – это красная область (общая область – это общие рёбра, которых в новом графе нет). Красная область – это сумма двух кругов (2𝑝 + 2𝑞) за вычетом двух накопившихся общих областей (−2𝑠). Ну и всё, в итоге получили, что степень вершины v в новом графе – чётная. Так как v – произвольная вершина, то у графа будут все вершины с чётными степенями. А значит, это чётный граф. 44-45. ФУНДАМЕНТАЛЬНОЕ СЕМЕЙСТВО ЦИКЛОВ ГРАФА Фундаментальное семейство циклов графа очень сильно напоминает линейную зависимость/независимость векторов, с помощью векторов можно привести аналогию. В фундаментальном семействе циклов какого-то графа содержатся циклы, любой из которых нельзя выразить с помощью других циклов, находящихся с ним (то есть здесь аналогия с линейной независимостью векторов, которые могут образовывать базис пространства); но с помощью циклов из этого семейства графа можно получить любой простой цикл этого графа (то есть здесь аналогия с линейной комбинацией векторов, линейной зависимостью). На этом и завязано определение фундаментального семейства циклов графа. Фундаментальное семейство циклов состоит из элементарных циклов длины не меньше трёх. Выражать простой цикл графа через циклы фундаментального семейства циклов этого графа можно с помощью операции суммы. Но для начала нужно определить операцию сложения циклов. Мы уже умеем складывать графы. Поэтому нам легче будет сложить графы, чем мы бы учились складывать новые объекты. Пусть у нас есть граф 𝐺 = (𝑉, 𝑈). Возьмём любой цикл в этом графе (допустим, что цикл есть). Сопоставим этому циклу граф 𝐺𝐶 = (𝑉, 𝐸(𝐶)). То есть это граф, содержащий все вершины графа 𝐺 (все вершины нам как раз таки и нужны, чтобы производить сложения; вершин в слагаемых должно быть одинаковое количество) и содержащий те рёбра, которые соответствуют циклу C (E(C) – множество всех рёбер графа C). Определение. Цикл 𝐶 в графе 𝐺 = (𝑉, 𝑈) называется суммой циклов 𝐶1 и 𝐶2 этого графа, если 𝐺𝐶 = 𝐺𝐶1 + 𝐺𝐶2 . Но нужно понимать, что при сложении двух графов, даже если эти графы представляют циклы, не всегда получится в итоге граф, представляющий цикл. То есть сложить-то сможем эти графы, но не факт, что может быть получен цикл. Поэтому, если в итоге всё же получился цикл, то принято записывать 𝐶 = 𝐶1 + 𝐶2. ТЕОРЕМА. Всякий неориентированный связный граф без петель имеет фундаментальное семейство циклов. ДОКАЗАТЕЛЬСТВО. Доказательство состоит из двух этапов (очень похоже на первые 2 пункта доказательства теоремы об отношении эквивалентности): 1) Построение этого семейства 2) Доказательство фундаментальности этого семейства 1) Алгоритм построения семейства несложный. Рассматриваем все циклические рёбра, входящие в этот граф (циклическое ребро – это всего лишь ребро, через которое проходит цикл). Взяли одно такое ребро. Потом рассматриваем элементарный цикл, который через это ребро проходит; элементарный цикл включаем в семейство, а циклическое ребро удаляем. Такие действия проводим со всеми циклическими рёбрами, пока они не закончатся. В итоге после удаления всех циклических рёбер у нас граф будет являться деревом (так как дерево – это по определению, можно сказать, граф без циклов). Во-первых, сразу стоит сказать, что если граф не имеет циклических рёбер, то ни о каких циклах этого графа говорить не приходится, и здесь мы полагаем, что F (так мы обозначаем семейство) = ∅. Далее, пусть граф всё же имеет циклические рёбра. Действуем так, как было написано выше. Выбираем первое циклическое ребро 𝑢1 и ищем элементарный цикл длины не меньше трёх, проходящий через это ребро. Цикл включаем в семейство, а ребро удаляем из графа. Если циклических рёбер не осталось, то процедуру завершаем. Если нет – продолжаем до тех пор, пока процедура не закончится. То есть берём второе циклическое ребро, ищем цикл, проходящий через него, цикл включаем в семейство, а ребро удаляем из графа. В итоге у нас получается дерево (граф без циклических рёбер), которое обозначим как 𝐺 𝑘 , 𝑘 – цикломатическое число графа (количество рёбер, которые мы удалили). Причём здесь важно понимать, какое ребро и когда мы его удалили (то есть порядок удаления циклических рёбер), это нам пригодится чуть позже. Теперь разберём, чему равно цикломатическое число 𝑘. Оно равно количеству циклов в графе (сколько рёбер удалили, столько и циклов). Есть такой факт, который требуется доказать ещё в вопросе про деревья, что для дерева количество вершин на один больше, чем количество рёбер: |𝑉| = |𝑈| + 1 (несложно доказывается). Так вот, пусть |𝑉| = 𝑛, |𝑈| = 𝑚 (это для изначального графа, а не для дерева). Изначально в графе было 𝑚 рёбер, а стало 𝑚 − 𝑘. Причём получилось дерево. Поэтому мы вправе воспользоваться формулой |𝑉| = |𝑈| + 1, но только количество рёбер будет 𝑚 − 𝑘: 𝑛 = 𝑚 − 𝑘 + 1 То есть 𝑘 = 𝑚 − 𝑛 + 1. Мы построили некоторое семейство циклов. Но мы пока не знаем, будет ли это семейство фундаментальным или нет. Поэтому нужно это проверить, что и делаем во втором пункте. 2) Для доказательства фундаментальности нужно доказать два утверждения: 1. Ни один цикл семейства не является суммой других циклов из F 2. Всякий простой цикл в графе G ненулевой длины представляется суммой циклов из F Доказываем первое от противного. Пусть какой-то цикл из семейства, которое мы построили, представляется в виде суммы других циклов из этого же семейства: 𝐶𝑗 = 𝐶𝑖1 + ⋯ + 𝐶𝑖𝑟 , 𝑖1 < ⋯ < 𝑖𝑟 (то есть индексы просто расположили в порядке возрастания; 𝑖 здесь выскакивает опять же по той причине, что мы не знаем, какие циклы мы берём, к примеру 𝑖1 может равняться 1, может 2, и тд). Вот здесь нам и понадобится тот самый порядок удаления циклических рёбер. У нас каждому циклу семейства соответствует то ребро, которое удаляли из-за него (у 𝐶𝑗 это ребро 𝑢𝑗 , у 𝐶𝑖1 это 𝑢𝑖1 , у 𝐶𝑖𝑟 это 𝑢𝑖𝑟 ). Возможны 2 случая: либо ребро 𝑢𝑗 было удалено раньше ребра 𝑢𝑖1 (и тогда 𝑗 < 𝑖1, так как чем раньше удалено ребро, тем меньше его индекс), либо наоборот, позже (и тогда 𝑗 > 𝑖1). Сейчас будем опираться только на равенство 𝐶𝑗 = 𝐶𝑖1 + ⋯ + 𝐶𝑖𝑟 . 1) 𝑗 > 𝑖1 Тогда к моменту, когда составлялся цикл 𝐶𝑗 , ребро 𝑢𝑖1 уже было удалено, поэтому в цикле 𝐶𝑗 этого ребра нет. Однако в цикле 𝐶𝑖1 это ребро есть, так как этот цикл через него проходит. Получаем несостыковку. 2) 𝑗 < 𝑖1 (то есть ребро 𝑢𝑗 было удалено раньше, чем все рёбра 𝑢𝑖1 ,…, 𝑢𝑖𝑟 ) Здесь рассуждения аналогичные, только здесь получается, что цикл 𝐶𝑗 содержит ребро 𝑢𝑗 , но ни одно из слагаемых правой части не содержит это ребро, так как к моменту, когда составлялись циклы из правой части равенства, ребра 𝑢𝑗 уже не было. Поэтому слева ребро 𝑢𝑗 есть, а справа нет. Несостыковка. 𝑗 не может равняться 𝑖1, иначе цикл семейства будет выражаться сам через себя, а нам бы этого не хотелось. Всё, первое утверждение доказали и поняли, что это семейство удовлетворяет первому условию из определения фундаментальности, осталось доказать второе и можно будет смело сказать, что мы построили фундаментальное семейство циклов. Доказываем второе утверждение из определения. Возьмём любой простой цикл 𝐶 из нашего графа. В итоге нам нужно прийти к равенству вида 𝐶 = 𝐶𝑖1 + ⋯ + 𝐶𝑖𝑟 (r у нас – это количество тех циклов, которое нужно для того, чтобы выразить тот или иной простой цикл 𝐶 из графа). Цикл 𝐶 содержит хотя бы одно из рёбер {𝑢1, … , 𝑢𝑘}, иначе – этот цикл бы проходил через граф, в котором все эти рёбра удалены. Но мы удалили все циклические рёбра из графа, поэтому сам граф стал деревом (графом без циклов). А в дереве никаких простых циклов ненулевой длины быть не может (могут быть нулевой длины, но это всё фигня, кому они нужны)). Этих рёбер может быть 1, 2, k-2, и тд, но одно точно есть. Выберем из всех рёбер {𝑢1, … , 𝑢𝑘}, которые есть в 𝐶, ребро с минимальным индексом (то есть то ребро, которое было раньше всех удалено; сейчас рассматриваем только рёбра из этого множества, которые принадлежат 𝐶). Назовём его 𝑢𝑖1 (𝑖1 опять же из-за того, что мы не знаем конкретный номер этого ребра, он нам неизвестен). Теперь берём цикл из семейства, который содержит это ребро (𝐶𝑖1 ). Теперь составим сумму 𝐶 + 𝐶𝑖1 . Если мы циклам сопоставим графы, которые их представляют, то получится новый какойто граф. Нужно понять, какими свойствами этот граф обладает. Графыслагаемые у нас – неориентированные, без петель и чётные. Почему чётные? Граф 𝐺𝐶 представляет простой цикл в графе 𝐺. Но сам-то граф – это же тупо простой цикл, и из него граф 𝐺𝐶 только и состоит. Поэтому в нём можно выделить цикл Эйлера (цикл Эйлера по определению – это простой цикл, проходящий через все рёбра графа; но все рёбра 𝐺𝐶 принадлежат циклу 𝐶 и нам вообще не важно, через все вершины он проходит или нет, главное – чтобы он проходил через все рёбра). Раз можно выделить Эйлера, то по его теореме граф чётный. Извиняюсь, что много текста, но по-другому не умею)) Граф, представляющий цикл 𝐶𝑖1 , также будет чётным, так как этот цикл элементарный (он из семейства, а семейство состоит из элементарных). Элементарный цикл – цикл, в котором все вершины (за исключением начала и конца) разные. Поэтому если мы один раз в вершину пришли, то из неё выйдем тоже один раз. Тогда степень каждой вершины будет равна 2, а значит, граф чётный. Сумма чётных графов – чётный граф, поэтому 𝐶 + 𝐶𝑖1 - чётный граф, неориентированный и без петель (может быть несвязным). И в 𝐶, и в 𝐶𝑖1 содержится ребро 𝑢𝑖1 , поэтому сумма это ребро не содержит. Но может содержать другие какие-то циклические рёбра, и они будут только из множества {𝑢1, … , 𝑢𝑘}. А те рёбра, которые с собой помимо 𝑢𝑖1 привёз цикл 𝐶𝑖1 , они какой-то свой новый цикл не будут образовывать, так как 𝐶𝑖1 «разомкнётся» из-за удаления 𝑢𝑖1 . Если ещё рёбра циклические есть – выберем из оставшихся рёбер с минимальным индексом, но такое, чтобы оно было удалено чуть позже, чем 𝑢𝑖1 , но раньше, чем остальные рёбра из множества {𝑢1, … , 𝑢𝑘} в графе 𝐶 + 𝐶𝑖1 . Назовём его 𝑢𝑖2 . Теперь берём цикл из семейства, который содержит это ребро (𝐶𝑖2 ). Проделываем короче то же самое. Составляем сумму 𝐶 + 𝐶𝑖1 + 𝐶𝑖2 . Так как граф, представляющий цикл 𝐶 + 𝐶𝑖1 , чётный, и граф цикла 𝐶𝑖2 тоже чётный (по тем же причинам, что выше), то получившийся граф этой тройной суммы (граф тройной суммы – это чисто моё, чтобы подсократить хотя бы немного текст) тоже чётный. Причём 𝐶 + 𝐶𝑖1 имеет 𝑢𝑖2 (так как мы предположили, что в 𝐶 + 𝐶𝑖1 есть ещё циклические рёбра), и это же ребро есть в 𝐶𝑖2 . Поэтому в сумме этого ребра нет. Процедуру проделываем до тех пор, пока есть рёбра из {𝑢1, … , 𝑢𝑘}. На определённом шаге получим сумму 𝐶 + 𝐶𝑖1 + ⋯ + 𝐶𝑖𝑟 , которая не будет содержать циклических рёбер и значит, граф этой суммы будет деревом. Но с другой стороны – мы получили чётный граф, поскольку в сумме у нас только чётные графы. Поэтому по теореме Эйлера в графе суммы 𝐶 + 𝐶𝑖1 + ⋯ + 𝐶𝑖𝑟 можно выделить цикл Эйлера. Но никакого адекватного цикла Эйлера в дереве не выделишь, потому что дерево циклов нормальных не содержит. Поэтому на самом деле в графе, представляющем сумму циклов 𝐶 + 𝐶𝑖1 + ⋯ + 𝐶𝑖𝑟 , вообще нет рёбер, то есть 𝐶 + 𝐶𝑖1 + ⋯ + 𝐶𝑖𝑟 = ∅. Осталось совсем чуть-чуть!!!! Нужно доказать равенство 𝐶 = 𝐶𝑖1 + ⋯ + 𝐶𝑖𝑟 . Для этого берём и обозначаем 𝐶𝑖1 + ⋯ + 𝐶𝑖𝑟 за какой-то граф 𝐺. Тогда сумма графов 𝐺𝐶 и 𝐺 равна графу без рёбер, то есть (V, ∅). Но в сумме по модулю 2 два слагаемых дают 0 только в случае, если они равны. Поэтому 𝐺𝐶 = 𝐺 и 𝐶 = 𝐶𝑖1 + ⋯ + 𝐶𝑖𝑟 . |