Úlohy na pravděpodobnost a grafy

• [druhá procházka, 3 body] (To je ten příklad z cvičení.) Máte síť \( (1..k) \times \mathbb{N} \), panďulák začíná v bodě (1, 1), z libovolného bodu (i, j) se v jednom kroku pohne s pravděpodobností p do bodu (i+1, j), s pravděpodobností (1-p) do bodu (i, j+1). Procházku končí v libovolném bodě tvaru (k, l), kde \( l \in \mathbb{N} \). S jakou pravděpodbností skončí ve kterém bodě?
• [kombinace grafů, 2 body] Ověřte existenci grafů (tj. uveďte příklad, nebo dokažte neexistenci) na alespoň dvou vrcholech, které splňují následující dvojice podmínek. Implikuje některá z dvojice podmínku druhou?
  • Bipartitní graf; strom.
  • Kružnice; úplný graf.
  • Kružnice, bipartitní graf.
• [doplněk, 5 bodů] Graf H nazveme doplňkem jiného grafu G na stejné množině vrcholů, má-li H hrany mezi těmi vrcholy, mezi kterými je G nemá, a naopak. (Úplný graf a prázdný graf jsou si doplňky. Kružnice na čtyřech vrcholech a graf složený ze dvou cest (každé na dvou vrcholech) jsou si doplňky.)
  • Pro která n může mít bipartitní graf na n vrcholech jako doplněk taktéž bipartitní graf?
  • Může být doplněk bipartitního grafu souvislý?