TDL1_2011.pdf

Teoria Gier i Decyzji

Lista nr 1

1. Dla jakich liczb r i p zachodzi [P1, P2] r = [[P1,P2] p ,P2] r/p ?

2. Przedstaw w postaci [P1,P2,P3,P4] (a,b,c,d) następującą mieszankę perspektyw:

a) [[P1,P2] 0.2 ,[P4,P3] 0.5, [P3,P1] 0.1 ] (0.3,0.5,0.2)

b) [P4, [[P1,P2] 0.2 ,[P4,P3] 0.5 ] 0.6 , [P3,P1] 0.1 ] (0.25,0.4,0.35)

3 . Grafem skierowanym nazywamy pare ( X,R ), gdzie X jest skończonym zbiorem elementów,

natomiast R jest relacją na parach elementów zbioru X . Elementy X nazywane są wierzchołkami lub

węzłami grafu. Jeśli wierzchołek x jest w relacji z wierzchołkiem y , tzn. x R y , to mówimy, że para

uporządkowana ( x , y ) jest łukiem o początku w x i końcu w y . Tę zależność często przedstawiamy

graficznie rysując strzałkę od x do y . Mówimy, że x jest poprzednikiem y jeśli ( x , y ) jest łukiem. Zbiór

wszystkich par wierzchołków będących w relacji R nazywamy zbiorem łuków U. Droga od

wierzchołka u do v nazywamy skończony ciąg { x 1 , x 2 ,…, x n } taki, że x 1 = u i x n = v i taki, że x i R x i +1 dla

i =1,…, n -1. Liczbę n -1 nazywamy długością drogi (jest to liczba łuków w tej drodze). Konturem

nazywamy drogę, której początek pokrywa sie z końcem. Łuk ( x , x ) nazywamy pętla. Gałęzią

nazywamy łuk ( x,y ) taki, że x R y lub y R x . Łańcuchem nazywamy skończony ciąg { x 1 , x 2 ,…, x n } taki,

że dla i =1,…, n -1, ( x i , x i +1 ) jest gałęzią. Graf nazywamy spójnym , jeśli dowolne wierzchołki można

połączyć łańcuchem. Wierzchołek bez poprzednika nazywamy korzeniem . Graf skierowany z jednym

korzeniem, taki że od korzenia do każdego wierzchołka , dochodzi jedna i tylko jedna droga nazywamy

drzewem lub dendrytem . Wierzchołkiem końcowym nazywamy element x zbioru X nie pozostający w

relacji do żadnego elementu (tzn. nie istnieje y takie, że x R y ).

a) podaj przykład drzewa posiadającego 12 gałęzi i 3 wierzchołki końcowe (narysuj)

b) podaj przykład grafu spójnego, takiego, że od korzenia do każdego wierzchołka , dochodzi jedna i

tylko jeden łańcuch, ale który nie jest drzewem