보자 G - 그래프 V (G) - 정점 E (G) - 에지 V 특히 정점 w한다.빌드 알고리즘 결정
그래프를 구축하기위한 알고리즘 :
//adding v (a new vertex to the graph)
if v has a friend in V (G) then E ← E ∪ {vw|w ∈ V (G)}
G ← (V ∪ v,E)
가 주어진 그래프이 알고리즘으로 구축 된 경우 어떻게 알아낼 수 나에게 적어도 단서를 얻을시겠습니까?
미리 감사드립니다.
G의 차수가 0 인 꼭지점은 마지막 "친숙한"꼭지점이 추가 된 후에 추가되어야합니다. 그들을 제거하십시오. 친구가없는 사람을 도태 한 후에는 "마지막 친숙한 버텍스가 추가되었습니다."라는 것이 식별 가능합니다. 왜냐하면 그것이 모든 것에 붙어 있기 때문입니다. 그것을 찾아서 제거하고 찾기 쉽고 파괴가없는 사람에게 돌아갑니다. 그래프가이 과정에서 완전히 파괴되면 알고리즘에 의해 그래프를 만들 수 있습니다.
찾기 단계에서 우리는 대부분의 모서리가있는 정점을 가져 간다. 그것이 모든 것에 붙어 있지 않다면 우리는 깨어서 아무 말도하지 않습니다. 우리가 모두를 파괴하면 우리는 그렇다고 말합니다. 감사 – sdadffdfd
그래프에 v을 추가 할 때 친구가있는 경우 그래프에 모든 기존 버텍스의 가장자리가 표시됩니다. 그래서 모든 추가는 모서리 나 모서리를 모든 정점에 추가하지 않습니다.
친구가없는 상태에서 추가 된 버텍스는 이후에 추가되는 버텍스에서 가장자리를 얻을 수 있습니다. 추가 된 순서를 알 수 있으면 해당 순서를 재생하고 모든 추가가 0 또는 가능한 모든 모서리를 추가하는지 확인하여 그래프가 가능한지 여부를 확인할 수 있습니다.
주문을 모르는 경우 가장 최근의 버텍스를 제거하여 그래프의 "언 래핑"을 시도해 볼 수 있습니다.
편집 제안 된 알고리즘이 숙제이기 때문에 제거되었습니다 ;-).
감사합니다. 괜찮아, 이해 : – sdadffdfd
친구를 V (G)로 정의하면 – shevski
우정 관계를 알고 있습니까? 아니면 그래프가 있습니까? –
V (G)의 @shevski 친구는 실제 상황이므로 친구 인 경우 2 개의 꼭지점 사이에 E의 가장자리가 있음을 의미합니다. @Gareth no – sdadffdfd