В графе G 5 вершин, (4,3,3,2,2) набор степеней его вершин. Минимальная степень вершины дополнительного графа равна

Предмет: Теория графов
Раздел: Свойства графов и дополнительные графы

Дано: граф ( G ) с 5 вершинами и степенями вершин ((4, 3, 3, 2, 2)).

Нужно найти минимальную степень вершины дополнительного графа (\overline{G}).

Решение:

1. Напомним, что дополнительный граф (\overline{G}) графа (G) на тех же вершинах, но с ребрами, которые отсутствуют в (G).

2. Для каждой вершины степени в (G) степень в (\overline{G}) рассчитывается по формуле:  \deg_{\overline{G}}(v) = n - 1 - \deg_G(v) 
   где (n) — число вершин в графе (G).

3. В нашем случае (n = 5).

4. Рассчитаем степени в дополнительном графе для каждой вершины:

• Для вершины со степенью 4:
   5 - 1 - 4 = 0 
• Для вершин со степенью 3:
   5 - 1 - 3 = 1 
• Для вершин со степенью 2:
   5 - 1 - 2 = 2 

5. Минимальная степень вершины в (\overline{G}) — это минимальное значение среди рассчитанных степеней:
    \min(0, 1, 1, 2, 2) = 0 

Ответ: минимальная степень вершины дополнительного графа равна 0.