Question

Каждую вершину полного графа G, имеющего 28 ребер, соединили ребром с каждой вершиной полного графа G’. Получился граф, насчитывающий 55 ребер. Сколько в графе G’? Сколько ребер соединяет вершины графа G с вершинами графа G’?

Answer 1

Ответ:

3 и 12

Пошаговое объяснение:

Количество ребер в полном графе считается по формуле: n(n-1)/2. Где n - количество вершин. (простыми словами, чтобы построить ребро нам нужно 2 вершины; у нас n вариантом для первой вершины и n-1 для второй(можно взять любую кроме взятой первой). Их произведение надо поделить пополам, потому что мы посчитали вариант когда брали сначала вершину А, а потом вершину Б, и вариант когда сначала брали вершину Б, а потом А. Но ребро АБ и ребро БА это одно и тоже ребро. Т.е. мы все ребра посчитали дважды, поэтому и делим на 2.)

Таким образом, если в полном графе G было n вершин, а значит n(n-1)/2=28. Откуда n = 8.

Пусть в полном графе G' было х ребер. Тогда (х + 8)(х + 8 - 1)/2=55. Откуда х = 3.

Аналогично, отвечаем на второй вопрос. Чтобы провести ребро между графом G и графом G', из первого мы можем выбрать любую из 8 вершин, а из второго любую из 3. Их произведение также нужно поделить пополам получим 8*3/2= 12.

Answer 2

Пусть у нас есть полный граф G с n вершинами. В полном графе каждая вершина соединена с каждой другой вершиной ребром. Таким образом, в полном графе с n вершинами будет n*(n-1)/2 ребер.

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

Поскольку в G есть 28 вершин, каждая из них соединена с каждой из вершин в G' ребром. Это означает, что для каждой вершины в G существует |G'| ребер, соединяющих её с вершинами в G'.

Таким образом, для всего графа G с 28 вершинами, соединенного с графом G', будет всего 28 * |G'| ребер.

У нас также есть информация, что общее количество ребер в полученном графе равно 55.

Из этого мы можем составить уравнение:

28 * |G'| = 55

Решая это уравнение, найдем:

|G'| = 55 / 28 ≈ 1.964

Поскольку вершины графа должны быть целыми числами, мы можем сделать вывод, что в графе G' будет 2 вершины.

Итак:

• В графе G' будет 2 вершины.
• Каждая вершина из графа G соединена с каждой из 2 вершин в графе G', то есть 2 ребра для каждой вершины в G.