Информатика · объяснение и практика

Чётной суммы мало: как построить граф по заданным степеням

Проверить графичность списка степеней и построить одну помеченную реализацию простого графа методом Хавела — Хакими.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Графы и маршруты · Учебная карта

Главная мысль

Последовательность степеней задаёт ограничения на соседство, а не готовый граф. Чётная сумма является лишь необходимой проверкой. Метод Хавела — Хакими последовательно снимает максимальную степень, уменьшая степени выбранных соседей, и позволяет восстановить сами рёбра.

Метод и постановка

Работа идёт с простым неориентированным графом без петель и кратных рёбер. Поэтому степень неотрицательна и меньше числа вершин. Сохраните исходные номера вершин при сортировке остаточных степеней: иначе построенная матрица может удовлетворять переставленному списку, но не исходному. При равных степенях для воспроизводимости достаточно выбирать меньший исходный номер первым.

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

Проверка и границы вывода

Восстановленная матрица должна быть симметричной, иметь нулевую диагональ и только нули или единицы. Сумма каждой строки сравнивается с соответствующим исходным элементом, а не с отсортированной копией. Полезно также проверить, что число рёбер равно половине суммы исходных степеней. Эти проверки подтверждают предъявленную реализацию, но не делают её единственной.

Один и тот же список часто допускает разные графы, в том числе с разными расстояниями и структурой циклов. Поэтому ответ «графичен» не разрешает восстанавливать скрытую настоящую сеть из одних степеней. Вход описывает только локальные количества соседей. Нулевая степень не требует удаления вершины: она остаётся изолированной в матрице. При отказе нельзя исправлять отрицательный остаток модулем или автоматически добавлять кратное ребро, поскольку это изменило бы класс допустимых графов и саму исходную задачу.

Пример

Список (3,3,3,1) имеет чётную сумму десять. После присоединения первой вершины ко всем остальным остаются степени (2,2,0) у трёх вершин.

Вершина остаточной степени два видит лишь одного кандидата с положительной степенью. Список не графичен, хотя проверка чётности успешно прошла.

От чтения к действию

А теперь — вы

Почему при сортировке необходимо хранить исходные номера?

Частые вопросы

Чётная сумма гарантирует граф?

Нет. Это необходимое условие; ограничения простого графа могут всё равно нарушаться.

Граф единственный?

Нет. Возвращается одна реализация с детерминированным разрешением равных степеней по номеру вершины.

Углублённый разбор

Степенная последовательность дополнения графа

Дополнение превращает плотный простой граф в разреженный и сохраняет задачу графичности через явное преобразование степеней. Но сортировка списка меняет соответствие меткам, поэтому восстановление нужно проверять на исходных вершинах.

Перед началом: Степень вершины; Простой граф.

Каждая отсутствующая пара становится ребром

На фиксированном наборе n вершин дополнение содержит ровно те неупорядоченные пары различных вершин, которых не было в G. Из n−1 возможного соседа у вершины v ровно d(v) уже использованы в G, поэтому d_compl(v)=n−1−d(v). Петли не добавляются: выражение n−d(v) дало бы лишнюю единицу.

Операция обратима: дополнение дополнения возвращает исходный граф. Следовательно, список d графичен тогда и только тогда, когда графичен список n−1−d с сохранёнными метками. Это позволяет искать реализацию более разреженной стороны, а затем переключить все пары, не меняя формальную задачу существования.

Сортированный порядок переворачивается

Если d₁≥…≥dₙ, то преобразованные значения n−1−dᵢ идут по возрастанию. Для нового невозрастающего списка их нужно прочитать с конца. Но саму матрицу следует строить по меткам, а не присвоить отсортированные значения старым вершинам без обратной перестановки. Числовая проверка отсортированных степеней может скрыть такую ошибку.

Числа рёбер связаны равенством m_compl=n(n−1)/2−m. Это даёт независимый суммарный контроль. При этом графичность не означает единственность реализации: разные дополнения с тем же списком могут дать разные исходные графы. Операция является биекцией реализаций, а не способом угадать неизвестную настоящую сеть.

Другие свойства не переносятся одним численным правилом

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

