Решение задачи 358

Доказательство:

1. Связность и ацикличность.

   • Связность бинарного отношения означает, что для любых $a$ и $b$ либо $a \leq b$, либо $b \leq a$, либо $a = b$.
   • Ацикличность означает, что в бинарном отношении нет циклов: если $a \leq b$ и $b \leq c$, то $c \nleq a$.

2. Переходность.

   • Связность гарантирует, что для любых двух элементов существует отношение.
   • Ацикличность добавляет свойства переходности: если $a \leq b$ и $b \leq c$, то $a \leq c$, так как иначе мы получаем цикл.

3. Антисимметричность.

   • Если $a \leq b$ и $b \leq a$, то из ацикличности следует, что $a = b$.

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

---

Решение задачи 359

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

1. Описание графа.
   • Граф состоит из $n$ вершин (городов), где каждые две вершины соединены ребром.
   • Требуется установить одностороннее движение, чтобы ни один цикл не существовал. Это эквивалентно требованию, чтобы граф стал ориентированным ацикличным графом (DAG).

Пункт (а): Возможность установить одностороннее движение.

• Доказательство:
  • Для ацикличности достаточно задать линейный порядок на вершинах (например, упорядочить города как $v_1, v_2, \dots, v_n$).
  • Направим каждую дорогу $(v_i, v_j)$ так, чтобы $v_i \to v_j$, если $i < j$. Таким образом, получается направленный граф без циклов.

Пункт (б): Город, из которого можно добраться до всех, и город, в который нельзя выехать.

• В полученном DAG-графе:
  • Город с минимальным номером в линейном порядке ($v_1$) будет иметь только исходящие дороги, и до него нельзя добраться.
  • Город с максимальным номером в линейном порядке ($v_n$) будет иметь только входящие дороги, и из него нельзя выехать.

Пункт (в): Единственный путь, проходящий через все города.

• Линейный порядок на вершинах ($v_1 \to v_2 \to \dots \to v_n$) задаёт единственный возможный путь, который проходит через все вершины графа.

Пункт (г): Сколькими способами можно осуществить намерение?

• Число способов задания линейного порядка на $n$ городах равно $n!$, так как для каждого линейного порядка можно задать одностороннее движение, используя порядок вершин.

---

Итог:

1. Одностороннее движение можно установить.
2. В DAG-графе найдутся города с только входящими или только исходящими дорогами.
3. Существует единственный путь, проходящий через все города.
4. Число способов равно $n!$.

---

Дополнительные вопросы:

1. Как связаны свойства линейного порядка и ацикличности графа?
2. Что произойдёт, если граф будет несвязным? Будет ли решение задач корректным?
3. Можно ли в задаче 359 исключить дороги и как это повлияет на решение?
4. Каким образом можно использовать топологическую сортировку для проверки решений?
5. Как доказать, что для любого полного графа всегда можно установить направление без цикла?

Совет: Для задач с графами и порядком полезно визуализировать графы с помощью топологической сортировки,