Найдите степени вершин графа, изображенного на рисунке. Начертите в тетради таблицу и заполните её.

### 1. Степени вершин графа Степень вершины — это количество ребер, входящих в неё. | Вершина | A | B | C | D | E | F | G | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | Степень | 2 | 3 | 3 | 3 | 4 | 0 | 1 | *Примечание: Вершина F изолирована, степень 0.* ### 2. Цепи в графе а) Цепь длины 4, соединяющая A и B: Например: **A — D — G — D — E — B** (путь: A-D, D-G, G-D, D-E, E-B — длина 5, это не подходит). Посмотрим внимательнее: **A — D — E — C — B** (длина 4). **Ответ: A — D — E — C — B** б) Цепей длины 5 между A и B: Нужно найти пути из 5 ребер: 1) A — D — E — C — E — B 2) A — D — E — B — E — B (не является простой цепью, но является цепью) 3) A — D — G — D — E — B В данном графе достаточно много таких путей. ### 3. Задача про 8 городов Нужно проверить, возможно ли построить такой граф. Воспользуемся леммой о рукопожатиях: сумма степеней всех вершин графа всегда четна (она равна удвоенному количеству ребер). У нас 8 городов (вершин): - 3 города имеют степень 3 (выходит по 3 дороги). - 5 городов имеют степень 4 (выходит по 4 дороги). Считаем сумму степеней: $3 \times 3 + 5 \times 4 = 9 + 20 = 29$. Сумма степеней равна 29 (нечетное число). Согласно лемме о рукопожатиях, сумма степеней должна быть четной. **Ответ: Это невозможно, так как сумма степеней вершин (29) — нечетное число.**