각 꼭지점이 최소한 p 인 그래프의 최대 서브 세트 크기 찾기

무향 그래프가 주어 졌을 때. 각 꼭지점이 atleast p에있는 그래프의 꼭지점의 최대 서브 세트의 크기를 찾는 방법. 부분 집합의 차수는 부분 집합의 꼭지점 중에서 만 찾을 수 있습니다.각 꼭지점이 최소한 p 인 그래프의 최대 서브 세트 크기 찾기

무엇을 시도 했습니까? 이것은 좋은 문제입니다 (일단 올바른 방법으로 살펴보면 쉬운 해결책이 있습니다). 그러나 나는 그것을 즉시주지 않을 힌트를 찾기 위해 고심하고 있습니다. – us2012

그것은 일종의 도적 인 것 같습니다. NP-Hard이지만 크기의 쿼리만으로 인한 그래프 유형 문제는 해결할 수있는 방법이 있습니다. 크기를 최대화하면 최대 매칭 알고리즘을 사용할 수있는 힌트를 얻지 만 매칭시 모델링 시간을 소비 한 후에도 성공은 없습니다. –

어때? 원래 그래프를 보아라. 어떤 정점은 당신이 찾고있는 부분 집합의 일부가 될 수 없습니까? – us2012

p보다 작은 도의 꼭지점은 절대로 솔루션의 일부가 될 수 없습니다. 가장자리를 포함하여 완전히 제거하십시오. 새 그래프를보고 반복하십시오.

이 프로세스가 중지되면 모든 꼭지점의 차수는 적어도 p입니다.

그런 다음 그래프의 연결된 구성 요소를보고 가장 큰 그래프를 선택하십시오! (Evgeny Kluev가 올바르게 지적했듯이, 물론 불필요합니다. 내 머리 속에는 나머지 부분 그래프가 연결되어 있어야합니다. 물론 원래의 문제는 그러한 요구를하지 않습니다.)

2013-03-09 10:49:31 us2012

좋은 해결책. 마지막 부분 (연결된 구성 요소 포함) 만 필요하지 않습니다. –

@EvgenyKluev 아! 그래 네가 맞아. 나는 혼란스러워했다 :) – us2012

답변