Для самодополнительного графа необходимы m=n(n−1)/4 и целочисленность этого числа. Это только необходимое арифметическое ограничение, не доказательство изоморфизма данного графа со своим дополнением. Одинаковые списки степеней тоже не доказывают изоморфизм;явное соответствие вершин остаётся самостоятельной задачей.

Плотный список через шесть отсутствующих пар

Условие. Для n=6 и меток 0,…,5 реализуйте степени(4,4,3,3,2,2) через дополнение с рёбрами 04,15,23,24,35,45.

  1. В предъявленном дополнении степени по меткам равны(1,1,2,2,3,3). Его шесть рёбер легко проверить подсчётом концов.
  2. Преобразование 5−d_compl даёт(4,4,3,3,2,2), то есть ровно исходный помеченный список.
  3. В полном графе на шести вершинах 15 пар. Удаление шести перечисленных пар оставляет 9 рёбер исходной реализации.
  4. Сумма исходных степеней 18 равна 2·9. Дополнение построенной матрицы возвращает первоначальные шесть пар, проверяя обратимость операции.

Ответ. Исходный граф содержит 9 рёбер; дополнение реализует степени(1,1,2,2,3,3).

Проверка. Прямой перебор 15 неупорядоченных пар и исключение шести заданных независимо возвращает нужные шесть сумм строк. Диагональ остаётся нулевой.

Где легко ошибиться. Сохраните метки при перевороте сортированного порядка. Формула степеней не разрешает автоматически переставить вершины восстановленной матрицы.

Проверьте понимание

Сколько рёбер имеет исходная реализация в задаче?

Вопросы к этой главе

Можно дополнить мультиграф той же формулой?

Нет. Формула считает наличие либо отсутствие единственной пары. Кратность рёбер требует другого определения, которое нужно задать отдельно.

Зачем использовать дополнение при построении?

Если исходные степени близки к n−1, список отсутствующих рёбер короче. Это может упростить ручной сертификат, хотя итоговую помеченную матрицу всё равно нужно проверить.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • NetworkX: complement

    Официальная документация: прочитаны определение дополнения и отсутствие петель/кратных рёбер. Собственные метки, степени и явная реализация построены отдельно.

Двудольные степени и критерий Гейла — Райзера

Для двудольного графа отдельно задаются степени двух долей. Равенства общих сумм недостаточно: каждое крупное подмножество строк должно помещаться в суммарную ёмкость столбцов.

Перед началом: Двудольный граф; Нулевая и единичная матрица.

Столбец способен обслужить только ограниченное число строк

Пусть r₁≥…≥r_m≥0 — степени левой доли, а s₁,…,s_n≥0 — правой. Их суммы должны совпадать, поскольку каждое ребро учитывается по одному разу с каждой стороны. Для первых k строк столбец j может дать не больше min(k,s_j) единиц: он имеет всего s_j единиц и не больше одной в каждой строке.

Поэтому необходимы Σᵢ≤k rᵢ≤Σⱼmin(k,sⱼ) для каждого k=1,…,m. Критерий Гейла—Райзера утверждает достаточность этих условий вместе с неотрицательной целочисленностью и равенством сумм. Проверки одного общего числа рёбер и максимальной степени эту систему не заменяют.

Проверять все подмножества заменяет сортировка

Среди подмножеств k строк наибольшая сумма степеней получается на первых k после сортировки. Поэтому достаточно именно этих префиксов. Сама правая последовательность в выражении суммы минимумов может идти в любом порядке. Если затем восстанавливаются конкретные связи, метки обеих долей нужно вернуть к исходному порядку.

Потоковая интерпретация объясняет достаточность: источник соединён со строками ёмкостями rᵢ, между каждой строкой и столбцом ёмкость 1, столбцы ведут в сток ёмкостями sⱼ. Условия исключают недостаточную ёмкость разрезов. Целочисленность максимального потока превращает допустимый поток в бинарную матрицу, а не в дробные доли рёбер.

Нарушенный префикс является коротким отрицательным сертификатом

При отказе достаточно назвать k и две точные суммы. Это доказательство отсутствия любой реализации, а не неудача одного жадного построения. При успехе полезно предъявить саму матрицу и независимо проверить все суммы: ошибка сортировки либо восстановления меток возможна даже после правильного теоретического теста.

