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

Решение:

Граф имеет 5 вершин: А, B, C, D, E.

Ребра графа: А-В, А-С, B-C, B-D, C-D, D-E.

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

Степень вершины — это количество рёбер, инцидентных этой вершине.

• Степень вершины А: Ребра, инцидентные А: А-В, А-С. Степень A = 2.
• Степень вершины D: Ребра, инцидентные D: B-D, C-D, D-E. Степень D = 3.

b) Количество рёбер, выходящих из вершины В:

Ребра, инцидентные В: А-В, B-C, B-D. Количество рёбер = 3.

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

Висячая вершина — это вершина со степенью 1.

Проверим степени всех вершин:

• Степень A = 2
• Степень B = 3
• Степень C: А-С, B-C, C-D. Степень C = 3.
• Степень D = 3
• Степень E: D-E. Степень E = 1.

Вершина E имеет степень 1.

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