아마도 알고리즘으로 Dijkstra를 찾고

Question

나는 평면에 노드를 배포하는 알고리즘을 찾고 있는데, 그 에지는 모두 같은 크기입니다. 나는 그것이 Dijkstra에 의한 것이라고 생각하지만 기억이 안납니다. 누구든지이 알고리즘에 대해 들어 봤습니까?

Answer 1

일반적으로 이것은 불가능합니다. 효과적으로 tilings of the plane에 유한 그림과 비슷한 것을 원합니다.

정규 폴리곤과 결합 된 다각형을 포함하는 몇 가지 그래프가 있지만 4 점 (4 면체)의 전체 그래프만큼 단순한 것도 불가능합니다.

불가능한 제약 조건의 균형을 유지하려고하는 것이 있다면 graphviz과 그 neato 프로그램을 사용해보십시오.

Answer 2

그런 속성을 가진 그래프를 만들고 싶다면 라인, 반지, 나무 등 당신을 도울 수있는 그래프가 있습니다.하지만 여기서 당신은 누구가 포함하거나 제외 할 가장자리를 결정합니다.

특정 그래프가 있고 동일한 크기의 모든 가장자리를 갖고 싶다면 다음과 같이 불가능합니다 (일부 노드의 경우) : 3 개 이상의 노드로 구성된 전체 그래프, 하나의 스타 토폴로지 주인과 5 명 이상의 노예, 서로 가깝게있는 노예들이 이웃입니다. [다른 게시물의 사례가 더 많이 알려줍니다.]

특별한 경우, $ G \ (V, E) $ 그래프를 $ $ \에 그려서 각 가장자리의 길이가 $ e \ in E $는 단위보다 작습니다. 이것은 NP-Hard 문제입니다. [즉, 임의의 그래프 $ G $가 단위 디스크 그래프인지 여부를 결정할 수 없습니다]