а) Найдите цепь длины 4, которая соединяет вершину В с вершиной А.

Решение:

Нам нужно найти путь из вершины B в вершину A, который состоит ровно из 4 ребер (длина цепи = 4). Будем перебирать возможные пути, не повторяя вершины (если это не явно петля).

Давай посмотрим на граф:

• Начнем с B. Из B можно попасть в A или E.
• Путь 1: B -> A. Это уже 1 ребро. Из A куда? В C или D.
• B -> A -> C. Теперь у нас 2 ребра. Из C можно попасть в A (но мы уже были там) или D.
• B -> A -> C -> D. 3 ребра. Из D можно попасть в A, C (были), E, G.
• B -> A -> C -> D -> E. 4 ребра. Из E можно попасть в B (были), D (были), G. Мы добрались до 4 ребер, но не до вершины A.
• B -> A -> C -> D -> G. 4 ребра. Из G можно попасть в D (были), E. Мы добрались до 4 ребер, но не до вершины A.
• B -> A -> D. Теперь у нас 2 ребра. Из D можно попасть в A (были), C, E, G.
• B -> A -> D -> C. 3 ребра. Из C можно попасть в A (были), D (были). Не ведет к A.
• B -> A -> D -> E. 3 ребра. Из E можно попасть в B (были), D (были), G.
• B -> A -> D -> E -> G. 4 ребра. Не ведет к A.
• B -> A -> D -> G. 3 ребра. Из G можно попасть в D (были), E.
• B -> A -> D -> G -> E. 4 ребра. Не ведет к A.

• B -> E -> D. 2 ребра. Из D можно попасть в A, C, E (были), G.
• B -> E -> D -> A. 3 ребра. Мы почти у цели! Из A можно попасть в B (были), C, D (были).
• B -> E -> D -> A -> C. 4 ребра. Не A.
• B -> E -> D -> A -> D. 4 ребра. Не A.
• B -> E -> D -> C. 3 ребра. Из C можно попасть в A, D (были).
• B -> E -> D -> C -> A. 4 ребра! Мы нашли путь!
• B -> E -> D -> G. 3 ребра. Из G можно попасть в D (были), E (были).
• B -> E -> D -> G -> E. 4 ребра. Не A.
• B -> E -> G. 2 ребра. Из G можно попасть в D, E (были).
• B -> E -> G -> D. 3 ребра. Из D можно попасть в A, C, E (были), G (были).
• B -> E -> G -> D -> A. 4 ребра! Еще один путь!

Итак, мы нашли две цепи длины 4, которые соединяют вершину B с вершиной A:

• B-E-D-C-A
• B-E-G-D-A

Ответ: B-E-D-C-A, B-E-G-D-A