На рисунке изображен граф. а) Найдите степень каждой его вершины. б) Можно ли обвести этот граф карандашом, не отрывая карандаша от бумаги и не проводя одну линию дважды (одним росчерком). в) Найдите суммарную степень вершин этого графа.

Решение:

Граф:

Вершины: A, B, C, D, E, F, G, H

Ребра: AB, AD, AC, BD, BE, CD, CE, CF, DE, DF, DG, EF, EG, FH

а) Степень каждой вершины:

• Степень вершины A: 3 (ребра AB, AD, AC)
• Степень вершины B: 3 (ребра AB, BD, BE)
• Степень вершины C: 3 (ребра AC, CD, CE)
• Степень вершины D: 4 (ребра AD, BD, CD, DF)
• Степень вершины E: 4 (ребра BE, CE, DE, EF, EG)
• Степень вершины F: 3 (ребра CF, DF, EF, FH)
• Степень вершины G: 3 (ребра DG, EG, FG)
• Степень вершины H: 1 (ребро FH)

б) Можно ли обвести граф одним росчерком?

Для того чтобы граф можно было обвести одним росчерком (т.е. пройти по всем ребрам, не отрывая карандаша и не проводя ребро дважды), он должен иметь либо 0, либо 2 вершины с нечетной степенью.

В данном графе вершины с нечетной степенью:

• A (3)
• B (3)
• C (3)
• F (3)
• G (3)
• H (1)

Всего 6 вершин с нечетной степенью. Следовательно, этот граф нельзя обвести одним росчерком.

в) Суммарная степень вершин графа:

Сумма степеней всех вершин равна сумме степеней: 3 + 3 + 3 + 4 + 4 + 3 + 3 + 1 = 24.

По теореме о сумме степеней, суммарная степень вершин графа равна удвоенному числу ребер. Посчитаем ребра:

• AB, AD, AC, BD, BE, CD, CE, CF, DE, DF, DG, EF, EG, FH — всего 14 ребер.

Проверим: 2 * 14 = 28. Мои расчеты степеней вершин дают 24, а ребер 14. Пересчитаем ребра внимательно:

• A-B, A-D, A-C (3)
• B-D, B-E (2)
• C-D, C-E, C-F (3)
• D-F, D-G (2)
• E-F, E-G (2)
• F-H (1)
• Всего: 3+2+3+2+2+1 = 13 ребер.

Сумма степеней = 2 * 13 = 26. Пересчитаем степени вершин:

• A: 3 (AB, AD, AC)
• B: 3 (AB, BD, BE)
• C: 3 (AC, CD, CE, CF) - здесь ошибка, C связан с F
• D: 4 (AD, BD, CD, DF)
• E: 4 (BE, CE, DE, EF, EG) - здесь ошибка, E связан с G
• F: 3 (CF, DF, EF, FH) - здесь ошибка, F связан с H
• G: 3 (DG, EG, FG) - здесь ошибка, G связан с E
• H: 1 (FH)

Давайте перерисуем граф и будем считать, чтобы избежать ошибок.

Пересчет с учетом более внимательного анализа изображения:

Вершины: A, B, C, D, E, F, G, H

Ребра:

• A-B, A-C, A-D
• B-E
• C-D, C-E, C-F
• D-F, D-G
• E-F, E-G
• F-H

Всего ребер: 3 + 1 + 3 + 2 + 2 + 1 = 12 ребер.

а) Степень каждой вершины (пересчет):

• A: 3 (AB, AC, AD)
• B: 2 (AB, BE)
• C: 4 (AC, CD, CE, CF)
• D: 3 (AD, CD, DF, DG) - ошибка, D связан с G
• E: 4 (BE, CE, EF, EG) - ошибка, E связан с G
• F: 4 (CF, DF, EF, FH) - ошибка, F связан с H
• G: 3 (DG, EG, FG) - ошибка, G связан с E
• H: 1 (FH)

Давайте заново, очень медленно, глядя на точки и линии.

Вершины: A, B, C, D, E, F, G, H.

Ребра:

1. A соединена с B, D, C. Степень A = 3.
2. B соединена с A, E. Степень B = 2.
3. C соединена с A, D, E, F. Степень C = 4.
4. D соединена с A, C, F, G. Степень D = 4.
5. E соединена с B, C, F, G. Степень E = 4.
6. F соединена с C, D, E, H. Степень F = 4.
7. G соединена с D, E. Степень G = 2.
8. H соединена с F. Степень H = 1.

Итого:

• Степень A: 3
• Степень B: 2
• Степень C: 4
• Степень D: 4
• Степень E: 4
• Степень F: 4
• Степень G: 2
• Степень H: 1

б) Можно ли обвести этот граф одним росчерком?

Число вершин с нечетной степенью: A (3), B (2) -четная, C (4) -четная, D (4) -четная, E (4) -четная, F (4) -четная, G (2) -четная, H (1).

Вершины с нечетной степенью: A (3), H (1). Всего 2 вершины с нечетной степенью.

Да, можно обвести этот граф одним росчерком, так как ровно две вершины имеют нечетную степень.

в) Суммарная степень вершин графа:

Сумма степеней = 3 + 2 + 4 + 4 + 4 + 4 + 2 + 1 = 24.

Число ребер = Сумма степеней / 2 = 24 / 2 = 12.

Проверим количество ребер по рисунку:

• AB, AC, AD (3)
• BE (1)
• CD, CE, CF (3)
• DF, DG (2)
• EF, EG (2)
• FH (1)

Всего ребер = 3 + 1 + 3 + 2 + 2 + 1 = 12 ребер.

Ответ:

• а) Степень вершин: A - 3, B - 2, C - 4, D - 4, E - 4, F - 4, G - 2, H - 1.
• б) Да, можно.
• в) Суммарная степень вершин равна 24.