На рисунке изображен граф (описание словами: 5 вершин: А, В, С, D, Е. Ребра: А-В, А-C, B-C, B-D, C-D, D-E). а) Определите степень вершины А и вершины D. b) Сколько рёбер выходит из вершины В? c) Есть ли в этом графе «висячая вершина» (степень 1)?

Решение:

Граф имеет вершины: А, В, С, D, Е. Ребра: А-В, А-C, B-C, B-D, C-D, D-E.

а) Степень вершины:

• Степень вершины — это число рёбер, которые к ней примыкают.
• Степень вершины А: рёбра А-В, А-C. Степень А = 2.
• Степень вершины D: рёбра B-D, C-D, D-E. Степень D = 3.

b) Ребра, выходящие из вершины В:

• Из вершины В выходят рёбра: А-В, B-C, B-D.
• Всего 3 ребра.

с) Висячая вершина:

• Висячая вершина — это вершина степени 1.
• В нашем графе:
• Степень А = 2
• Степень В = 3
• Степень С = 3 (А-С, B-C, C-D)
• Степень D = 3
• Степень Е = 1 (D-E)
• Вершина Е имеет степень 1.

Ответ: а) Степень А = 2, степень D = 3. b) Из вершины В выходит 3 ребра. c) Да, в графе есть висячая вершина Е.