А.2. На рисунке изображён граф. а) Составьте в нём какую-нибудь цепь из вершины А в вершину В. Ответ: б) Составьте в нём какую-нибудь цепь из вершины А в вершину В, проходящую через ребро CD. Ответ: в) Сколько циклов в этом графе? Ответ: г) Сколько в этом графе циклов длины 3? Ответ:

a) Цепь из вершины А в вершину В может быть, например, такой: A-E-H-C-F-B.

Ответ: A-E-H-C-F-B

б) Цепь из вершины А в вершину В, проходящая через ребро CD, может быть, например, такой: A-E-D-C-F-B.

Ответ: A-E-D-C-F-B

в) Чтобы посчитать количество циклов в графе, нужно определить все замкнутые пути. В данном графе можно выделить следующие циклы: A-E-D-C-H-A, E-D-C-H-E, D-C-F-B-G-D, H-C-F-H, D-C-F-D, E-D-H-E, C-F-B-C, A-E-D-H-A, D-C-H-D, C-F-C

Ответ: 10

г) Циклом длины 3 является цикл, состоящий из трех ребер. В данном графе это циклы: D-C-F-D, H-C-F-H, C-F-B-C, E-D-H-E

Ответ: 4