Sbírka matematických úloh

Problém jednosměrek

Úloha číslo: 3818

• Řešení

  Indukcí podle počtu přidávaných uší. Každé přidávané ucho celé zorientujeme jedním směrem. Takto dostaneme hledanou orientaci, protože:

  Jsou-li $u$ a $v$ vybrané vrcholy, potom alespoň jeden z nich je na přidávaném uchu.

  Jsou-li oba na přidaném uchu, potom jedna z cest, dejme tomu z $u$ do $v$ odpovídá orientaci ucha. Druhou cestu najdeme tak, že z $v$ postupujeme po směru šipek na konec ucha, z něj podle indukčního předpokladu najdeme orientovanou cestu v původním grafu na začátek ucha a pak cestu dokončíme do $u$.

  Je-li jen jeden vrchol, např. $u$ na uchu, pak hledané cesty lze podobným způsobem sestavit ze dvou částí ucha a vhodnými cestami mezi $v$ a konci ucha $x$ a $y$. Konkrétně, je-li ucho zorientováno $x\to u\to y$, pak najdeme cesty. $u\to y \to v$ a $v \to x \to u$. Obrácená implikace neplatí. Získáme jen hranově dvousouvislý graf. Ve skutčnosti lze předpoklad oslabit a dokázat, že každý hranově dvousouvislý graf má silně souvislou orientaci, tedy tyto dvě třídy grafů jsou shodné.

  Daný graf rozdělíme v artikulacích na dvousouvislé bloky, na které použijeme argument výše. Pak už jen stačí ukázat, že cesty lze napojit v artikulacích.