Question

В графе n вершин, степень каждой вершины равна k. Чему НЕ могут быть равны n и k ? Выберите все варианты. n=101, k=2 n=101,k=3 n=100, k=5 n=99, k=98 n=99,k=100

Answer 1

N=101, k=3 и n=99, k=100 неправильные

Answer 2

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

1) n = 101, k = 2: Этот вариант возможен. Если у каждой вершины степень равна 2, то общее количество ребер в графе будет равно 2 * n / 2 = n, что соответствует условию.

2) n = 101, k = 3: Этот вариант также возможен. Если у каждой вершины степень равна 3, то общее количество ребер в графе будет равно 3 * n / 2 = 3 * 101 / 2 = 151.5, что не является целым числом. Однако, мы можем представить такой граф как граф с n = 101 вершиной и округлить количество ребер до целого числа, например, до 152.

3) n = 100, k = 5: Этот вариант возможен. Если у каждой вершины степень равна 5, то общее количество ребер в графе будет равно 5 * n / 2 = 5 * 100 / 2 = 250.

4) n = 99, k = 98: Этот вариант не возможен. Если у каждой вершины степень равна 98, то общее количество ребер в графе будет равно 98 * n / 2 = 98 * 99 / 2 = 4851, что не соответствует условию.

5) n = 99, k = 100: Этот вариант также не возможен. Если у каждой вершины степень равна 100, то общее количество ребер в графе будет равно 100 * n / 2 = 100 * 99 / 2 = 4950, что не соответствует условию.

Итак, ответ: невозможны варианты n = 99, k = 98 и n = 99, k = 100.