2
는
I 가중 최대 가중 매칭 무향 이분 그래프 (즉, 할당 문제)를 계산하기 위해 다양한 알고리즘들을 알고 Ford 또는 Blossom 알고리즘 (일반적으로, 즉 bipartite, graphs에서는 작동하지 않음).최대 가중 이분 정합 _with_ 관한 에지
그러나 2 부분 그래프의 가장자리가 이고 가중치가 적용된 인 경우 어떻게 최대 가중치 매칭을 계산할 수 있습니까?
위의 알고리즘 중 하나를 적용 할 수 있도록 그래프의 방향이 바뀌지 않도록하기 위해 폴리 노미 널 복잡성 또는 이전 변형이있는 알고리즘에 대한 포인터가 좋을 것입니다.
편집 : 관한 에지 갖는 차분 (A-> B는 B-보다 완전히 다른 중량>을 가질 수) 만드는 이유 매칭 에지의 중량을 최대화하도록 참고 때문입니다.
인정 하듯이, 나는 기수를 극대화 한 경우 감독 가장자리 차이가 나지 않을 것 내가 카디널리티 극대화하기 위해 잘 알려진 알고리즘 중 하나를 적용 할 수 : Hopcroft - 카프, 최대 네트워크 흐름을 ....
편집 2 : 시작이나 끝 정점 공유하지 않는 지시 가장자리의 집합 : 일반적으로 방향성 그래프에 적용되는 용어이다 일치 이후는, 제가 바로이 질문에 일치 무슨 뜻인지 명확히 할 수 있습니다. 좀 더 공식적으로, 만약 U-> V와 U '-> V'가 매칭의 일부라면, V/= U '와 V'/ = U입니다.
지도력이 어떻게 발생합니까? 어쩌면 그것은 나 일 뿐이지 만, 직접적인 매칭이 무 디렉션과 다른 점은 나에게 불분명하다. 모든 모서리가 그래프의 파트 A에서 파트 B로 이동하면 모서리 세트 만 일치합니까? 그러나이 경우를 지향되지 않는 경우로 축소하는 것은 사소한 일입니다. – us2012
응? bipartite 그래프는 방향성이 없을 수도 있지만, max-flow 알고리즘은 모든 에지가 set A에서 set B로 향하는 암시 적 변환을 만듭니다. 지시 된 bipartite 그래프를 가지고 있더라도 A-> B와 B- > A와 일치하는 문제의 맥락에서? – dfb
다른 방향 (방향이 다른)이 다른 가중치를 가질 수 있기 때문에 방향성은 차이를 만듭니다. G = (U u V, E)를 방향성이있는 그래프로하고 u를 V의 노드 U와 노드 V의 노드라고하면 에지 u -> v에 할당 된 가중치는 에지에 할당 된 가중치와 다를 수 있습니다. v -> u 일치하는 최대 카디널리티가 있지만 일치하는 최대 가중치를 언급하는 경우에는 차이가 없습니다. – fons