Примеры заданий.

Бинарные отношения

  1. Сколько можно ввести отношений на множестве из $n$ элементов? Указание: такое отношение задаётся произвольной матрицей $n\times n$.
  2. Сколько можно ввести рефлексивных (другая версия задачи: антирефлексивных, симметричных, антисимметричных, асимметричных, одновременно симметричных и рефлексивных, симметричных и антисимметричных) отношений на множестве из $n$ элементов? Указание: в матрице отношения часть клеток могут быть произвольными, а часть — определяются однозначно.
  3. Некоторое отношение рефлексивно, симметрично и антисимметрично. Что это за отношение?
  4. Сколько можно ввести транзитивных отношений на множестве из 2 элементов? Указание: отношений на множестве из двух элементов всего 16.
  5. Отношение $\circeq$ задано на $\mathbb{Z}$: $x\circeq y$ если $x^3 \equiv y^3 \pmod 7$. Проверьте, что это отношение эквивалентности и определите его классы эквивалентности.
  6. Отношение $\propto$ задано на множестве слов $\{\mbox{ab}, \mbox{abc}, \mbox{abd}, \mbox{abce}, \mbox{abdf}\}$. Для двух слов $s_1$ и $s_2$ проверяется, что строка $s_1$ начинается на $s_2$. Например $\mbox{abc}\propto \mbox{ab}$ и $\mbox{abde}\propto \mbox{ab}$. Но $\cancel{\mbox{abc}\propto \mbox{abd}}$. Является ли это отношение отношением порядка? Строгого или нестрогого? Частичного или линейного? Выпишите все возможные способы топологически отсортировать элементы множества.
  7. На множестве $\mathbb{Z}_{13}$ задано отношение $x\ltimes y$, которое означает $x \equiv y+1 \pmod 13$. Найдите транзитивное замыкание этого отношения.

Неориентированный граф и основные понятия: вершины, рёбра, степень вершины, связность

Задачи про количество рёбер.

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

  1. Существует ли граф со степенями вершин 1, 1, 2, 4, 5, 5, 6? Если нет, то почему?
  2. Существует ли граф, у которого все степени вершин разные?
  3. Сколько рёбер в графе со степенями вершин 1, 1, 2, 2, 3, 3, 4, 4, 5, 5?
  4. В двудольном графе в левой и правой доле по 10 вершин. Степени всех вершин в левой доле равны 5. Степени всех вершин в правой доле тоже одинаковые. Какие? Подсказка: посчитайте количество ребер в графе.
  5. а) Докажите, что если в графе из $n$ вершин есть вершина степени $n-1$, то граф связен. б) Если в графе степени всех вершин больше $\frac{n}{2}$, то граф связен. Указание: возьмите две вершины и поймите, что между ними есть путь из 1 или 2 рёбер.
  6. Сколько рёбер может быть в связном графе из 10 вершин? Указание: больше всего рёбер в полном графе, а меньше всего в графе без циклов, иначе из цикла можно было бы убрать ребро, не нарушив связность.
  7. Сколько рёбер может быть в связном двудольном графе из 10 вершин? Указание: максимальное количество рёбер будет в полном двудольном графе, но надо разобраться, по сколько вершин должно быть в каждой доле, чтобы рёбер было как можно больше.
  8. Какое максимальное количество рёбер будет в несвязном графе из 10 вершин?
  9. (*) Постройте двудольный граф, в котором по 57 вершин в каждой доле, степени всех вершин равны 8, для любых двух разных вершины из левой доли есть ровно одна вершина из правой доли, с которой они обе соединены.

Планарные графы.

