На рисунке изображен граф. Назовите, если в графе имеется: 1)какой нибудь путь и укажите его длину 2) какую нибудь цепь 3) какой нибудь цикл 4) какой нибудь простой цикл. Определите является ли граф цепью или простым циклом.

Для решения выберем граф **б)** как наиболее наглядный. 1) **Путь:** $M \rightarrow A \rightarrow K \rightarrow H$. Длина пути (количество ребер) равна 3. 2) **Цепь** (путь, в котором все ребра различны): $M \rightarrow H \rightarrow K \rightarrow A \rightarrow M$. В данном графе это также является циклом. 3) **Цикл** (замкнутая цепь): $A \rightarrow M \rightarrow H \rightarrow A$. 4) **Простой цикл** (цикл, в котором не повторяются вершины, кроме первой и последней): $K \rightarrow A \rightarrow M \rightarrow L \rightarrow K$ (если рассматривать внешние ребра) или $A \rightarrow K \rightarrow H \rightarrow A$. **Определение:** Граф **б)** не является цепью, так как из его вершин выходит более двух ребер (он содержит циклы). Он также не является простым циклом в целом, так как это полный граф $K_4$ с дополнительными внутренними связями (диагоналями), а не одна замкнутая линия. Если рассматривать граф **а)**: Это **цепь** $H \rightarrow A \rightarrow L \rightarrow K \rightarrow M$. Она же является **простым путем** длины 4. Циклов в этом графе нет.