\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
