В11. а) Существует ли граф, у которого сумма степеней всех вершин равна 365? б) В некотором графе сумма степеней всех вершин равна 168. Сколько в этом графе рёбер? В15. На рисунке изображён граф. а) Сколько кратчайших путей ведёт из вершины А в вершину В? б) Сколько кратчайших путей из вершины А в вершину В проходит через вершину С?

В11.

a) Сумма степеней всех вершин графа всегда должна быть четной, так как каждая вершина вносит вклад в сумму, равный ее степени, а каждое ребро соединяет две вершины, добавляя 2 к общей сумме. Число 365 нечетное, поэтому граф с такой суммой степеней вершин не существует.

б) Сумма степеней всех вершин графа равна удвоенному числу ребер. Если сумма степеней вершин равна 168, то число ребер равно половине этой суммы: \[\frac{168}{2} = 84\]

В15.

a) Чтобы добраться из вершины А в вершину В, нужно сделать 3 шага вправо и 3 шага вниз (или наоборот). Кратчайший путь состоит из 6 шагов. Количество таких путей можно вычислить как количество способов выбрать 3 шага из 6 (или 3 шага вниз из 6):

Количество путей: \[C_6^3 = \frac{6!}{3! \cdot 3!} = \frac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20\]

б) Чтобы путь из А в В проходил через вершину С, сначала нужно добраться из А в С, а затем из С в В.

• Из А в С: 1 шаг вправо и 1 шаг вниз. Количество путей: \[C_2^1 = \frac{2!}{1! \cdot 1!} = 2\]
• Из С в В: 2 шага вправо и 2 шага вниз. Количество путей: \[C_4^2 = \frac{4!}{2! \cdot 2!} = \frac{4 \cdot 3}{2 \cdot 1} = 6\]

Общее количество путей из А в В через С равно произведению количества путей из А в С и из С в В: \[2 \cdot 6 = 12\]

Ответ: В11. а) не существует, б) 84; В15. а) 20, б) 12

Отлично! Ты хорошо поработал. Продолжай в том же духе, и у тебя все получится!