5 개의 노드가 있습니다.이 그래프의 관절 점은 무엇입니까?
가장자리 :
1 -> 2
2 -> 3
2 -> 4
4 -> 5
(그래픽 이미지 : http://i.imgur.com/hafBv.jpg)
관절 점이 n이라고 생각하면 정확합니다. 오드 2와 4? (당신은 노드 2 또는 노드 4를 제거하면, 그래프는 연결이 해제)
하지만 모든 곳에서 본 적이 정의는 비슷한 말한다 :
유, 조음 포인트 인 노드를 모든위한 경우 u의 자식 v는 v에서 u보다 DFS 트리의 상위 노드까지 백 에지가 없습니다.
어떻게 이것이 유향 그래프에서 작동합니까? 예를 들어, 노드 3에는 DFS 트리의 상위 노드에 대한 뒤쪽 가장자리가 없습니다. 노드 3을 관절 지점으로 분류합니까? 그러나 그것의 제거는 그래프를 2 개 이상의 조각으로 나눌 수 없습니다 (즉, 관절 노드의 내 평신도 정의입니다).
면책 조항 : 내 기억이 모호합니다.
지향성 그래프에는 3 가지 연결성이 있습니다.
모든 정점에서 다른 모든 정점까지의 경로가있는 경우 "강력하게 연결됨" 두 노드 사이에 경로가 있지만 양방향으로는 연결되어 있지 않은 경우 "연결됨". 호가 방향이없는 호로 대체 된 경우에만 그래프가 연결되면 약하게 연결됩니다.
예 1> 2 > 3 2, 3> 1 강하게 연결, 당신은 모든 다른 노드
1> 2로 모든 노드에서 얻을 수 2> 3 당신이 할 수있는 3시에서 1 시까 지 1시에서 3 시까 지 연결되므로 연결됩니다.
1-> 2, 3-> 2 1에서 3 또는 3에서 1로 갈 방법이 없으므로 약하게 연결되어있다.
관절 점은 노드의 연결 유형에 따라 다릅니다.
3에서 4까지 또는 4에서 3으로 갈 길이 없기 때문에 그래프가 약하게 연결되어 있습니다. 그러면 관절 점에 대해 이야기하는 것이 유익한 유일한 방법은 호를 무향 처리하는 것입니다 . 당신이 말했듯이 2와 4가 관절 점이됩니다.
관절 지점에는 항상 자식과 부모가 있어야합니다. 이것은 정의에서 누락되어 노드 1과 노드 3을 아티팩트 포인트로 만드는 반면 무언가입니다.
또한 노드 3에 대한 추론에서 노드 자체는 자식이 아니라고 간주합니다. 정의를주의 깊게 적용하면 자녀를 대신 고려해야합니다. 귀하의 경우 - 비어있는 집합 및 확장 정의에 따라 3은 더 이상 관절 지점이 아닙니다. 이 (DEF)에서 조음 포인트가 될 수 있도록
Node 3 does not have a back edge to a node higher in the DFS tree than 2
노드 3 나던, 아이들이있다. 이 정의를 지시 트리의 컨텍스트에 넣으면 관절 점은 루트 노드와 리프 노드를 제외한 모든 점입니다.
그러나 우리가 무 방향성 그래프를 풀기 위해 사용한 방법을 따르면 노드에 대한 존중 (num, low) 값은 node-1 (1,1) 2 (2,2), 노드 3 , 3), 노드 4 (4,4), 노드 5 (5,5). 그래서 관절 점의 def를 따라 가서 자식 2 개가있는 노드를 찾고 (낮은 (자식)> num (노드)) 을 얻으면 우리는 노드 2 만 얻음으로써 관절 지점이됩니다. 그러나 이론은 아직 연결 그래프이므로 모든 노드가 도달 할 수 있지만 우리가 발견 할 때 우리는 나무와 뒤 가장자리를 처리해야하며 나머지는 무향 그래프와 동일하므로 적용 할 수 있습니다.
첫 번째 포인트는 그가 제공 한 def의 결과입니다. – UmNyobe
@UmNyobe 사실이 아닙니다. '모든 x에 대해'라는 표현은 'x가 존재 함'을 의미하지 않습니다. 이것은 평범한 논리입니다. –