Теорема относится к простому двудольному графу. Если разрешить несколько рёбер между одной парой, ёмкость 1 исчезнет и ограничение min(k,sⱼ) изменится. Если заранее запретить некоторые пары, полная двудольная сеть тоже исчезнет: понадобится проверка её конкретных разрезов, а не этот общий критерий.

Одна допустимая и одна невозможная пара

Условие. Проверьте пары r=(3,2,1),s=(2,2,2) и r=(3,3,0),s=(3,2,1).

  1. У первой пары обе суммы 6. Для k=1,2,3 левая сумма 3,5,6, а правая 3,6,6;все неравенства выполнены.
  2. Матрица[[1,1,1],[1,1,0],[0,0,1]] имеет заданные первые суммы строк и столбцов, подтверждая существование.
  3. У второй пары суммы тоже 6 и степени не превышают размер другой доли. Но при k=2 левая сумма 6, правая min(2,3)+min(2,2)+min(2,1)=5.
  4. Неравенство 6≤5 ложно, поэтому ни одной бинарной реализации второй пары нет. Первые две строки требуют по три единицы, что заставило бы все три столбца иметь степень хотя бы 2.

Ответ. Первая пара реализуема; вторая невозможна из-за префикса k=2.

Проверка. Полный перебор 512 бинарных матриц 3×3 находит предъявленную первую пару и не находит вторую. Это независимая проверка разрезного сертификата и всех пределов степеней.

Где легко ошибиться. Совпадение сумм и допустимость каждой отдельной степени не гарантируют совместимость двух долей. Отрицательный префикс опровергает все реализации сразу.

Проверьте понимание

Какова ёмкость правой стороны при k=2 для s=(3,2,1)?

Вопросы к этой главе

Почему r нужно сортировать?

Префиксы должны представлять наибольшую возможную сумму среди k строк. Без сортировки проверенный префикс может пропустить более требовательное подмножество.

Это критерий обычной графичности одного списка?

Нет. Доли зафиксированы, и рёбра разрешены только между ними. Обычный простой граф имеет другую задачу реализации и другие условия.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • SageMath: is_gale_ryser

    Официальная документация: вебом прочитаны условия binary matrix с заданными суммами строк/столбцов и критерий Гейла—Райзера. Собственная допустимая матрица и отдельный нарушающий разрез рассчитаны независимо; PDF Krause по найденному адресу не прочитан из-за таймаута.

Формула Эйлера запрещает некоторые планарные вложения

Число вершин и рёбер может запретить плоское вложение, даже если степени выглядят допустимыми. Формула Эйлера вместе с длинами границ граней даёт строгие верхние оценки. Их прохождение, однако, не является алгоритмом распознавания планарности: подразделение рёбер создаёт явные контрпримеры.

Перед началом: Степень вершины; Грань плоского вложения.

Граница грани учитывает мост дважды

Для связного плоского вложения n−m+f=2, где f включает внешнюю грань. Сумма длин всех граничных обходов равна 2m: каждая сторона каждого ребра принадлежит некоторой грани. Мост может встречаться дважды в одном обходе, а не образовывать новую грань. Поэтому нельзя считать границу просто множеством различных рёбер и терять её кратности.

В простом связном графе с n≥3 длина каждого граничного обхода не меньше 3; тогда 3f≤2m. Совмещая с Эйлером, получаем m≤3n−6. Для несвязного простого графа та же верхняя оценка сохраняется: можно соединить компоненты дополнительными рёбрами в плоском вложении. Петли и параллельные рёбра исключены, иначе возможны грани длины 1 или 2 и вывод изменится.

Отсутствие треугольников усиливает необходимое условие

Если простой граф не содержит треугольников и имеет n≥3, при наличии циклов границы имеют длину не меньше 4; леса удовлетворяют той же итоговой оценке напрямую. Получаем m≤2n−4. В частности это применимо к двудольным графам. Для K₃,₃ имеем n=6,m=9, а верхняя граница равна 8, поэтому плоское вложение невозможно.

Обе оценки являются только необходимыми. Удаление рёбер может уменьшить плотность, но не всякий малоплотный граф планарен. Более того, замена одного ребра путём через новую вершину увеличивает n и m на1, сохраняя саму возможность плоского вложения: вершину степени 2 можно вставить на дуге или, обратно, сгладить её. Поэтому плотностный фильтр может перестать замечать ту же топологическую преграду.

