f-제한 서브그래프에 대한 일반화된 Tutte—Berge 공식의 또 다른 증명

Key Points

• 목적은 Tutte의 정리를 사용하여 f-제한 서브그래프의 크기에 대한 최소-최대 관계의 새로운 증명을 확립하는 것입니다.
• 멀티그래프의 각 정점에 대해 비음수 정수 가중치를 도입했습니다.
• Tutte의 f-인자 정리를 적용하여 관계를 도출했습니다.
• f-제한 서브그래프가 전통적인 정의로 축소되는 특정 조건을 고려했습니다.
• 일반적인 f-제한 서브그래프에 대해 최소-최대 관계가 성립함을 확인했습니다.
• 이론이 최대 매칭을 위한 전통적인 Tutte-Berge 공식을 포함하고 있음을 입증했습니다.