Решение задач по теории графов

Ниже представлены решения задач из карточки, оформленные для записи в тетрадь. Задание А14 (по графу А7) а) Цепь из вершины А в вершину В: А — Н — С — В. б) Цепь из А в В через ребро CD: А — Н — С — D — В. Задание А15 (по графу А12) а) Кратчайший путь из А в В: А — F — В. Длина этого пути равна 2 (количество ребер). б) Кратчайшие пути из С в В: 1) С — D — E — B; 2) С — F — B. Длина кратчайшего пути равна 2. Количество таких путей: 2. Задание А16 а) Граф А1 является связным? Нет, граф А1 не является связным (состоит из двух отдельных частей). б) Граф А3 является связным? Да, граф А3 является связным (из любой вершины можно попасть в любую другую). Задание А17 а) Граф А13 является связным? Да, граф А13 является связным. б) Граф А12 является связным? Да, граф А12 является связным. Задание А18 Циклами являются следующие графы: На рисунке а): 1, 2. На рисунке б): 3. Задание А21 (по графу А12) а) Наименьшая длина цикла: Цикл A — D — F — A имеет длину 3. Ответ: 3. б) Наибольшая длина цикла: Цикл A — C — E — B — F — A имеет длину 5. Ответ: 5. Задание А22 Графы в задании А18, которые не являются циклами, но содержат цикл: На рисунке а): 4. На рисунке б): 1, 2, 4. Задание А24 (по графу А7) а) Сколько циклов в этом графе? В графе А7 можно выделить следующие простые циклы: 1) A-H-C-B-A 2) A-H-C-D-B-A 3) B-C-D-B 4) A-E-B-A 5) A-E-B-C-H-A и другие комбинации. Всего в таком графе 7 простых циклов. б) Сколько в этом графе циклов длины 3? Цикл длины 3 только один: B — C — D — B. Ответ: 1.