된 그래프에서 교차의 수를 최소화

다음의 알고리즘 문제 나 발생한 표시된대로 에지 교차 수가 최소화되도록 각 열 내의 노드를 어떻게 재 배열 할 수 있습니까? 나는이 문제가 일반 그래프 (link)에 대해 NP 어려운 것을 알고 있지만, 그래프가 이원적이라는 것을 고려하면 몇 가지 트릭이 있습니까? 후속으로된 그래프에서 교차의 수를 최소화

만 V에 가장자리가 세 번째 열w , 어떤이 있다면? 아니면 더?

출처

2013-11-20 Imre Kerr

그래서 그래프에 파일을 준비 방금 설치 한 후 * 두 개의 열 * (각 하위 그래프에 하나씩)을 원하거나 노드를 중개자에 배치 할 수 있습니까 이봐 요? –

최적 해 또는 근사값을 원하십니까? (좋은 질문 btw) –

@arturgrzesiak 노드는 여전히 두 개의 열에 있어야합니다. 나는 그 질문을 편집하여 그 내용을 명확하게 할 것입니다. –

Garey 및 존슨 교차 번호 원래 논문은 또한 에지 교차점의 수를 최소화하기위한 이분 그래프 NP-어렵다는 것을 입증 언급 용지 On the one-sided crossing minimization in a bipartite graph with large degrees by Hiroshi Nagamochi. 사실, 당신이 하나 개의 컬럼에 대한 최적의 순서를 이야기하는 경우에도 여전히 NP-하드 입니다 : 된 그래프 감안할 때

, 2 층 도면의 첫 번째 노드 집합 V의 노드 배치 구성 직선 L1 및 제 2 노드 집합 내의 노드를 평행선 L2 상에 놓는 노드를 배치한다. 2 층 도면에서 호 사이의 교차 수를 최소화하는 문제는 Harary와 Schwenk가 처음 도입 한 입니다. 일방 교차 최소화 문제는 L1에서 두 노드의 순서를 찾도록 요청하므로 아크 교차 수가 최소화되는 동안 ( 의 순서는 L2에서 W 노드를 지정하고 고정하는 동안) 입니다. 문제의 응용 프로그램은 VLSI 레이아웃 및 계층 적 도면에서 찾을 수 있습니다.

그러나 양면 및 한면 문제는 Garey 및 Johnson과 Eades 및 Wormald에서 각각 NP으로 표시됩니다.

출처

2013-11-20 22:14:49

그 종이는 내가 원하는 것을 정확하게 본다. 감사! –

Peter de Rivaz는 NP-Hard라고 지적했지만 여전히 근사치가 있으면 다음 솔루션으로 진행할 수 있습니다.

필자의 초기 생각은 그래프 레이아웃에 몇 가지 강제 기반 알고리즘을 사용하는 것이지만 구현하기가 약간 지루할 수 있습니다. 그러나 이봐,이 멋진 프로그램 graphviz.org이있어, 당신을 위해 모든 일을 할 수 있습니다.

graph G{ 
    {rank=same A B C D E} 
    {rank=same F G H K I J} 

    A -- F; 
    A -- G; 
    A -- K; 
    A -- I; 
    A -- H; 
    A -- J; 

    B -- G; 

    C -- G; 
    C -- J; 

    D -- K; 
    D -- I; 
}

실행 : dot -Tpng yourgraph -o yourgraph.png

및 무료 :-) 위해 그런 일을 얻을 :

enter image description here

출처

2013-11-20 22:30:38

된 그래프에서 교차의 수를 최소화

답변

관련 문제