Сколько компонент сильной связности может быть в графе, состоящем из 18 вершин, где каждая вершина имеет степень

Letuchaya_Mysh

42

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

В данной задаче говорится, что в графе состоящем из 18 вершин каждая вершина имеет степень 2 или 5, и присутствуют вершины обеих степеней.

Давайте представим, что у нас есть граф G с 18 вершинами, где каждая вершина имеет степень 2 или 5. Допустим, существует k компонент сильной связности в этом графе.

Мы знаем, что степень каждой вершины в графе равна сумме степеней инцидентных ребер. Поскольку каждая вершина имеет степень 2 или 5, это означает, что сумма степеней всех вершин в графе будет четным числом.

Теперь давайте рассмотрим каждую компоненту сильной связности. Если в компоненте сильной связности есть x вершин со степенью 2 и y вершин со степенью 5, тогда общее количество ребер в этой компоненте будет состоять из \(\frac{2x + 5y}{2}\) ребер, так как каждое ребро добавляет 2 к степени вершины степени 2 и 5 к степени вершины степени 5.

Таким образом, общее количество ребер во всех компонентах сильной связности составит \(\sum_{i=1}^{k}{\frac{2x_i + 5y_i}{2}}\), где \(x_i\) и \(y_i\) - количество вершин со степенями 2 и 5 соответственно в i-ой компоненте сильной связности.

Сумма четных чисел (\(2x_i\)) всегда будет четным числом, а сумма пятерок (\(5y_i\)) также будет четным числом, так как количество вершин в графе нечетное. Следовательно, сумма \(\frac{2x_i + 5y_i}{2}\) также будет четным числом.

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

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