Укажите двудольные графы с паросочетанием из 2 рёбер:

вопрос

Правильный ответ:

Оставить комментарий

Отправить

• # Какой метод использован при доказательстве следующей теоремы? Теорема. Любое дерево на n >= 2 вершинах содержит 2 висячие вершины. Доказательство. Рассмотрим цепь наибольшей длины, обратившись к любой из её концевых вершин (A). Если степень A отлична от 1, то существует вершина B, смежная с A и отличная от вершины, смежной с A в цепи. Если B не принадлежит цепи, то цепь не максимальна, что противоречит условию. С другой стороны, B не содержится в цепи, так как это ведёт к образованию цикла в дереве.
• # Установив взаимно однозначное соответствие с сочетаниями 2 из 15 объектов, определить число рёбер графа K15.
• # Всем помеченным деревьям на n вершинах могут быть поставлены в соответствие различные наборы из n-2 натуральных чисел. Наоборот, каждый из указанных наборов соответствует вполне определённому дереву. Каково количество помеченных деревьев на 5 вершинах?
• # При каком значении X последовательность 4,X,2,1,1 является разбиением простого графа?
• # Укажите матрицу, соответствующую двудольному графу: