태그 보관물: graph-theory

graph-theory

내 그래프는 평면입니까? 1), (0, 2),

당신의 작업은 그래프가 평면인지 여부를 결정하는 것입니다.

평면에 포함 할 수있는 경우 그래프, 즉 가장자리가 교차하지 않고 그릴 수있는 경우에는 평면입니다.

입력 : 다음 형식 중에서 선택한 무 방향 그래프가 제공됩니다.

  • 에지리스트 [(0, 1), (0, 2), (0, 3)]

  • 인접도, 예 : {0: [1, 2, 3], 1:[0], 2:[0], 3:[0]}

  • 인접 매트릭스, 예 : [[0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

노드 이름은 숫자, 문자열 또는 유사 할 수 있지만 선택한 형식은 임의의 그래프를 지원할 수 있어야합니다. 노드 이름에 코드를 넣지 마십시오. 자체 루프가 없습니다.

STDIN, 명령 행 인수 및 함수 인수를 포함한 표준 입력 선택.

출력 : 모든 평면 그래프에 대한 특정 출력과 모든 비평면 그래프에 대해 다른 특정 출력을 반환해야합니다.

STDOUT, 함수 반환 값을 포함한 표준 출력 선택.

예 :

평면 :

[]
[(0,1), (0,2), (0,3), (0,4), (0,5), (0,6)]
[(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)]
[(0,2), (0,3), (0,4), (0,5), (1,2), (1,3), (1,4), (1,5), (2,3),
 (2,5), (3,4), (4,5)]

비평면 :

[(0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)]
[(0,3), (0,4), (0,5), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5)]
[(0,3), (0,4), (0,6), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (5,6),
 (7,8), (8,9), (7,9)]

평면성 테스트를 명시 적으로 수행하거나 특별히 평면 임베딩을 참조하는 기능은 허용되지 않습니다.

이것은 코드 골프입니다. 가장 짧은 코드가 이길 수 있습니다.

답변

수학, 201 바이트

f@g_:=EdgeCount@g<9||!(h=g~IsomorphicGraphQ~CompleteGraph@#&)@5&&!h@{3,3}&&And@@(f@EdgeDelete[g,#]&&f@EdgeContract[g,#]&/@EdgeList@g);And@@(f@Subgraph[g,#]&/@ConnectedComponents[g=Graph[#<->#2&@@@#]])&

이것은 명명되지 않은 함수로 평가되며,

{{0, 3}, {0, 4}, {0, 5}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}}

이것은 Wagner의 정리 에 기반한 끔찍하게 비효율적 인 재귀 접근법입니다 .

유한 그래프는 K 5 또는 K 3,3 이 마이너로 없는 경우에만 평면 입니다.

여기서 K 5 는 5 개의 정점이있는 완전한 그래프이고, K 3,3 은 각 그룹에 3 개의 정점이있는 완전한 이분 그래프입니다. 그래프 A 는 에지 삭제 및 에지 수축의 시퀀스에 의해 B 로부터 획득 될 수있는 경우 , 그래프 B 의 부 이다 .

따라서이 코드는 그래프가 K 5 또는 K 3,3에 동형인지 확인 하고 그렇지 않은 경우 가능한 모든 가장자리 삭제 또는 축소에 대해 재귀 적으로 한 번 호출합니다.

연결되지 않은 그래프의 한 구성 요소에서 가장자리를 삭제하거나 축소하면 거기에있는 모든 정점이 제거되지 않으므로 원하는 동형이 발견되지 않습니다. 따라서이 검색을 입력 그래프의 연결된 각 구성 요소에 개별적으로 적용합니다.

이것은 주어진 입력에 대해 매우 빠르게 작동하지만 가장자리를 몇 개 더 추가하면 치명적으로 오래 걸리고 많은 메모리가 필요합니다.

다음은 들여 쓰기 버전입니다 f(입력에서 그래프 객체를 생성 한 후 명명되지 않은 함수).

f@g_ :=
  EdgeCount@g < 9 ||
  ! (h = g~IsomorphicGraphQ~CompleteGraph@# &)@5 &&
  ! h@{3, 3} &&
  And @@ (f@EdgeDelete[g, #] && f@EdgeContract[g, #] & /@ EdgeList@g)

그리고 이것은 입력을 그래프로 변환하고 f연결된 각 구성 요소를 호출하는 명명되지 않은 함수입니다 .

And @@ (
  f @ Subgraph[g, #] & /@ ConnectedComponents[
    g=Graph[# <-> #2 & @@@ #]
  ]
)&

종료 조건을에서 EdgeCount@g<9로 변경하여 몇 바이트를 절약 할 수 g==Graph@{}있지만 런타임이 크게 줄어 듭니다. 두 번째 테스트 케이스는 30 초가 걸리고 마지막 테스트 케이스는 아직 완료되지 않았습니다.

답변