Подразделение отделяет численный фильтр от полного критерия

Чтобы показать недостаточность оценки, достаточно предъявить непланарный граф, проходящий её, и объяснить непланарность независимо. Одного совпадения чисел недостаточно. В подразделённом K₃,₃ предполагаемое плоское вложение позволило бы удалить новую вершину степени 2 и соединить две части её дуги, получив плоский исходный K₃,₃. Это противоречит уже доказанному запрету. Такой аргумент использует структуру, которую одни n,m не сохраняют в достаточной степени.

Один новый узел скрывает плотностное нарушение

Условие. Начните с K₃,₃ и замените одно ребро uv двумя рёбрами uz,zv через новую вершину z. Проверьте две численные оценки и решите, стал ли граф планарным.

  1. Исходный K₃,₃ имеет 6 вершин,9 рёбер и не содержит треугольников. Поскольку 9>2·6−4=8, он непланарен.
  2. После подразделения получаем n=7,m=10. Треугольников по-прежнему нет: любой новый цикл через z заменяет старый участок uv более длинным.
  3. Обычная граница даёт 10≤3·7−6=15, усиленная 10≤2·7−4=10. Оба необходимых численных условия теперь выполнены.
  4. Если бы новый граф имел плоское вложение, сглаживание z степени 2 восстановило бы исходное ребро uv без новых пересечений. Получился бы плоский K₃,₃, что невозможно. Значит граф остался непланарным.

Ответ. Обе оценки пройдены, но граф непланарен; плотностные условия недостаточны.

Проверка. Независимая проверка списка рёбер подтверждает n=7,m=10, отсутствие треугольников и ровно две связи z. После их замены одним uv получается точный исходный K₃,₃ с нарушенной границей.

Где легко ошибиться. Не утверждайте планарность из m≤3n−6 или m≤2n−4. Эти условия могут только отвергнуть вход; прошедшему графу требуется структурная проверка или явное вложение.

Проверьте понимание

Что верно для K₃,₃ после одного подразделения ребра?

Вопросы к этой главе

Остаётся ли подразделённый граф двудольным?

Не обязательно: подразделение одного ребра чётного цикла делает соответствующий цикл нечётным. В примере возникает цикл длины 5. Усиленная оценка всё равно применима, потому что граф остаётся свободным от треугольников.

Почему внешняя грань включена в f?

Она имеет такую же границу из сторон рёбер, как ограниченные грани. Без неё нарушаются и формула n−m+f=2, и двойной подсчёт суммарной длины границ.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Jeff Erickson: Planar Graphs, §2.7 Euler’s Formula

    Прочитаны формула Эйлера, подсчёт длин граней и следствия для простых графов; отдельно проверены условия n≥3 и отсутствие треугольников. Собственный контроль подразделённого K3,3 показывает недостаточность обоих численных фильтров, а не утверждает обратную теорему.

Переключение двух рёбер сохраняет степени, но меняет реализацию

Одна последовательность степеней допускает разные графы. Операция 2-switch меняет две пары соседства, сохраняя степень каждой помеченной вершины. Законность переключения зависит от отсутствия новых петель и повторов; связность при этом не обязана сохраняться, даже если исходный граф был одним циклом.

Перед началом: Степень помеченной вершины простого графа; Связность и отсутствие кратных рёбер.

Четыре различные вершины получают по одному старому и новому ребру

Пусть в простом неориентированном графе есть рёбра ab и cd с четырьмя различными концами. Если рёбер ac и bd нет, можно удалить ab,cd и добавить ac,bd. Каждая из четырёх вершин теряет одно инцидентное ребро и получает одно, поэтому весь помеченный вектор степеней сохраняется.

Требование четырёх различных концов запрещает петли и неоднозначные совпадения удаляемых рёбер. Отсутствие новых пар в исходном наборе предотвращает кратные рёбра. Можно выбрать и другое перекрёстное соединение ad,bc, но его допустимость проверяется отдельно. Сохранение одной суммы степеней было бы слабее покоординатного сохранения каждой метки.

Пространство реализаций связано, но отдельные свойства меняются

