Изменения
Нет описания правки
= Дискретная математика, 1 семестр =
Задания, помеченные 🤔 - задания повышенной сложности. Задания, помеченные 😱 - задания очень высокой сложности. ✋ помечены задания, где мы передаем привет курсу "Алгоритмы и структуры данных", 💩 👻 - задания только для групп M3132-M3135.
# Пусть $<math>R$ </math> и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.
# Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение?
# Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?
# Докажите, что биномиальный коэффициент $C_n^k$ нечетен тогда и только тогда, когда в двоичной записи $k$ единицы стоят только на тех позициях, где в двоичной записи $n$ также находятся единицы (иначе говоря, двоичная запись $k$ доминируется двоичной записью $n$ как двоичным вектором).
# Докажите "метод треугольника" построения полинома Жегалкина по таблице истинности.
# Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.# Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.# Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов и глубиной $O(\log n)$.# Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$# Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.# Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.# Мультиплексором называется схема, которая имеет $2^n+n$ входов и один выход. Обозначим входы как $x_0, x_1, \ldots, x_{2^n-1}, y_0, y_1, \ldots, y_{n-1}$. На выход подается то же, что подается на вход $x_i$, где $i$ - двоичное число, которое кодируется входами $y_0, \ldots, y_{n-1}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для мультиплексора.# Дешифратором называется схема, которая имеет $n+1$ входов и $2^n$ выходов. Обозначим входы как $y_0, y_1, \ldots, y_{n-1}, x$, а выходы как $z_0, z_1, \ldots, z_{2^n-1}$. На все выходы подается 0, а на выход $z_i$ то же, что подается на вход $x$, где $i$ - двоичное число, которое кодируется входами $y_0, \ldots, y_{n-1}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для # Игра "два шага вперед, один назад". Задана булева функция от $n$ аргументов $f(x_1, \ldots, x_n)$. Играют два игрока: 0 и 1. Игроки делают ходы по очереди. Для хода используется вспомогательное значение $m$, исходно равное 0, кроме того исходно все значения переменных не определены. Ход заключается в следующем. Игрок либо увеличивает $m$ на 2, либо уменьшает на 1. После этого действия значение $m$ должно удовлетворять неравенству $1 \le m \le n$. Затем, если значение $x_m$ не определено, то игрок присваивает переменной $x_m$ значение на свое усмотрение. Если же значение $x_m$ определено, то оно меняется на противоположное. Игра заканчивается, когда все значения определены. Если значение функции $f$ на получившемся наборе переменных равно 1, то выигрывает 1, иначе выигрывает 0. Проанализируйте описанную игру для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ лексикографически строго меньше строки $x_nx_{n-1}\ldots x_1$.# Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)= 💩 💩 💩 💩 https:x_1\oplus x_2\oplus \ldots\oplus x_n$.# Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ не содержит двух единиц подряд.# Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ представляет собой (возможно дополненную ведущими нулями) двоичную запись простого числа.дешифратора.# Докажите, что не существует схемы константной глубины для сложения.# На одном <strike>китайском</strike> заводе в матричном умножителе случайно использовали элементы "или" вместо "и". Можно ли из получившихся значений получить произведение исходных чисел (доступа к входам нет, есть только доступ к $n\times n$ выходам матричного псевдоумножителя).# Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами''). Зафиксируем некоторые значения переменным. Тогда ''замкнутыми'' называются ребра, на которых записана 1, ребра, на которых записан 0, называются ''разомкнутыми''. Зафиксируем две вершины $u$ и $v$. Тогда контактная схема вычисляет некоторую функцию $f$ между вершинами $u$ и $v$, равную 1 на тех наборах переменных, на которых между $u$ и $v$ есть путь по замкнутым ребрам. Постройте контактные схемы для функций "и", "или" и "не".# Постройте контактную схему для функции "xor".# Постройте контактную схему для функции медиана трех.# Докажите, что любую булеву функцию можно представить контактной схемой.# Постройте контактную схему "xor от $n$ переменных", содержащую $O(n)$ ребер.# Постройте контактную схему "большинство из $2n+1$ переменных", содержащую $O(n)$ ребер.# Постройте контактную схему, в которой для каждого из $2^n$ наборов дизъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта дизъюнкция, используя $O(2^n)$ ребер.# Докажите, что любую булеву функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер.# 👻 По числам $l_1, l_2, \ldots, l_n$, удовлетворяющим неравенству $\sum\limits_{i=1}^n 2^{-l_i} \le 1$, постройте префиксный код с таким набором длин кодовых слов.# Как выглядит дерево Хаффмана для частот символов $1, 2, ..., 2^{n-1}$ (степени двойки) ?# Как выглядит дерево Хаффмана для частот символов $1, 1, 2, 3, ..., F_{n-1}$ (числа Фибоначчи)?# Докажите, что если размер алфавита - степень двойки и частоты никаких двух символов не отличаются в 2 или более раз, то код Хаффмана не лучше кода постоянной длины# Модифицируйте алгоритм Хаффмана, чтобы строить $k$-ичные префиксные коды# Укажите, как построить дерево Хаффмана за линейное время, если символы уже отсортированы по частоте# Предложите алгоритм построения оптимального кода среди префиксных кодов с длиной кодового слова не более L бит# Предложите способ хранения информации об оптимальном префиксном коде для n-символьного алфавита, использующий не более $2n - 1 + n \lceil\log_2(n)\rceil$ бит ($\lceil x\rceil$ - округление $x$ вверх)# Можно ли разработать алгоритм, который сжимает любой файл не короче заданной величины $N$ хотя бы на 1 бит?# Приведите пример однозначно декодируемого кода оптимальной длины, который не является ни префиксным, ни развернутым префиксным# Для каких префиксных кодов существует строка, для которой он является кодом Хаффмана? Предложите алгоритм построения такой строки.# Пусть заданы пары $(u_i, v_i)$. Предложите полиномиальный алгоритм проверки, что существует код Хаффмана для некоторой строки, в котором $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц.# Докажите, что если в коде Хаффмана для некоторой строки $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц, то для многочлена от двух переменных $f(x, y) = \sum_{i=1}^n x^{u_i}y^{v_i}$ выполнено $f(x, y) - 1 = (x + y - 1) g(x, y)$ для некоторого многочлена $g(x, y)$.# При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?# При арифметическом кодировании трудным моментом является деление отрезка в пропорциях, не являющихся степенями двойки. Рассмотрим модификацию арифметического кодирования, когда соотношения между символами приближаются дробями со знаменателями - степенями двойки. Что можно сказать про получившийся алгоритм?# Проанализируйте время работы алгоритма арифиметического кодирования# Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в $c$ раз лучше Хаффмана# Докажите, что при оптимальном кодирование с помощью LZ77 не выгодно делать повтор блока, который можно увеличить вправо# Верно ли утверждение из предыдущего задания при кодировании с помощью L78?# Разработайте алгоритм оптимального кодирования текста с помощью LZ77, если на символ уходит $c$ бит, а на блок повтора $d$ бит# Предложите семейство строк $S_1, S_2, \ldots, S_n, \ldots$, где $S_i$ имеет длину $i$, таких, что при их кодировании с помощью LZW длина строки увеличивается. Начальный алфавит $\{0, 1\}$.# Предложите алгоритм декодирования кода Барроуза-Уиллера.# Предложите алгоритм декодирования кода Барроуза-Уиллера за $O(n)$.# Предложите реализацию преобразования Move to Front за $O(n \log n)$.# Предложите реализацию преобразования Move to Front за $O(n)$.# Докажите, что $n$-битный код, исправляющий одну ошибку содержит не более, чем $2^n/vk(n+1)$ кодовое слово.com# Обобщите оценку из предыдущего задания на код, исправляющий $k$ ошибок.# Разработайте оптимальный код исправляющий одну ошибку при пересылке 2 битов# Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов# Разработайте оптимальный код исправляющий одну ошибку при пересылке 4 битов# Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2^n$ символьного алфавита (для $n > n_0$)# Докажите, что в зеркальном коде Грея $g_i = i \oplus \lfloor i /eatmoar 💩 💩 💩 💩 2\rfloor$# Докажите, что в зеркальном коде Грея при переходе от $g_i$ к $g_{i+1}$ меняется тот же бит, который меняется с 0 на 1 при переходе от $i$ к $i+1$# Разработайте код Грея для k-ичных векторов# При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз?# При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз, а в конце возвращается в исходную ячейку?# Код "антигрея" - постройте двоичный код, в котором соседние слова отличаются хотя бы в половине бит# Троичный код "антигрея" - постройте троичный код, в котором соседние слова отличаются во всех позициях# При каких $n$ и $k$ существует двоичный $n$-битный код, в котором соседние кодовые слова отличаются ровно в $k$ позициях?# Докажите, что для достаточно больших $n$ существует код Грея, который отличается от любого, полученного из зеркального перестановкой столбцов, отражением и циклическим сдвигом строк# 🤔 Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея# Факториальная система счисления. Рассмотрим систему счисления, где бесконечно много цифр, в $i$-м разряде (нумерация разрядов с 1 от младшего к старшему) разрешается использовать цифры от 0 до $i$, вес $i$-го разряда $i!$. Докажите, что у каждого положительного числа ровно одно представление в факториальной системе счисления (с точностью до ведущих нулей). Предложите алгоритм перевода числа в факториальную систему счисления.# Как связана факториальная система счисления и нумерация перестановок?# Фибоначчиева система счисления. Рассмотрим систему счисления, где есть две цифры, 0 и 1. Пусть нумерация разрядов ведется с 1 от младшего к старшему, вес $i$-го разряда $F_i$, где $F_i$ - $i$-е число Фибоначчи ($F_0 = 1$, $F_1 = 1$, нулевой разряд не используется). При этом запрещается исползовать две единицы в соседних разрядах. Сколько представлений в Фибоначчиевой системе счисления у положительного числа $x$? Предложите алгоритм перевода числа в фибоначчиеву систему счисления.# Свяжите фибоначчиеву систему счисления с нумерацией каких-либо комбинаторных объектов.# Выведите рекуррентную формулу для числа комбинаторных объектов: вектор длины $2n$, в котором каждое число от $1$ до $n$ встречается ровно два раза.# Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).# Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.# Коды Грея для размещений. Предложите способ перечисления размещений, в котором соседние размещения отличаются заменой одного элемента в одной позиции.# Докажите, что $C_r^mC_m^k=C_r^kC_{r-k}^{m-k}$.# Докажите, что $\sum_{k=0}^n C_{m+k}^k=C_{m+n+1}^n$.# Докажите, что $\sum_{k=0}^n C_r^kC_s^{n-k}=C_{r+s}^n$.# Для решения этой и следующих задач вам понадобится понятие чисел Каталана. Числом Каталана $C_n$ называется количество правильных скобочных последовательностей с $n$ открывающимися скобками. Докажите, что $C_n = \sum_{i=0}^{n-1}C_iC_{n-i-1}$.# Докажите, что число Каталана $C_n = \frac{1}{n+1}C_{2n}^n$.# Докажите, что число различных триангуляций правильного $n$-угольника равно числу Каталана. В этом и нескольких следующих заданиях номер соответствующего числа Каталана может отличаться от $n$, требуется также установить соответствие между размером задачи и номерами чисел Каталана.# Докажите, что число двоичных деревьев с $n$ вершинами равно числу Каталана.# Докажите, что число подвешенных деревьев с порядком на детях с $n$ вершинами равно числу Каталана.# Будем называть последоватедовательность ''сортируемой стеком'', если ее можно отсортировать, используя в произвольном порядке следующие операции: (а) взять первый элемент входной последовательности и положить в стек (б) взять верхний элемент стека и отправить в конец выходной последовательности. Докажите, что число перестановок $n$ элементов, сортируемых стеком, равно число Каталана. # Докажите, что число перестановок $n$ элементов, в которых нет возрастающей последовательности длины 3, равно числу Каталана.# Докажите, что число способов расставить числа от 1 до $2n$ в прямоугольник $2 \times n$, чтобы числа в каждой строке и каждом столбце возрастали, равно числу Каталана.# Матрица Ханкеля - матрица $n \times n$, такая что $a[i][j] = C_{i+j-2}$. Докажите, что определитель матрицы Ханкеля равен 1.# В этом и последующих заданиях необходимо подробно изложить алгоритм вычисления числа комбинаторных объектов с таким префиксом, чтобы можно было получить объект по номеру и номер по объекту. Получение объекта по номеру и номера по объекту для правильных скобочных последовательностей с одним типом скобок.# Получение объекта по номеру и номера по объекту для правильных скобочных последовательностей с двумя типами скобок.# Укажите способ подсчитать число разбиений заданного $n$-элементного множества на $k$ упорядоченных непустых подмножеств (например, для $n = 3$, $k = 2$ есть следующие разбения: $\{[1], [2, 3]\}$, $\{[1], [3, 2]\}$, $\{[1, 2], [3]\}$, $\{[1, 3], [2]\}$, $\{[2, 1], [3]\}$, $\{[2], [3, 1]\}$.# Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами# Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками# Чему равно число перестановок с заданным циклическим классом?# Степенью перестановки $\pi$ называется минимальное $k$, такое что $\pi^k=i$, где $i$ - тождественная перестановка. Как связана степень перестановки с ее циклическим классом?# Предложите алгоритм поиска перестановки из $n$ элементов с максимальной степенью за $O(n^3)$.# Рассмотрим коды Грея для перестановок и коды Грея для их таблиц инверсий. Есть ли между ними связь?# Докажите, что минимальное число невозрастающих подпоследовательностей, на которые можно разбить заданную последовательность, равно длине ее наибольшей возрастающей подпоследовательности# Докажите, что произведение длины наибольшей возрастающей подпоследовательности и наибольшей убывающей подпоследовательности перестановки не меньше $n$# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетные слагаемые# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетное число слагаемых# Выведите рекуррентную формулу для числа разбиений числа $n$ на различные слагаемые # Предложите алгоритм подсчета количества разбиений числа $n$ на слагаемые за $O(n\sqrt{n})$.# Выведите рекуррентную формулу для числа разбиений числа $a+ib$, где $a$ и $b$ целые неотрицательные числа, на комплексные слагаемые вида $c + id$, где $c$ и $d$ целые неотрицательные числа, хотя бы одно из которых положительно.# Раскрашенные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые раскрашенным, если каждому слагаемому сопоставлен один из $k$ заданных цветов. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа раскрашенных разбиений числа $n$ на слагаемые# Разноцветные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые разноцветным, если каждому слагаемому сопоставлен один из $k$ заданных цветов, причем одинаковым числам в разбиении не сопоставляются одинаковые цвета. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа разноцветных разбиений числа $n$ на слагаемые# Приведите другое доказательство формулы включения-исключения на базе формулы $\sum_{i=1}^n (-1)^i C_n^i = -1$.# Сколько существует чисел, не превышающих $n$, которые взаимно просты с числом $n$?# Докажите, что $\max(x_1, \ldots , x_n)$ = $\sum_{i} x_i - \sum_{i < j} \min(x_i, x_j) +$ $\sum_{i < j < k} \min(x_i, x_j, x_k) + \ldots + (-1)^{n-1} \min(x_1, \ldots , x_n)$# Формула обращения Мёбиуса. Пусть $S$ — конечное множество, и пусть $f \colon 2^S \to \mathbb{R}$ — произвольная функция, определенная на совокупности подмножеств $S$ и принимающая вещественные значения. Определим функцию $g \colon 2^S \to \mathbb{R}$ следующим соотношением: $g(Y) = \sum_{X \supseteq Y} f(X)$. Докажите, что $f(Y) = \sum_{X \supseteq Y} (-1)^{|X| - |Y|} \, g(X)$.# Чему равно число сюрьекций из $n$-элементного множества в $m$-элементное?# Сколько существует пар взаимно-простых чисел от $1$ до $n$?# Выведите формулу для числа ожерелий из $n$ бусинок $k$ цветов с точностью до циклического сдивига и отражения.# Выведите формулу для числа раскрасок прямоугольника $n \times m$ в $k$ цветов с точностью до отражения относительно горизонтальной и вертикальной оси.# Выведите формулу для числа раскрасок граней тетраэдра в $k$ цветов с точностью до любого поворота в 3D.# Выведите формулу для числа раскрасок ребер тетраэдра в $k$ цветов с точностью до любого поворота в 3D.# Выведите формулу для числа раскрасок граней куба в $k$ цветов с точностью до любого поворота в 3D.# Выведите формулу для числа раскрасок ребер куба в $k$ цветов с точностью до любого поворота в 3D.# Выведите формулу для числа раскрасок граней октаэдра в $k$ цветов с точностью до любого поворота в 3D.# Почему мы не сделали задачу про вершины тетраэдра, вершины куба, вершины и ребра октаэдра? Неужели оставили на контрольную?# Раскрашенные деревья. Выведите формулу для числа подвешенных деревьев с $n$ вершинами без порядка на детях, раскрашенных в $k$ цветов.# Раскрашенные деревья. Выведите формулу для числа подвешенных деревьев с $n$ вершинами с порядком на детях, раскрашенных в $k$ цветов.# Коды Прюфера. Рассмотрим процедуру для помеченного неподвешенного дерева. Будем по очереди выбирать лист, помеченный минимальным числом и удалять его из дерева, выписывая число в вершине, с которой он был связан. Таким образом будет выписано $n - 1$ число, последнее выписанное число всегда $n$. Докажите, что различным деревьям соответствуют различные коды Прюфера.# Докажите, что любой код Прюфера соответствует некоторому дереву. Предложите алгоритм восстановления дерева по коду Прюфера. Сделайте вывод о числе помеченных неподвешенных деревьев с $n$ вершинами.# Пусть 2 - множество из двух различных элементов, каждый из которых имеет вес 1. Можно условно называть их черный и белый. Что представляет собой $Seq(2)$? Посчитайте число элементов для него, в зависимости от веса.# Что представляет собой $Set(2)$? Посчитайте число элементов для него, в зависимости от веса.# Что представляет собой $MSet(2)$? Посчитайте число элементов для него, в зависимости от веса.# Что представляет собой $Cycle(2)$? Посчитайте число элементов для него, в зависимости от веса.# Пусть $F$ - множество из двух различных элементов, один из которых имеет вес 1, а другой - 2. Можно условно называть их маленький и большой. Что представляет собой $Seq(F)$? Посчитайте число элементов для него, в зависимости от веса.# Что представляет собой $Set(F)$? Посчитайте число элементов для него, в зависимости от веса.# Что представляет собой $MSet(F)$? Посчитайте число элементов для него, в зависимости от веса.# Что представляет собой $Cycle(F)$? Посчитайте число элементов для него, в зависимости от веса.# Пусть $A$ - комбинаторные объекты. Выведите формулу для числа элементов в зависимости от веса для $Pair(Seq(A), Seq(A))$.# Пусть $A$ - комбинаторные объекты. Обозначим как $Seq^+(A)$ множество непустых последовательностей из элементов $A$. Выведите рекуррентную формулу для числа элементов в зависимости от веса для $Seq^+(Seq^+(A))$.# Пусть $A$ - комбинаторные объекты. Обозначим как $Seq^1(A) = Seq^+(A)$, $Seq^k(A) = Seq^+(Seq^{k-1}(A))$. Выведите рекуррентную формулу для числа элементов в зависимости от веса для $Seq^k(A)$.# Разбиения на множества. Проинтерпретируйте разбиения $n$-элементного множества на $k$ множеств как конструируемый помеченный комбинаторный объект. Получите альтернативную рекуррентную формулу для чисел Стирлинга 2 рода.# Разбиения на циклы. Проинтерпретируйте разбиения $n$-элементного множества на $k$ циклов как конструируемый помеченный комбинаторный объект. Получите альтернативную рекуррентную формулу для чисел Стирлинга 1 рода.# Будем называть граф циклическим мультибамбуком, если он устроен следующим образом: есть цикл, из каждой вершины которого выходит путь. Предложите способ посчитать непомеченные циклические мультибамбуки.# Предложите способ посчитать помеченные циклические мультибамбуки.# Подсчет помеченных унициклических графов. Граф называется унициклическим, если он содержит ровно один цикл. Предложите способ подсчета помеченных унициклических графов.# Подсчет помеченных двудольных графов. Граф называется двудольным, если его вершины можно разбить на два множества, таких что ребра соединяют только вершины различных множеств. Сколько существует помеченных двудольных графов?# Подсчет помеченных связных двудольных графов. Сколько существует помеченных связных двудольных графов? = ЭТО КОНЕЦ =
