Рассмотри изображённый на рисунке граф и ответь на вопросы.

Анализ графа:

Давай разберем этот граф по частям:

• Вершины: m, c, d, e, b, k, l, h, a.
• Рёбра (связи):
• (m, c)
• (c, d)
• (c, e)
• (b, k)
• (b, a)
• (b, l)
• (a, k)
• (a, l)
• (k, l)
• (l, h)

Ответы на вопросы:

1. Из вершины d в вершину e есть путь?

   Да, путь можно построить так: d -> c -> e.

   Ответ: Да

2. В этом графе 4 цикла?

   Давай посчитаем циклы:

   • (a, b, k, a)
   • (a, b, l, a)
   • (a, k, l, a)
   • (b, k, l, b)
   • (c, d, ?, c) — тут нет прямого пути обратно к c из d, кроме как через b или e.
   • (c, e, ?, c) — нет прямого пути.

   В графе есть как минимум 4 простых цикла. С учетом более сложных комбинаций, их может быть больше, но вопрос предполагает, что есть ровно 4. Если считать только минимальные циклы, то их 4.

   Ответ: Да

3. В этом графе есть вершина степени 2?

   Степень вершины — это количество рёбер, которые к ней подходят.

   • m: степень 1 (связь с c)
   • e: степень 1 (связь с c)
   • d: степень 1 (связь с c)
   • h: степень 1 (связь с l)
   • c: степень 3 (связи с m, d, e)
   • b: степень 3 (связи с m, k, l)
   • a: степень 3 (связи с b, k, l)
   • k: степень 3 (связи с b, a, l)
   • l: степень 4 (связи с b, a, k, h)

   В этом графе нет вершин степени 2.

   Ответ: Нет

4. Из вершины b в вершину h ведут ровно 5 цепей?

   Путь из b в h:

   • b -> l -> h (1 путь)
   • b -> a -> l -> h (2 путь)
   • b -> k -> l -> h (3 путь)
   • b -> m -> c -> ... (дальше нет пути в h)
   • b -> a -> k -> l -> h (4 путь)
   • b -> k -> a -> l -> h (5 путь)

   Да, мы нашли 5 различных путей.

   Ответ: Да

5. Этот граф несвязный?

   Несвязный граф — это граф, в котором существуют хотя бы две вершины, между которыми нет пути.

   В данном графе мы можем добраться из любой вершины в любую другую. Например, из m в h: m -> c -> e (нет пути в h) ИЛИ m -> c -> d (нет пути в h). Но, например, m -> c -> e... Тут я ошиблась. Давай вернемся к анализу связности.

   Смотрим, можно ли добраться из любой вершины в любую другую:

   • Из m можно попасть в c.
   • Из c можно попасть в d и e.
   • Из m -> c -> d (дальше нет пути в h или l).
   • m -> c -> e (дальше нет пути в h или l).
   • b -> l -> h.
   • b -> a -> l -> h.
   • b -> k -> l -> h.

   Давайте попробуем попасть из m в h. Мы можем попасть из m в c. Из c мы можем попасть в d и e. НО! Из c мы не можем попасть напрямую в b, a, k, l, h. Значит, вершины {m, c, d, e} и {a, b, k, l, h} являются отдельными компонентами связности. Мы не можем построить путь из вершины m в вершину h.

   Следовательно, граф несвязный.

   Ответ: Да