Для простых помеченных графов с одним и тем же вектором степеней существует последовательность допустимых 2-switch, переводящая одну реализацию в другую. Поэтому переключения используют для исследования разных реализаций, а не как ещё один тест графичности уже заданного списка.

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

Проверка шага состоит из локальной и глобальной частей

Локально достаточно удостоверить существование старых рёбер, различность четырёх вершин и отсутствие новых рёбер. Затем сравнивают степени до и после и проверяют, что матрица осталась симметричной с нулевой диагональю. Это сертификат корректного переключения.

Глобальные свойства исследуют независимо. Например, обход связности после шага может показать распад на компоненты. Нельзя считать такую проверку избыточной только потому, что у каждой вершины осталось по два соседа. Граф степени два может состоять из одного длинного цикла или нескольких отдельных циклов.

Один шестицикл превращается в два треугольника

Условие. Пусть рёбра равны 01,12,23,34,45,05. Выполните переключение, удаляющее 12 и 45 и добавляющее 15 и 24. Проверьте законность, степени и связность результата.

  1. Удаляемые рёбра существуют и имеют четыре различные вершины 1,2,4,5. Пар 15 и 24 в исходном шестицикле нет, поэтому шаг допустим.
  2. После замены остаются рёбра 01,23,34,05,15,24. Каждая вершина по-прежнему имеет степень два; число рёбер осталось шесть.
  3. Вершины 0,1,5 образуют треугольник по рёбрам 01,15,05. Вершины 2,3,4 образуют второй по рёбрам 23,34,24.
  4. Между двумя тройками рёбер нет, поэтому число компонент выросло с одной до двух. Диаметры и треугольная структура изменились, хотя степени полностью сохранились.
  5. Обратное переключение удаляет новые пары и возвращает прежние рёбра, значит операция обратима как переход между помеченными реализациями.

Ответ. Переключение законно и сохраняет вектор (2,2,2,2,2,2), но нарушает связность: результат состоит из двух треугольников.

Проверка. Независимые списки соседей до и после проверяют все шесть степеней. Два обхода связности и полный список новых рёбер подтверждают распад, который один подсчёт степеней не обнаруживает.

Где легко ошибиться. Не объявляйте переключение сохраняющим связность только потому, что оно сохраняет степени. Связность — отдельное глобальное условие, и пример даёт прямой контрпример.

Проверьте понимание

Что происходит со связностью после указанного допустимого 2-switch?

Вопросы к этой главе

Можно ли добавить уже существующее ребро и просто оставить один экземпляр?

Нет. Тогда одна из вершин потеряет ребро без соответствующего нового вклада, и сохранение степеней нарушится. В простом графе новые пары должны отсутствовать заранее.

Почему нельзя соединять реализации с одинаковым отсортированным списком, забыв метки?

Операция сохраняет степень каждой конкретной вершины. Перед преобразованием нужно согласовать соответствие меток; одинаковый отсортированный список сам по себе этого соответствия не задаёт.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Bereg, Ito: Transforming graphs with the same graphic sequence

    Прочитана аннотация статьи о преобразовании помеченных реализаций 2-switch и сохранении степени каждой вершины. Здесь не используется алгоритм минимального числа шагов из статьи. Локальные условия и контрпример сохранению связности проверены отдельно.

Эрдёш—Галлаи: неравенство объясняет невозможную степенную последовательность

Чётность суммы степеней исключает часть невозможных графов, но не контролирует спрос группы крупных вершин на соседей. Критерий Эрдёша—Галлаи сравнивает каждый префикс с количеством инцидентностей, которое способны предоставить внутренние и внешние рёбра. Нарушение одного неравенства является коротким доказательством невозможности любой простой реализации, а не неудачей выбранного жадного порядка.

Перед началом: Степени простого графа и лемма о рукопожатиях; Сортировка и префиксные суммы.

Крупные степени конкурируют за ограниченные связи

Один невозрастающий список неотрицательных целых степеней простого неориентированного графа; петли и кратные рёбра запрещены.

Пусть d₁≥…≥dₙ≥0, все значения целые и меньше n. Для первых k вершин сумма степеней учитывает внутренние рёбра дважды, а выходящие наружу — один раз. Внутри k вершин возможно не больше k(k−1)/2 рёбер, дающих не больше k(k−1) инцидентностей.

