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

вопрос

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

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

Отправить

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