2. В графе, показанном на рисунке, цепь ACDG имеет длину 3. а) Найдите цепь длины 4, которая соединяет вершину В с вершиной А. б) Сколько в этом графе цепей длины 5, которые соединяют вершину А с вершиной В?

Решение:

а) Цепь длины 4, соединяющая вершины В и А:

Цепь — это последовательность вершин, где каждая следующая вершина соединена с предыдущей ребром, и вершины не повторяются.

Рассмотрим возможные пути от В к А:

• В → G → D → C → A (длина 4)
• В → G → D → A (длина 3)
• В → A (длина 1)
• B → E → D → C → A (длина 4)
• B → E → D → A (длина 3)

Ответ: Цепь длины 4, соединяющая вершины В и А, — это B → G → D → C → A или B → E → D → C → A.

б) Количество цепей длины 5, соединяющих вершины А и В:

Ищем пути длины 5, где вершины не повторяются.

Возможные цепи:

• A → D → C → G → B (длина 4)
• A → D → E → B (длина 3)
• A → C → D → G → B (длина 4)
• A → C → D → E → B (длина 4)
• A → D → E → B (длина 3)
• A → C → D → E → B (длина 4)
• A → B (длина 1)
• A → D → C → G → B (длина 4)
• A → E → D → C → G → B (длина 5)
• A → C → D → E → B (длина 4)
• A → D → G → C → D → E → B (это не цепь, вершина D повторяется)
• A → D → C → D → E → B (это не цепь, вершина D повторяется)
• A → C → D → G → B (длина 4)
• A → E → D → G → B (длина 4)
• A → D → C → G → B (длина 4)
• A → C → D → E → B (длина 4)
• A → D → E → B (длина 3)
• A → E → D → B (длина 3)
• A → D → C → D → E → B (не цепь)
• A → E → D → C → G → B (длина 5)
• A → C → G → D → E → B (длина 5)

Найдем все возможные цепи:

1. A → D → C → G → B (длина 4)
2. A → D → E → B (длина 3)
3. A → C → D → G → B (длина 4)
4. A → C → D → E → B (длина 4)
5. A → E → D → C → G → B (длина 5)
6. A → E → D → G → B (длина 4)
7. A → C → G → D → E → B (длина 5)
8. A → G → D → E → B (длина 4)

Всего найдено 2 цепи длины 5.

Ответ: 2.