№1 Рассмотрите рисунок и выпишите номера графов, которые являются: а) цепями; б) циклами; в) несвязными графами

Решение:

Рассмотрим каждый граф:

1. Граф 1: Имеет два концевых узла (степени 1) и остальные узлы имеют степень 2. Это цепь.
2. Граф 2: Не имеет концевых узлов, все узлы имеют степень больше 1. Образует замкнутый путь, но есть ответвления. Это не простой цикл.
3. Граф 3: Все узлы имеют степень 2. Образует замкнутый контур. Это цикл (пятиугольник).
4. Граф 4: Имеет два концевых узла (степени 1) и два узла степени 2. Это цепь.
5. Граф 5: Состоит из одного узла. Это также считается связным графом, но в контексте классификации, это отдельный случай. Если рассматривать как граф без ребер, то он является сам по себе.
6. Граф 6: Имеет два концевых узла (степени 1) и три узла степени 2. Это цепь.
7. Граф 7: Все узлы имеют степень 2. Образует замкнутый контур. Это цикл.
8. Граф 8: Имеет два концевых узла (степени 1) и два узла степени 2. Это цепь.
9. Граф 9: Имеет четыре концевых узла (степени 1) и три узла степени 2. Это цепь.

а) Цепи: Графы 1, 4, 6, 8, 9.

б) Циклы: Графы 3, 7.

в) Несвязные графы: В данном наборе нет явно несвязных графов (состоящих из нескольких отдельных компонент, кроме графа 5, который можно рассматривать как тривиальный несвязный граф, или как единичный узел).

Ответ: а) 1, 4, 6, 8, 9; б) 3, 7; в) 5.