\input /home/pasky/school/fastex/lib.tex

\subchapter{2--souvislost}{

	\definition{
		Graf $G = (V,E)$ je {\bf (vrcholově) 2--souvislý}, pokud $|V|\ge3$ a $G-v$ je souvislý pro $\forall v \in V$.
	}

	\example{
		\asciiart{
o - o
|     > o   2--souvislý
o - o
}

		\asciiart{
  o   o
 / \ / \
o   o   o   není 2--souvislý (ale je hranově 2--souvislý)
 \ / \ /
  o   o
}
	}

	\observation{
		$G$ je 2--souvislý $\Rightarrow$ $\cases{G+e & 2--souvislý pro $\forall e \notin E$.\cr
		                                         G-e & souvislý pro $\forall e \in E$.\cr
							 G\,\%\,e& 2--souvislý pro $\forall e \in E$.}$

		\proof{
		\list{
			\namedListItem{a}{zřejmé}

			\namedListItem{b}{$e = \{x,y\} \in E$
			
				$G-x$ souvislý $\Rightarrow$ $y$ je v $G - e$ v jedné komponentě se všemi vrcholy $v \ne x,y$.

				$G-y$ souvislý $\Rightarrow$ $x$ je v $G - e$ v jedné komponentě se všemi vrcholy $v \ne x,y$.

				Tedy $G-e$ má určitě jednu komponentu, takže je souvislý.
			}

			\namedListItem{c}{
\asciiart{
     e
 x ----- y  -->  x - z - y
.
     G               G'
}

				$G'-v$ souvislý $\forall v \ne z$. $G'-z = G-e$ souvislý podle (b).

			}
		}
		\qed

		}
	}


	\definition{
		Grafy $G=(V,E)$ je {\bf hranově 2--souvislý}, pokud $G$ je souvislý a $G-e$ je souvislý pro $\forall e \in E$.

	}


	\theorem{}{}{
		$G$ je 2--souvislý $\Leftrightarrow$ $G$ vznikne z $K_3 = \triangle$
		postupným přidáváním a dělením hran.

		\TODO{Obrázek úplného trojúhelníčku s vrcholem uprostřed a jeho odvození z trojúhelníčku.}

		\proof{
			\proofrightimpl{
				$\triangle$ je 2--souvislý, přidávání a dělení hran uchovává 2--souvislost.

			}

			\proofleftimpl{
				Nebudeme dělat.

			}

			\qed
		}
	}

	\theorem{}{}{
		V 2--souvislém grafu leží každé 2 vrcholy na společné kružnici.

		\proof{
			Podle předchozí věty stačí dokázat:
			\list{
			\listItem{Věta platí pro $\triangle$. Triviální.}
			\listItem{Věta platí pro $G$ $\Rightarrow$ platí i pro $G+e$ (triviální).}
			\listItem{Věta platí pro $G$ $\Rightarrow$ platí i pro $G\,\%\,e$:

				Nechť $u \in V(G)$, $z \in V(G') \setminus V(G)$ (vytvořený na $e=(x,y)$).
				Leží $u,z$ na společné kružnici? (Ostatní případy jsou triviální.)

				$C = $ kružnice v $G$ společná pro $x,u$.

				\list{
					\listItem{$y \in C$ --- \TODO{Obrázek D1}
					}
					\listItem{$y \notin C$ --- \TODO{Obrázek D2}

						$P = $ nejkratší cesta z $y$ do $V(C)$ v $G-x$.
						Pak nová kružnice vede z $x$ přes $z$ do $y$,
						pak po $P$ až k nějakému vrcholu $C$ a poté
						po $C$ až zpět k $x$.

					}
				}
			}
			}
		}

		\note{
			V 2--souvislém grafu též každé 2 hrany leží na společné kružnici.
			(Bez důkazu).

		}
	}
}

\bend