인접성 매트릭스 만 주어진 선형 시간의 그래프 속성 확인

그래프와 관련된 문제가 발생했습니다. 레이크 그래프를 정의합시다.인접성 매트릭스 만 주어진 선형 시간의 그래프 속성 확인

이 정점 수준의 정점에 연결되어 그래프도 (1)의 정점이있다 :이 일정한 조건을 충족하는 경우

막내 버텍스 그래프는 퀴 인 2
이 두 번째 꼭지점은 차수 n-2의 다른 꼭지점에 연결되어 있으며 다른 꼭지점은 서로 연결되어 있거나 연결되지 않았을 수 있습니다.

나는 n 개의 꼭지점의 그래프에 대한 인접 행렬을 받았다. 내 임무는 주어진 매트릭스가 나타내는 그래프가 "갈퀴"인지 아닌지를 확인하는 것이다. 캐치는 선형 시간으로 수행되어야한다는 것입니다.

나는 모든 것을 시도했습니다. 인접 목록이있을 때 쉽게 할 수 있지만 주어진 행렬을 사용하여 O (n) 시간이 걸리게하려면 어떻게해야합니까?

2013-11-22 Simon

해시 테이블을 사용하여 각 노드에 대한 카운터를 보관할 때마다 각 노드에 대해 누적 된 인접성을 스캔하기 만하면됩니다. 그런 다음 인접성 1,2 및 n-2 중 하나가 있는지 노드를 확인하십시오. 그것은 O (n)입니다. – RBarryYoung

@RBarryYoung 좀 더 말씀해 주시겠습니까? 나는이 문제가 사소한 것이 아니라고 생각한다. –

최악의 경우 'O (n)'에 대해 100 % 명확하게 나타낼 수 있습니까? (btw. 그것은 정말로 좋은 문제 다 ;-) 그 덕택으로!) –

좋아요. 답변을 찾은 것 같습니다. 그래프가 전갈 그래프인지 과학 검사의 세계에서 내가 제시 한 문제가 호출 되었기 때문에 실제로이 문제를 해결하는 선형 시간 알고리즘이 있습니다!

여기 내가 찾고 있었던 알고리즘을 찾을 수 있습니다. http://www.cs.cornell.edu/courses/cs681/2007fa/Handouts/scorpion.pdf

도움 주셔서 감사합니다!

출처

2013-11-23 16:23:41 Simon

[so] 지침에 더 가까워 지려면 링크에서 충분한 정보를 추출하여 링크를 확인하지 않아도 알고리즘을 이해할 수 있도록 해답을 제시해야합니다. – Dukeling

+1, 나를 위해 지금까지 만난 최고의 문제는 - 그냥 그것에 대해 생각을 멈출 수 없었다 :-) 나는 정말로 그것이 선형 시간에 할 수 있다고 믿었다. 그냥 조금 늦게 대답을 게시 해주세요 ;-) [나는 단지 그것이 무엇인지를 확인하기 위해 저항 할 수 없었습니다] –

글쎄, 당신이 그것을 좋아했기 때문에 기쁘다, pozdrowienia z Gdańska :) – Simon

인접성 매트릭스 만 주어진 선형 시간의 그래프 속성 확인

답변

관련 문제