그래프의 가장자리 교차 감소

그래프의 가장자리 교차를 최소화하는 알고리즘이 있는지 묻고 싶습니다. 예를 들어 그래프의 전환 행렬이있는 경우를 예로들 수 있습니다.그래프의 가장자리 교차 감소

다른 노드 주위에 노드를 배치하는 것과 같은 방법이 있지만 다른 아이디어를 알고 싶습니다. 감사.

2012-12-19 DropDropped

그래프 * 드로잉 * - 그래프 G (V, E)에 대해 좋은 꼭지점 레이아웃을 제공하는 알고리즘 (가장자리 엇갈림 등을 최소화하는 알고리즘)을 묻습니다. –

예, 그렇습니다. – DropDropped

그래프 그리기 응용 프로그램 용으로 개발 된 잘 정의 된 알고리즘/라이브러리 범위가 있습니다. 약간의 배경을 얻을 수 있습니다. here.

무향 그래프를 그리려면 일반적으로 그래프 에지를 스프링 (인력)으로 취급하고 정점은 하전 입자 (반발력 적용)처럼 취급하는 힘 기반 레이아웃 알고리즘을 선택하십시오. 알고리즘은 정상 상태에 도달 할 때까지 이러한 힘을 기반으로 정점 위치를 업데이트하여 작동합니다. 힘 기반 방법에 대한 자세한 내용은 here을 참조하십시오. 이러한 알고리즘은 평형 솔루션을 검색하기 때문에 종종 가장자리가 엉키지 않고 의사 최적화 된 레이아웃이됩니다.

사용 가능한 많은 그래프 드로잉 라이브러리 중 하나를 사용하는 데 관심이있을 수 있습니다. Graphviz 패키지는 일반적으로 꽤 좋으며 다른 그래프 그리기 응용 프로그램에 대해 여러 알고리즘을 지원합니다.

출처

2012-12-28 00:29:45

그래프의 가장자리 교차 감소

답변

관련 문제