가역적 인 방법으로 digraph (지향 그래프)를 방향이없는 그래프로 변환하는 알고리즘을 찾고 있습니다. 즉, 방향이없는 그래프가 주어지면 digraph를 재구성 할 수 있어야합니다. 나는 이것이 더 많은 정점을 가진 무 방향 그래프를 희생시킬 것이지만 나는 신경 쓰지 않는다는 것을 이해합니다.
이것을하는 방법을 알고 있거나 참조를 제안 할 수 있습니까? 미리 감사드립니다.
업데이트 : 아래 AdrianN의 답변에 관해서. 좋은 출발점이 될 수 있지만 현재의 형태로는 효과가 없다고 생각합니다. 내가 생각하지 않는 이유는 다음과 같습니다.
DW의 의견 후 업데이트 : 그래프의 정점이 레이블이없는 것으로 간주합니다. 솔루션에 정점에 레이블을 지정하는 경우 (AdrianN과 마찬가지로) 레이블링 방법에 관계없이 동일한 (동형) 무 방향 그래프를 제공해야합니다. 레이블이있는 정점이있는 그래프에 대한 “동형”의 정의는 두 그래프와 관련된 레이블의 순열이 있지만 레이블이없는 그래프에 대한 정확한 정의는 확실하지 않습니다.
답변
각 지정 모서리 에 대해 새 꼭지점 하고 를 모서리 , , , , , .
e=(x,y)v1e,…,v5e
e
xv1e
v1ev2e
v1ev3e
v3ev4e
v4ev5e
v3ey
디코딩하기 위해, 이웃이 차수 2를 갖는 모든 리프 (degree-1 vertex)는 어떤 에지에 대해 이어야한다. ; 그 이웃은 그리고 다른 이웃 이며 . 은 3도이고 잎과 인접한 고유 한 이웃을 가지고 있습니다. 이웃은 이고 잎은 ( 에 두 개의 잎이있는 이웃이 있으면 임의로 선택) ). 다른 이웃 있다 와 다른 이웃 이고 . 지정된 가장자리를 복원
v5ee=(x,y)
v4e
v4e
v3e
v3e
v1e
v2e
v1e
v2e
v1e
x
v3e
y
(x,y)
정점 .
v1e,…,v5e답변
David Richerby의 답변 (허용됨)이 좋습니다.
나는 간단한 예제 digraph에 대한 그의 지시를 따르고 그것이 누군가를 돕기를 바랍니다.
(David의 답변에 대한 의견으로 이것을 게시했지만 필요한 평판 점수는 없습니다.)
답변
유 방향 그래프를 변환하려면
D무 방향 그래프로
G하나는 다음을 수행합니다.
- 노드 수
D - 무 방향 그래프 2 개 생성
G′ , G″ 와 동일한 정점에서 D - 모든 에지 , 의 로 에지를 추가 경우 , 다른 행의 에지를 추가
u v D G′ u<v G″ - G는 와 의 분리 된 결합이다
G′ G″
분리 된 연합을 수행 할 때 가역적 인 결합을 유지하도록주의를 기울여야합니다.
답변
아이덴티티 기능은 어떻습니까? 즉, 모든 digraph는 동일한 크기의 파티션을 가진 방향이없는 이분 그래프로 볼 수 있으며 그 반대도 마찬가지입니다.
답변
이것에 대한 찔림은 다음과 같습니다.
방향이없는 그래프에서 방향 정보를 추가 정점으로 바꿉니다. 즉, 방향이 지정되지 않은 그래프의 추가 정점을 사용하여 방향 정보를 "인코딩"합니다. 예를 들어, 하나 이상의 모서리가있는 각 지정 꼭지점에 대해 1 + "들어오는"모서리 개수와 같은 여러 개의 지정되지 않은 꼭지점을 추가합니다. 가장자리가 0 인 정점은 변경되지 않습니다.
역방향을 수행하려면 가장자리가 0 이상인 각 정점에 대해 정점을 만듭니다. 가장자리가 정확히 하나 인 정점은 "방향 인코딩"정점입니다. 다른 다중 모서리 정점을 연결하는 각 모서리는 유 방향 그래프의 연결입니다. 이제 알고리즘을 설명 할 수없는 까다로운 부분이 있습니다 (하지만 존재한다고 생각합니다). 각 정점에 대해 들어오는 화살표의 수만 주어진 화살표의 방향을 추론해야합니다.
까다로운 부분은 지뢰 찾기와 같은 것이라고 생각합니다. 🙂 폭탄 (들어오는 가장자리)에 각 사각형 (정점)에 인접한 폭탄의 수가 주어진 곳을 찾으십시오.