MOKIP 07.03.2012

Graf tam gdzie go nie widać (od razu)

  1. Zadanie Spokojna Komisja z VIII OI, kod
  2. Zadanie Sumy z X OI, kod

Dokończenie Spokojnej Komisji.
Przyjmę, że kolega $v$ to $v'$. Wyjaśnienie dlaczego gdy nie udało nam się uzbierać zachłannie $n$ osób do parlamentu, to na pewno się nie da ułożyć dobrego parlamentu w żaden inny sposób:
Zgodnie z naszym założeniem musi istnieć takie $x$, że $x$ oraz $x'$ nie zostali wzięci do parlamentu. Zatem silnie spójne składowe w których się znajdują otrzymały wartość 0, z powodu jakichś innych wierzchołków. Jeśli $x$ oraz $x'$ należą do jednej silnie spójnej składowej, to jasnym jest, że nie da się utworzyć dobrego parlamentu. Zajmijmy się więc przypadkiem, gdy $x$ i $x'$ należą do różnych SSS. Niech $A$ oznacza SSS do której należy $x$, przez $y$ oznaczmy taki wierzchołek w parlamencie, który wyzerował $A$, czyli $y' \in A$. Istnieje pewien cykl wymuszeń $C$ w $A$ do którego należą $x$ i $y'$. Potrzebna nam będzie prosta obserwacja: jeżeli $a$ wymusza $b$, to $b'$ wymusza $a'$ (bo $a$ nie lubi $b'$). Wobec tej obserwacji otrzymujemy, że istnieje cykl wymuszeń $C'$ złożony ze 'sprimowanych' wierzchołków cyklu $C$, w szczególności $x',y\in C'$ oraz krawędziami zorientowanymi w drugą stronę. Ale skoro $x'$ oraz $y$ leżą na cyklu, to należą też do jednej SSS, czyli $x'$ jest w parlamencie (bo SSS w której jest $y$ jest 'zjedynkowana'). Zatem dochodzimy do sprzeczności. Dowiedliśmy nawet, że parlamentu nie da się sformować wtedy i tylko wtedy, gdy $x$ i $x'$ należą do jednej SSS.