최대 오일러 서브 그래프를 찾는 방법은 무엇입니까?

Question

주어진 그래프의 최대 오일러 부 그래프를 찾는 방법은 무엇입니까? "최대"란 모서리 나 정점 또는 둘 모두가 최대 인 부분 그래프를 의미합니다. 내 생각은 사이클 공간의 기초를 찾고 적절한 방법으로 기초주기를 결합하는 것이지만, 어떻게 해야할지 모르겠다. (좋은 생각인지 아닌지).

UPD. 소스 그래프가 연결되었습니다.

Answer 1

몇 가지 생각. 그래프가 연결되어 있으면 (가능한 격리 된 정점을 사용하여) 모든 정점이 균일하게됩니다.

홀수 차수의 꼭지점 쌍 사이의 (최단) 경로를 제거하여 두 번째 기준을 만족하는 것은 '쉽다'.

가장자리를 제거하면 연결되지 않은 그래프가 생성 될 수 있으므로 연결성 문제가 있습니다.

'단순한'(탐욕스러운) 해결책은 생산하기 쉽지 않다는 것을 보여주는 예입니다. 각 모서리를 두 모서리 (또는 그 이상)로 분할하여 전체 그래프 K5를 수정합니다. 이 수정 된 K5 그래프 두 개를 취해 각각에서 두 개의 정점 (첫 번째부터 A, B부터 두 번째까지 D)을 가져옵니다. A-C와 B-D를 연결하십시오. 욕심 많은 접근법은 최단 경로이므로 추가 된 가장자리를 제거합니다. 그 그래프가 연결되지 않은 상태가됩니다. 해결책은 경로 A-B 및 C-D를 제거하는 것입니다.

알고리즘은 가장자리를 제거하는 동안 하위 그래프 연결에주의해야합니다. 알고리즘은 그 사이의 경로를 제거하는 데 사용되는 쌍이없는 홀수 차수 버텍스의 각 하위 집합이 하위 집합의 카디널리티보다 커야 함을 유지해야합니다.

최적화를 통한 재귀 적 무차별 대항력 솔루션을 사용하여 (테스트 용으로) 시도 할 것입니다. O는 홀수 차수의 정점 목록입니다.

def remove_edges(O, G): 
    if O is empty: 
    return solution 
    for f in O: 
    for t in O\{f}": 
     G2 = G without path edges between (f,t) 
     if G2 is unconnected: 
     continue 
     return remove_edges(O\{f,t}, G2) 

최적화는 O 및 O {f} 집합을 최단 경로를 갖는 꼭지점으로 정렬 할 수 있습니다. 가장자리를 제거하기 전에 O에서 정점의 모든 쌍 사이의 최단 길이를 찾아서 수행 할 수 있습니다. 이는 각 O 정점에서 BFS를 통해 수행 할 수 있습니다.