Zanim przejdziemy do meritum, potrzebne będzie nam jeszcze pojęcie jądra grafu.
Definicja: Jądrem grafu skierowanego nazywamy zbiór wierzchołków spełniający następujące warunki:
a) jest niezależny
b) dla dowolnego wierzchołka \(\displaystyle{ u}\) nienależącego do jądra istnieje krawędź skierowana \(\displaystyle{ (u,v)}\) taka, że \(\displaystyle{ v}\) należy do jądra.
przyda się nam również następujące
Spostrzeżenie: w każdym DAGu istnieje wierzchołek o zerowym stopniu wyjściowym.
(dowód jest dosyć trywialny, zostawiam jako pracę domową)
jesteśmy już przygotowani, aby udowodnić następujące
Twierdzenie: Każdy DAG \(\displaystyle{ G}\) posiada jądro, które jest jednoznacznie wyznaczone.
Dowód: Niech \(\displaystyle{ V_1}\) będzie zbiorem wierzchołków o zerowym stopniu wyjściowym (na mocy spostrzeżenia \(\displaystyle{ V_1}\) nie jest zbiorem pustym). Wszystkie wierzchołki należące do \(\displaystyle{ V_1}\) muszą należeć do jądra \(\displaystyle{ G}\). Niech \(\displaystyle{ W_1}\) będzie zbiorem wierzchołków incydentnych z wierzchołkami w \(\displaystyle{ V_1}\). Na mocy warunku a), żaden wierzchołek należący do \(\displaystyle{ W_1}\) nie może należeć do jądra. Ponadto wierzchołki te spełniają warunek b). Usuńmy teraz z grafu wszystkie wierzchołki należące do \(\displaystyle{ W_1 \cup V_1}\) wraz z incydentnymi z nimi krawędziami. Otrzymamy graf \(\displaystyle{ G'}\) który oczywiście też jest DAGiem. W \(\displaystyle{ G'}\) analogicznie jak poprzednio wybieramy zbiór należących do jądra wierzchołków o zerowym stopniu wyjściowym \(\displaystyle{ V_2}\), oraz zbiór \(\displaystyle{ W_2}\). Usuwamy wierzcholki z obu tych zbiorów oraz incydentne z nimi krawędzie itd. Postępowanie kontynuujemy tak długo jak to możliwe tj. aż usuniemy z pierwotnego grafu wszystkie wierzchołki.
przykład:
czarne wierzchołki należą do jądra
dla nas jednak ważniejszy niż samo twierdzenie jest płynący z niego Wniosek: w każdej skończonej, dwuosobowej grze o pełnej informacji, w której nie ma remisów, istnieje strategia wygrywająca dla któregoś z graczy.
Dowód: rozpatrzmy przypadek w którym P należy do jądra a K reprezentuje zwycięstwo gracza, który wykonał ostatni ruch zanim gra dobnęła do tej pozycji końcowej. Na początku pierwszy gracz spycha drugiego gracza na pozycję reprezentowaną przez wierzchołek nienależący do jądra. Drugi gracz może (na mocy definicji jądra) zepchnąć rywala na pozycję w jądrze itd. Drugi gracz więc zawsze może zepchnąć rywala na jądro, więc ma strategię wygrywającą. Pozostałe przypadki są analogiczne.
Nie należy podanego wniosku uogólniać na wszystkie gry dwuosobowe. Oto przykład gry która zawsze kończy się zwycięstwem jednego z graczy, ale żaden nie ma strategii wygrywającej:
W tym samym czasie każdy z graczy A i B pisze niezależnie od drugiego na swojej kartce pewną liczbę rzeczywistą. Kto napisze większą liczbę wygrywa. Jeśli napiszą takie same wygrywa gracz A.
Nadmieńmy jeszcze, że gdy dopuszczamy remisy, jeden z graczy ma strategię zapewniającą co najmniej remis.
Gry które mogą ciągnąć się w nieskończoność można odpowiednio zmodyfikować, orzekając remis po kilkukrotnym dojściu do tej samej pozycji.