2
같은 크기의 X와 Y를 갖는 2 부분 그래프가 주어지면 그래프를 완벽하게 만들 수 있도록 추가해야하는 최소 가장자리 수를 어떻게 효율적으로 찾을 수 있습니까? 어울리는? 홀의 정리가 만족 될 때까지 모든 2^(| X |) 서브 세트를 반복하고 가장자리를 추가하는 것보다 나은 해결책이 있습니까?완벽 한 일치를 갖도록 bipartite 그래프를 수정합니다.
감사합니다.
A
답변
2
질문을 올바르게 이해하면 Hungarian method 또는 네트워크 흐름 문제로 모델링을 사용하여 초기 그래프를 효율적으로 일치시키는 것이 가능해야합니다. 카디널리티 - 최대 매칭이 발견되면 어느 한 파티션에 일치하지 않는 노드가 동등해야하며, 원하는대로 추가 에지를 사용하여 일치시킬 수 있습니다. 환언
,M는 기수 - 최대 매칭 카디널리티 원래 그래프이고
|X|=|Y| 후 적어도
M-|X| 가장자리 그래프에 포함 된 최적 정합을 위해 첨가 될 필요가 보유하고있는 경우.