Problém jednosměrek

Úloha číslo: 3818

Ulice a křižovatky v malém městečku tvoří graf – křižovatky si představujeme jako vrcholy a ulice jako hrany grafu. Dokažte, že je-li graf dvousouvislý, potom lze ze všech ulic udělat jednosměrky tak, aby bylo možno projet autem z každé křižovatky na každou jinou křižovatku bez porušení dopravních předpisů. (Takové orientaci se říká silně souvislá orientace.)

Rozhodněte, zdali platí i obrácená implikace: „Má-li graf silně souvislou orientaci, pak je dvousouvislý.“

  • Ř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.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze