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

Question

Вопрос:

Ответ:

ФИО:Телефон:Емаил:Полное описание сути нарушения прав (почему распространение данной информации запрещено Правообладателем):

Accepted Answer

Краткое пояснение: Цепь - это последовательность вершин, соединенных ребрами. Нужно найти подходящие цепи.

a) Цепь длины 4, соединяющая вершину A с вершиной B:

Один из возможных вариантов: A-D-E-C-B

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

Один из возможных вариантов: A-D-E-G-F-G

A-D-E-C-B это цепь, которая соединяет вершину A с вершиной B. Если повторить вершину, то получается цепь длины 5.

Проверка за 10 секунд: Перепроверь, что найденные цепи действительно имеют указанную длину и соединяют нужные вершины.

Читерский прием: Нарисуй граф на бумаге и пройдись по нему пальцем, чтобы визуально найти нужные цепи.