Ein weiterer Beweis der verallgemeinerten Tutte—Berge-Formel für f-begrenzte Teilgraphen

Key Points

• Ziel ist es, einen neuen Beweis der Min-Max-Beziehung für die Größe von f-begrenzten Teilgraphen unter Verwendung von Tuttes Theorem zu etablieren.
• Es wurde ein nichtnegatives ganzzahliges Gewicht für jeden Knoten in einem Multigraphen eingeführt.
• Tuttes f-Faktor-Theorem wurde angewandt, um die Beziehung herzuleiten.
• Es wurden spezifische Bedingungen betrachtet, bei denen der f-begrenzte Teilgraph sich auf klassische Definitionen reduziert.
• Bestätigt wurde, dass die Min-Max-Beziehung für allgemeine f-begrenzte Teilgraphen gilt.
• Es wurde gezeigt, dass die Theorie die klassische Tutte-Berge-Formel für maximale Matchings umfasst.

Abstract