Verbundenes Teilgraphen, Zuordnungen und Partitionen

Gegeben ist ein ungerichteter Graph Formel: siehe Text und ein Vektor mit reellen Kantengewichten. Das Problem des verbundenen Teilgraphen besteht darin, eine Teilmenge von Kanten mit maximalem Gewicht zu finden, die einen verbundenen Teilgraphen von Formel: siehe Text induziert. In diesem Papier stellen wir einen Zusammenhang zwischen der Komplexität des Problems des verbundenen Teilgraphen und der Matching-Zahl her. Wir untersuchen das Trennungsproblem, das mit den sogenannten Matching-Partition-Ungleichungen verbunden ist, die von Didi Biha, Kerivin und Ng in der polyedrischen Studie des Problems des verbundenen Teilgraphen eingeführt wurden, Discr. Math. 338 (2015) 80–92 für das verbundene Teilgraphen-Polytope.