2
존경받는 선생님,vericed가있는 방향성 그래프의 최대 사이클 수 = | V | 가장자리 = | E |
저는 2 인용 일반형 게임 (게임 이론)을 나타내는 구체적인 그래픽 구조로 작업 중입니다. Tarjans를 통해 O (V + E)에서 유향 그래프의 모든 강하게 연결된 구성 요소를 계산할 수 있지만 강하게 연결된 구성 요소의 모든 단순 사이클을 계산하는 것이 얼마나 복잡한 지 궁금합니다. 그리고 강하게 연결된 구성 요소를 정의하는 정점의 수를 감안할 때 이러한 간단한주기의 수에 대한 알려진 상한이 있습니까?
이 두 가지 문제와 관련된 문학/알고리즘을 찾고 있습니다. 고맙습니다!
완전히 연결된 다이 그래프 (E = V²)에서, 거의 모든 것이주기를 유도하기 때문에 초 폴리 폴리임을 나타냅니다. 악용 될 수있는 구조가 더 있습니까? –
선생님, 저는 'm + n'번 확인을하고 있습니다. 'n'은 프로세스의 수이고 'm'은 리소스의 수입니다. 관계는 프로세스에서 리소스로 또는 리소스에서 프로세스로 진행될 수 있습니다. 최대 가장자리는 m * n.and 그 순전히 방향 그래프입니다 – Learner
누군가 회신 해주십시오 – Learner