уникальное максимальное соответствие

Question

Я пытаюсь использовать двудольный граф для кодирования моей программы со следующими свойствами:

1. с каждой стороны, есть N вершин
2. график подключен

Теперь я хочу добавить в мой код условие, которое проверяет, больше ли число ребер, чем M , не позволяет пользователю выполнять больше действий (в простом предложении выведите что-то в этом состоянии) M равно максимальное число ребер так, что оно все еще имеет уникальное максимальное совпадение.

Вопрос в том, как мне найти М?

Любая идея будет оценена Спасибо

Answer 1

, если вы хотите найти максимум m такой, что существует хотя бы один граф с n вершинами и m ребрами с уникальным максимальным соответствием, ответ будет (n + 1) * n / 2.

, чтобы показать, что существует хотя бы один граф с таким числом ребер, рассмотрим граф с вершинами x ₁ , x ₂ , .., x _n в одной части и вершины y ₁ , .. y _n в другой части. проведите ребро между вершиной x _i и y _j тогда и только тогда (i <= j). </p>

чтобы показать, что ребер больше нет, используйте индукцию по числу вершин. Прежде всего, мы можем показать, что если каждая вершина графа связана хотя бы с двумя вершинами, граф имеет как минимум два разных максимальных соответствия. (рассмотрим одно максимальное совпадение, следуйте по пути от вершины, ребра которой чередуются между совпадающими ребрами и несоответствующими ребрами, сделайте окружность и поверните все ребра в обратном направлении.)

поэтому мы знаем, что есть одна вершина со степенью, равной единице. удалите эту вершину и ее соседа и используйте индукцию на оставшемся графе.

извините за плохой английский.