Внешняя вершина j может соединиться с группой не более чем min(k,dⱼ) рёбрами: ограничены и число разных возможных соседей в группе, и её собственная степень. Поэтому необходимо Σᵢ≤k dᵢ≤k(k−1)+Σⱼ>k min(k,dⱼ). Внешний вклад здесь считается только по хвосту списка, поскольку связи внутри префикса уже учтены отдельно.

Чётность и все префиксы дают достаточный критерий

Теорема Эрдёша—Галлаи утверждает достаточность этих неравенств для k=1,…,n вместе с чётностью общей суммы и неотрицательной целочисленностью. Проверять произвольный порядок вместо невозрастающего нельзя: префиксы должны представлять наиболее требовательные группы заданного размера. При отказе сохраняют k, левую и правую суммы.

Это критерий одного списка для обычного графа. В двудольном варианте фиксируются две отдельные доли, и внутренний член k(k−1) отсутствует в соответствующей строковой проверке. Одинаковые слова «префикс» и «степень» поэтому не разрешают перенести формулу Гейла—Райзера на неразделённое множество вершин.

Положительный ответ и построенная сеть проверяются отдельно

Все неравенства можно вычислить непосредственно за O(n²); префиксные суммы и границы одинаковых значений позволяют ускорить реализацию. Для короткой учебной задачи явная таблица предпочтительнее скрытого оптимизированного кода: в ней видны ограничения, которые сработали точно на границе.

Критерий устанавливает существование, но сам список сумм не является матрицей смежности. При необходимости после положительного ответа отдельно строят одну реализацию и проверяют исходные помеченные степени. Нулевые степени просто соответствуют изолированным вершинам. Наличие реализации не означает её единственности и не гарантирует связность без дополнительного условия.

Одинаковая чётность, разные ответы

Условие. Проверьте списки d=(4,4,3,3,1,1) и e=(4,4,4,1,1,0) по Эрдёшу—Галлаи. Для положительного ответа предъявите граф, для отрицательного — первый нарушенный префикс.

  1. У d сумма 16, у e сумма 14; обе чётные, максимальные степени допустимы для шести вершин. Эти первичные проверки не различают ответы.
  2. Для d левые суммы при k=1,…,6 равны 4,8,11,14,15,16. Правые границы равны 5,8,11,14,21,30. Все сравнения выполнены, три средних даже достигают равенства.
  3. Реализация d: полный граф на вершинах 1,2,3,4, затем рёбра 1—5 и 2—6. Степени первых четырёх становятся 4,4,3,3, двух последних — 1,1.
  4. Для e при k=1 получаем 4≤4, но при k=2 сумма 8 превышает 2+min(2,4)+min(2,1)+min(2,1)+min(2,0)=6. Это первый нарушенный префикс и универсальный отрицательный сертификат.

Ответ. d графичен, одна реализация содержит 8 рёбер. e не графичен: при k=2 требуется 8 инцидентностей при возможных не более 6.

Проверка. Независимый перебор всех 32768 простых графов на шести помеченных вершинах находит первую степень и не находит вторую. Проверка рёбер явно построенного K₄ с двумя листьями подтверждает все шесть исходных степеней.

Где легко ошибиться. Не включайте первые k степеней ещё раз в сумму внешних минимумов. Внутренние связи уже оценены членом k(k−1); двойной учёт может скрыть невозможность.

Проверьте понимание

Какова правая граница при k=2 для невозможного списка e=(4,4,4,1,1,0) из разбора?

Вопросы к этой главе

Почему одного нарушенного k достаточно для отказа?

Любая реализация обязана удовлетворять подсчёту связей для этой конкретной группы вершин. Если её потребность превышает даже универсальный верхний предел, другой выбор рёбер ситуацию не исправит.

Зачем проверять чётность, если есть все неравенства?

Неравенства не заменяют равенство суммы степеней удвоенному числу рёбер. Например, список из трёх единиц проходит соответствующие верхние ограничения, но имеет нечётную сумму и не реализуется.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Tripathi, Vijay — A note on a theorem of Erdős & Gallai, Theorem EG

    Условие графичности через чётность и префиксные неравенства. Нулевые степени можно отделить как изолированные вершины; оба шестичленных списка и реализация подготовлены независимо.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться