Сколько помеченных 2,3-графов (двудольных графов с 2 и 3 вершинами в первой и второй долях)?

вопрос

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

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

Отправить

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