그래프로 보는 특정 게임의 승리 전략

Question

게임은 다음과 같이 진행됩니다.두 명의 플레이어, 플레이어 1과 플레이어 2가 게임을 하고 있는데, 첫 번째 플레이어가 영웅의 이름을 지정하여 시작합니다. $h_1$, 플레이어 2가 악당으로 응답합니다. $v_1$ 누구와 함께 영화에 출연한 적이 있나요? $h_1$.그런 다음 플레이어 1은 다른 영웅으로 응답합니다. $h_2$ 함께 영화에 출연한 사람 $v_1$, 기타 등등.각 영웅과 악당은 최대 한 번만 사용할 수 있습니다.캐릭터의 이름을 지정할 수 없는 첫 번째 플레이어(사용 가능한 영웅/악당은 다른 플레이어의 마지막 선택과 공통 영화가 없음)가 게임에서 패배합니다.플레이어 1은 항상 게임을 시작합니다.

입력은 영웅 세트입니다. $H$, 악당 세트 $V$ ($ | h | = | v | geq 1 $) 및 영화 가족 $M$, 각 영화는 해당 영화에 등장한 영웅과 악당의 집합입니다.

질문은 ~이야:당신은 기반으로 할 수 있습니까? $H$, $V$ 그리고 $M$, 두 플레이어가 모두 최적으로 플레이한다고 가정하면 어느 플레이어가 게임에서 승리할지 결정하시겠습니까?

---

예:

다음 데이터가 주어지면:영웅들은 아이언 맨, 캡틴 아메리카, 토르 그리고 스파이더 맨.악당들은 편달, 울트론, 타노스 그리고 무자비한 사람.영화는 어벤저스:인피니티 워 (아이언맨, 캡틴 아메리카, 토르, 타노스, 스파이더맨 출연) 스파이더 맨:귀가 (아이언맨, 벌처, 스파이더맨 주연)어떤 플레이어가 승리 전략을 가지고 있는지 결정할 수 있나요?

---

내 접근 방식은 데이터를 두 세트로 분할할 수 있기 때문에 최대 이분 매칭을 사용하여 어떤 플레이어가 승리 전략을 가지고 있는지 알아내는 것입니다. $H$ 그리고 $V$ 그리고 그 두 집합 사이에는 관계가 있습니다.Hopcroft-Karp 알고리즘은 이러한 세트 중 두 개를 가져와 최대 카디널리티를 알아낼 수 있습니다.내가 틀렸다면 정정해주세요:완벽한 일치가 있는 경우 플레이어 2가 승리하고 그렇지 않으면 플레이어 1이 승리합니다.완벽한 일치가 있을 때마다 플레이어 2는 항상 플레이어 1이 명명한 영웅에 대한 답을 가지고 있다는 것을 의미합니다.

이 문제를 어떻게 해결하시겠습니까?최대 이분 매칭보다 더 좋고 효율적인 솔루션이 있습니까?

Answer 1

짧은 대답은, 해당 그래프가 세트를 "포괄"하는 일치를 허용하는 경우에만 플레이어 2가 승리한다는 것입니다. $H$.

---

여기에 약간의 설명이 있습니다.

당신의 생각은 거의 옳습니다.그러나 증명은 직관적이지 않으며 이론적인 질문이거나 승리한 플레이어를 출력하는 것뿐만 아니라 정확한 승리 전략을 설계해야 하는 경우 필요한 일부 세부 사항을 놓칠 수 있습니다.

답변에서 누락된 부분부터 시작하겠습니다.주어진 인스턴스가 완벽한 일치를 허용하는 그래프에 해당한다고 가정합니다.당신의 전략에 따르면, 이 경우에는 선수 2가 승리합니다. 이는 맞습니다.이제 동일한 사례가 한 명의 악당, 또는 10명의 악당 또는 1000명의 악당과 함께 제공된다고 가정합니다.악당을 추가하는 방법에 관계없이 두 번째 플레이어에게만 도움이 되기 때문에 두 번째 플레이어가 여전히 승리합니다.따라서 귀하의 주장이 항상 유효한 것은 아닙니다.그러나 귀하의 답변은 내 주장과 매우 ​​유사하며 동일한 직관을 가지고 있습니다.형식적인 부분이 조금 부족할 뿐입니다.

주장하다. 두 플레이어가 모두 최적으로 플레이한다고 가정하면, 주어진 인스턴스가 있는 경우에만 플레이어 1이 승리합니다. $I$, 해당 그래프는 집합을 포화시키는 일치를 허용하지 않습니다. $H$.

그럼 그게 무슨 뜻인가요?일치는 정점 세트를 포화시킵니다. $S$, 만약 각 정점이 $S$ 일치의 꼭지점에 부수적입니다.이제 우리는 주장을 증명합니다.그래프가 세트를 포화시키는 일치를 인정할 때 플레이어 2에 대한 두 가지 승리 전략을 보여줍니다. $H$ 그래프가 그러한 일치를 허용하지 않는 경우 플레이어 2에 대한 하나입니다.

증거. 이제 그래프가 그러한 일치를 허용한다고 가정합니다.이 일치를 보자 $M$.전략은 다음과 같습니다.플레이어 1이 잃지 않는 한, 각 선택에 대해 $h \in H$ 플레이어 1의 경우 다음을 선택하세요. $v \in V$ 정점이 일치함 $h$ ~에 $M$.

정확성은 플레이어 2의 각 정점이 고유하고 플레이어 1의 선택과 인접하다는 사실(매칭 속성으로 인해)에서 직접적으로 발생합니다.직관적으로 플레이어 1은 어느 시점에서 이동이 부족할 것입니다(아마도 세트의 모든 영웅을 선택한 후). $H$).

이제 그래프가 일치하는 포화를 허용하지 않는다고 가정합니다. $H$, Hall의 정리에 따르면 다음과 같은 부분 집합이 있습니다. $A \subseteq H$, 그렇게 $ | n (a) | <a $.포함 측면에서 최소한의 집합을 선택하십시오.우리는 일치하는 것이 있다고 주장합니다 $M'$ 포화되는 $N(A)$.그렇지 않다고 가정하면 다시 Hall로 인해 하위 집합이 있습니다. $S \하위 기술N(A)$ 그렇게 $ | n (s) | <s $, 그러나 제거 $N(S) \캡 A$ ~에서 $A$ 그리고 $S$ ~에서 $N(A)$ 의 하위 집합을 생성합니다. $A$ 이는 또한 선택의 모순을 형성하는 Hall의 조건과 모순됩니다. $A$ 최소한으로.따라서 일치하는 항목이 있습니다. $M'$ 포화되는 $N(A)$.

이제 전략은 다음과 같습니다.정점을 선택하세요 $A$ 이는 어떤 모서리에도 영향을 미치지 않습니다. $M$.그러한 꼭지점은 다음과 같이 존재합니다. $ | n (a) | <| a | $.처음에는 이 정점을 선택하고 각 선택에 대해 $v \in V$ 플레이어 2 중 정점을 선택하세요 $h \in H$ 일치하는 $v$ ~에 $M'$.

다시 말하지만, 플레이어 2가 어떤 시점에서(아마도 모든 정점을 선택한 후) 움직임이 부족하다는 것을 쉽게 알 수 있습니다. $N(A)$) 따라서 플레이어 1이 승리합니다.