Приёмы доказательств в теории графов - ответы
Количество вопросов - 10
Какой метод использован при доказательстве следующей теоремы?
Теорема. Не существует графа без петель и кратных рёбер, вершины которого имеют попарно различные степени.
Доказательство. Предположим, что n вершин графа имеют попарно различные степени. Таким образом, граф содержит вершины степеней 0, 1,…, n-1. Наличие вершин степени 0 и n-1 даёт противоречие.
Доказательство теоремы Дирака осуществляется методом:
В комнате, в которой нет света, разбросано бесконечное число носков 3 цветов. Какое минимальное количество носков, взятых из комнаты, достаточно для составления пары 1 цвета?(Ответ необходимо ввести в поле ввода.)
Установив взаимно однозначное соответствие с сочетаниями 4 из 11 объектов, определить число графов K4 , содержащихся в помеченном графе K11.(Ответ необходимо ввести в поле ввода.)
Всем помеченным деревьям на n вершинах могут быть поставлены в соответствие различные наборы из n-2 натуральных чисел. Наоборот, каждый из указанных наборов соответствует вполне определённому дереву. Каково количество помеченных деревьев на 5 вершинах?(Ответ необходимо ввести в поле ввода.)
Сколько помеченных 3,3-графов (двудольных графов с 3 вершинами в каждой доле)?(Ответ необходимо ввести в поле ввода.)
При каком значении X последовательность 4,3,3,3,X является разбиением простого графа?(Ответ необходимо ввести в поле ввода.)
Определить X, если последовательность 7,X,5,3,2,2,2,2 является разбиением простого графа. Рекомендация: использовать критерий Гавела-Хакими более 1 раза, при необходимости упорядочивая образующиеся последовательности.(Ответ необходимо ввести в поле ввода.)
Укажите двудольные графы с паросочетанием из 2 рёбер: ![]()
Укажите матрицу, соответствующую двудольному графу: ![]()