1. Сколько ребер есть в полном графе с 9 вершинами? 2. Сколько ребер в графе с вершинными степенями 5, 4, 3, 5

Пижон

29

1. В полном графе каждая вершина соединена с каждой другой вершиной. Количество ребер можно найти, применив формулу \(E = \frac{{n \cdot (n-1)}}{2}\), где \(E\) - количество ребер, а \(n\) - количество вершин. В данном случае, у нас 9 вершин, поэтому подставим \(n = 9\) в формулу и найдем количество ребер:
\[E = \frac{{9 \cdot (9-1)}}{2} = \frac{{9 \cdot 8}}{2} = \frac{{72}}{2} = 36\]

Таким образом, в полном графе с 9 вершинами имеется 36 ребер.

2. Сумма вершинных степеней в графе равна удвоенному количеству ребер. Мы знаем вершинные степени в графе: 5, 4, 3, 5, 4, 3, 5, 4 и 3. Чтобы найти количество ребер, нужно сложить все вершинные степени и поделить их на 2:
\[E = \frac{{5 + 4 + 3 + 5 + 4 + 3 + 5 + 4 + 3}}{2} = \frac{{36}}{2} = 18\]

Таким образом, в данном графе с вершинными степенями 5, 4, 3, 5, 4, 3, 5, 4 и 3 имеется 18 ребер.

3. В полном графе каждая вершина соединена с каждой другой вершиной. Полный граф с 16 вершинами имеет \(\frac{{n \cdot (n-1)}}{2}\) ребер, где \(n\) - количество вершин. В данном случае, у нас 16 вершин. Подставим это значение в формулу:
\[E = \frac{{16 \cdot (16-1)}}{2} = \frac{{16 \cdot 15}}{2} = \frac{{240}}{2} = 120\]

Чтобы полный граф перестал быть связным, нужно удалить хотя бы одно ребро. Таким образом, необходимо удалить не менее 119 ребер.