Scharfe untere Schranken für die Anzahl der maximalen Paarungen in bipartiten Multigraphen

Zusammenfassung Wir untersuchen die minimale Anzahl maximaler Paarungen in einem bipartiten Multigraphen mit Teilen und unter verschiedenen Bedingungen und verfeinern die bekannte untere Schranke von M. Hall. Wenn, jeder Scheitelpunkt in mindestens Grad hat und jeder Scheitelpunkt in mindestens verschiedene Nachbarn hat, ist das Minimum, wenn und ist, wenn. Wenn jeder Scheitelpunkt mindestens zwei Nachbarn hat und, ist das Minimum, wo. Wir bestimmen auch die minimale Anzahl maximaler Paarungen in mehreren anderen Situationen. Wir bieten eine Vielzahl von Schärfekonstruktionen an.