Банк задач по математике

Задача 2.5.1

(1)(2)

Сколько всего мультиграфов с данными $n$ вершинами

?

(1)

ориентированных без кратных рёбер, но, возможно, с петлями?

(2)

неориентированных без петель, но, возможно, с кратными рёбрами?

Примечание.

?

Мультиграфом (или графом с петлями и кратными рёбрами) называется квадратная таблица из целых неотрицательных чисел, симметричная относительно главной диагонали. При этом число, стоящее на пересечении $i$ -й строки и $j$ -го столбца, интерпретируют как число рёбер (или кратность ребра) между вершинами с номерами $i$ и $j$ при $i \neq j$ и как число петель в вершине с номером $i$ при $i = j$ . Ребро называется кратным, если его кратность больше единицы.

Ориентированным мультиграфом (или ориентированным графом с петлями и кратными рёбрами) называется квадратная таблица из целых неотрицательных чисел. Если в некоторой клетке (неважно, диагональной или нет) стоит число, большее 1, то говорят, что ориентированный мультиграф имеет кратные рёбра.

Задача 2.5.2

(1)(2)

Сколько всего мультиграфов с данными $n$ вершинами, имеющих $k$ рёбер и

?

(1)

неориентированных без петель и кратных рёбер?

(2)

неориентированных, у которых допускаются кратные рёбра и петли?

Задача 2.5.3

Эйлеров цикл (путь) в мультиграфе — цикл (путь), проходящий по каждому ребру мультиграфа ровно один раз.

?

(1)

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

(2)

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

(3)

При каком условии в мультиграфе существует эйлеров путь?

(4)

При каком условии в ориентированном мультиграфе существует ориентированный эйлеров цикл?

(5)

При каких $n$ граф $K_{n}$ имеет эйлеров цикл?

(6)

То же для графа $K_{m,n}$ .

Задача 2.5.4

(1)(2)(3)(4)

?

(1)

Если количество вершин нечётной степени в связном графе равно $2k$ , то множество его рёбер можно представить в виде объединения $k$ путей, ни один из которых не проходит ни по какому ребру дважды и никакие два из которых не имеют общих рёбер.

(2)

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

(3)

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

(4)

В нарисованном на плоскости без самопересечений связном графе есть эйлеров цикл тогда и только тогда, когда грани можно раскрасить в 2 цвета правильно, т.е. так, что при переходе через каждое ребро цвет меняется.

Примечание.

?

Входящей степенью вершины ориентированного мультиграфа называется число входящих в нее рёбер (с учётом кратности). Аналогично определяется исходящая степень. При этом петля кратности $k$ «вносит вклад» $k$ и во входящую, и в исходящую степень.

Задача 2.5.5

(1)(2)(3)

Математик забыл трёхзначный код своего замка́. Замок открывается, если три цифры кода набраны подряд (даже если перед этим были набраны другие цифры). Математик набирает одну цифру в секунду; набранная цифра добавляется в конец. Докажите, что математик сможет открыть замок за

?

(1)

29 секунд, если в коде могут быть использованы только цифры 1, 3 и 7;

(2)

1002 секунды, если в коде могут быть использованы десять цифр.

(3)

Сформулируйте и докажите правило « $0 < 1 < 2 < \ldots < 8 < 9$ » открытия замка за 1002 секунды.

Примечание.

?

Последовательность де Брёйна (П.д.Б.) с параметрами $n$ и $k$ — последовательность, элементы которой принадлежат заданному множеству из $k$ элементов (обычно — $\{ 0,1,\ldots ,k-1\}$ ), причём все её подпоследовательности длины $n$ различны и среди этих подпоследовательностей встречаются все $k^{n}$ возможных последовательностей. (Таким образом, длина П.д.Б. равна $k^{n}+n-1$ .)

(Также П.д.Б. называют бесконечную периодическую последовательность с периодом $k^{n}$ , каждая подпоследовательность которой длины $k^{n}+n-1$ является П.д.Б. с параметрами $n$ и $k$ .)

Задача 2.5.6

(1)(2)(3)

Постройте последовательность де Брёйна с параметрами $k=2$ («двоичную») и

?

(1)

$n=3$ , начинающуюся с 111;

(2)

$n=4$ , начинающуюся с 1011;

(3)

$n=4$ , заканчивающуюся на 1010.

Задача 2.5.7

Рассмотрим последовательность из нулей и единиц, построенную по следующим правилам. Она начинается с $k$ единиц. Дальше мы пишем 1, только если при написании 0 не все подпоследовательности длины $k$ новой последовательности различны. Если даже при написании 1 не все подпоследовательности длины $k$ новой последовательности различны, то заканчиваем написание последовательности. Докажите, что таким образом получится последовательность де Брёйна.

?

Задача 2.5.8

(1)(2)(3)

Дан связный ориентированный мультиграф с $n$ вершинами. Входящая степень $d_{k}$ каждой вершины $k$ равна исходящей.

?

(1)

Существует дерево, содержащее все вершины этого мультиграфа, все рёбра которого направлены в сторону вершины 1.

(2)

Фиксируем дерево $T$ из п. (1). Будем обходить этот граф (по стрелкам), проходя по каждому ребру не более одного раза. Сначала выйдем из вершины 1 в произвольном направлении. Далее, пусть мы пришли в некоторую вершину $v$ . Выходим из нее по любому ребру, не принадлежащему $T$ , если это возможно. А если невозможно, то выходим из нее по ребру, принадлежащему $T$ (такое ребро единственно). Докажите, что движение закончится в вершине 1 и что в результате получится ориентированный эйлеров цикл.

(3)

Число ориентированных эйлеровых циклов в этом мультиграфе кратно числу $(d_{1}-1)! \cdot \ldots \cdot (d_{n}-1)!$ .

Эйлеровы пути и циклы