szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 9 paź 2009, o 21:31 
Użytkownik

Posty: 2000
Lokalizacja: Stare Pole/Kraków
Różne problemy teorii gier można rozwiązywać z pomocą narzędzi jakich dostarcza teoria grafów. Każdą grę skończoną możemy reprezentować jako acykliczny graf skierowany (DAG). W grafie takim wierzchołki reprezentują możliwe pozycje w grze, a między dwoma wierzchołkami u,v istnieje krawędź skierowana (u,v) wtedy i tylko wtedy gdy z pozycji u można przejść do pozycji v. Zauważmy że istnieje dokładnie jeden wierzchołek o zerowym stopniu wejściowym, reprezentujący pozycję początkową (P). Ponadto szczególne pozycje, do których dojście oznacza zwycięstwo któregoś z graczy w reprezentujmy przez jeden wierzchołek (K).
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 u nienależącego do jądra istnieje krawędź skierowana (u,v) taka, że 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 G posiada jądro, które jest jednoznacznie wyznaczone.
Dowód: Niech V_1 będzie zbiorem wierzchołków o zerowym stopniu wyjściowym (na mocy spostrzeżenia V_1 nie jest zbiorem pustym). Wszystkie wierzchołki należące do V_1 muszą należeć do jądra G. Niech W_1 będzie zbiorem wierzchołków incydentnych z wierzchołkami w V_1. Na mocy warunku a), żaden wierzchołek należący do 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 W_1 \cup V_1 wraz z incydentnymi z nimi krawędziami. Otrzymamy graf G' który oczywiście też jest DAGiem. W G' analogicznie jak poprzednio wybieramy zbiór należących do jądra wierzchołków o zerowym stopniu wyjściowym V_2, oraz zbiór 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:
Obrazek

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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 własność Darboux a istnienie pierwotnej  olka_k  1
 Rozstrzygnąć istnienie granicy  R?kawiczka  1
 istnienie pierwiastka  Czeczot  19
 Istnienie granicy funkcji - zadanie 2  leg14  0
 istnienie wielomianów  robin5hood  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl