Czy w mojej obserwacji mam rację, że liczność maksymalnego dopasowania wykresu dwudzielnego jest zawsze równy ?
źródło
Czy w mojej obserwacji mam rację, że liczność maksymalnego dopasowania wykresu dwudzielnego jest zawsze równy ?
Biorąc dwudzielny wykres a maksymalna dopasowanie z poprzez Koniga twierdzenia widzimy gdzie jest minimalna pokrywa wierzchołek o . Twoje stwierdzenie stanowi jedynie górną granicę wielkości możliwego dopasowania, a nie ścisłą równość.
Obraz na stronie wikipedii stanowi miły kontrprzykład dla twojego roszczenia. Widzimy, że , podczas gdy .
Jednak w przypadku pełnego dwuczęściowego wykresu Twoja instrukcja jest w posiadaniu.
Nie. Na przykład rozważmy przypadek, w którym obie strony są rozłączone lub przypadek, w którym duża grupa węzłów jest połączona z tym samym pojedynczym węzłem: