Fractional matching preclusion number of graphs and the perfect matching polytope

G ist ein Graph mit einer geraden Anzahl von Eckpunkten. Die übereinstimmende Präklusionszahl von G, bezeichnet durch mp (G), ist die minimale Anzahl von Kanten, deren Löschung den resultierenden Graphen ohne perfekte Übereinstimmung zurücklässt. Wir führten ein lineares 0-1-Programm ein, das verwendet werden kann, um die übereinstimmende Präklusionszahl von Graphen zu finden. In dieser Arbeit erhalten wir durch Lockerung des linearen 0-1-Programms ein lineares Programm und nennen seinen optimalen objektiven Wert als fraktionelle zusammenpassende Präklusionszahl von Graph G, bezeichnet durch. Wir zeigen, dass sich die Polynomzeit für jeden Graphen G berechnen lässt. Durch Verwendung des perfekt passenden Polyos transformieren wir es in ein neues lineares Programm, dessen optimaler Wert dem reziproken entspricht. Für den zweiseitigen Graphen G erhalten wir eine explizite Formel für und zeigen, dass der maximale Integer k ist, so dass G einen k-Faktor hat. Außerdem zeigen wir für zwei beliebige zweiseitige Graphen G und H, wo sich das kartesische Produkt von G und H. befindet.