Дан граф с 7 вершинами и степенями вершин 1,1,2,2,2,3,4. Возможно ли такой граф? Обоснуйте выбор критериев (теорема о сумме степеней, построение) и приведите пример или контрпример
Дан граф с 7 вершинами и степенями вершин 1,1,2,2,2,3,4. Возможно ли такой граф? Обоснуйте выбор критериев (теорема о сумме степеней, построение) и приведите пример или контрпример
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
По теореме о сумме степеней (рукопожатий): сумма степеней всех вершин равна удвоенному числу рёбер, т.е. должна быть чётной:
∑di=2∣E∣. \sum d_i=2|E|.
∑di =2∣E∣. Здесь
1+1+2+2+2+3+4=15, 1+1+2+2+2+3+4=15,
1+1+2+2+2+3+4=15, а 151515 нечётно, следовательно не существует простого (неориентированного без петель) графа с такой последовательностью степеней.