Про планарные графы мы знаем формулу Эйлера, у неё есть два варианта: основной для связных графов и более общая формула, если известно количество компонент связности. Из этой формулы следует неравенство $m \le 3n-6$, если $n \ge 3$.

  1. Как известно, футбольный мяч имеет форму усеченного икосаэдра. В усечённом икосаэдре 12 граней — пятиугольники, 20 граней — шестиугольники. Сколько у него вершин? Проверить ответ можно в википедии. Указание: мы обсуждали, что для многогранников работает ровно та же самая формула Эйлера, что и для планарных графов.
  2. В планарном графе все грани ограничены тремя рёбрами. Проверьте, что $3f=2m$, где $f$ и $m$ — это граней и рёбер соответственно. Нарисуйте пример такого графа из 5 вершин. А если у такого графа 100 вершин, сколько в нём ребер?
  3. (*) Докажите, что если планарный граф двудолен, количество вершин хотя бы 3, то для него справедливо неравенство $m \le 2n-4$. Указание: в двудольном графе циклы четные, т.е. они имеют длину хотя бы 4, а не 3, как предполагалось при выводе первой формулы.

Деревья

  1. Волейбольная сетка имеет вид прямоугольника размером $5\times10$ клеток. Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски? Указание: это же задача про дерево.
  2. У Царя Гвидона было 5 сыновей. Среди его потомков 100 имели каждый ровно по 3 сына, а остальные умерли бездетными. Сколько потомков было у царя Гвидона?

Хроматические числа и многочлены

  1. Может ли хроматический многочлен графа быть равен $k^4 - 7k^3 + 10k^2 - 8k$?
  2. Постройте граф, у которого хроматический многочлен $k^4 - 5k^3+8k^2-4k$.
  3. Чему равно хроматическое число графа $C_n$, т.е. цикла из $n$ вершин?
  4. а) Придумайте граф с хроматическим числом 3, но чтобы он не содержал треугольник из рёбер. б) А еще придумайте граф с хроматическим числом 4, но чтобы он не содержал полный подграф из четырёх вершин.
  5. А может хроматический многочлен быть равен $(k-1)^n$?
  6. Хроматический многочлен связного графа имеет вид $k^n - nk^{n-1} + \cdots$. Докажите, что он равен $(k-1)^{n-c}((k-1)^c + (-1)^c{k-1})$ для некоторого $3\le c \le n$.

Длины путей в графах

  1. Нарисуйте дерево из 10 вершин диаметра 3.
  2. Какое максимальное количество рёбер может быть в графе диаметра 2?

Потоки в сетях, максимальное паросочетание

  1. В графе из вершины $s$ идут рёбра в вершины $u_i$, где $1 \le i \le n$. Пропускные способности рёбер равны $c_i$. Из вершин $u_i$ идут ребра в вершину $t$. Их пропускные способности равны $d_i$. Запишите формулой величину максимального потока в такой сети. А как устроен минимальный разрез в такой сети?
  2. Граф сети имеет четыре вершины $s$, $t$, $u$, $v$. Он содержит рёбра $s-u$ с пропускной способностью $x$, $u-v$ с пропускной способностью $y$, $v-u$ с пропускной способностью $y$, $v-t$ с пропускной способностью $x$. Как устроен максимальный поток в этой сети в зависимости от значений $x$, $y$? Как выглядит минимальный разрез? Опишите все максимальные потоки в этой сети.
  3. Придумайте двудольный граф с долями по 4 вершины, в котором 5 рёбер, а максимальное паросочетание состоит из двух рёбер. Сколько максимально может быть рёбер в таком графе (4 + 4 вершины, паросочетание размера 2)? (Указание: максимальное контроллирующее множество должно содержать 2 вершины).
  4. Придумайте сеть с максимальным потоком 4, в нём 10 ребер, все рёбра имеют пропускную способность 1.

Поиски в глубину и ширину, связанные алгоритмы

  1. Может ли в некотором графе совпадать прямая и обратная нумерация при поиске в глубину?
  2. Как выглядит дерево обхода в глубину (напомню, оно состоит из тех рёбер графа, по которым прошел поиск) в полном неориентированном графе?