Таблицы Брадиса

Докажите, что можно заменить не

Докажите, что можно заменить не

Элементы математики в задачах - Г. А. Мерзон

Задача 16*. В полном неориентированном графе с не менее чем тре­мя вершинами на ребрах как-то расставили стрелки. Докажите, что можно заменить не более одной дуги на противоположную так, чтобы полученный граф стал сильно связным.

Определение 4. Количество дуг, входящих в вершину (ориентиро­ванного графа), называется входной полустепенью (или полустепе- нью захода) этой вершины. Количество выходящих дуг называется выходной полустепенью (или полустепенью исхода).

Задача 17. Найдите входные и выходные полустепени каждой вер­шины для всех графов из задачи 10.

Задача 18. Что можно сказать о сумме всех входных полустепеней и сумме всех выходных полустепеней одного и того же ориентирован­ного графа?

Задача 19. Сформулируйте и докажите критерий эйлеровости ори­ентированного графа.

Задача 20 (цикл де Брюина). Для того, чтобы открыть кодовый за­мок (с кнопками от 0 до 9), необходимо набрать код из четырех цифр, причем не важно, что было нажато до набора правильного кода. За какое наименьшее количество нажатий его можно гарантированно открыть?

Задача 21. 20 школьников решали 20 задач. Каждый решил ровно две задачи, и каждую задачу решили ровно двое. Докажите, что можно устроить разбор задач так, чтобы каждый рассказал одну решенную им задачу.

Определение 5. Граф называется двудольным, если его вершины можно разбить на две группы (называемые долями) так, чтобы все ребра (или дуги) были между различными долями.

Паросочетанием называется такой набор ребер графа, что каждая вершина графа является концом не более одного ребра из набора. Паросочетание называется совершенным., если каждая вершина явля­ется концом ровно одного ребра паросочетания.