Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
\subsection{Ograniczenie górne}
Rozpatrzmy zbiór $F =\{S_1,\ldots,S_n\}$ rozłącznych odcinków prostych na płaszczyźnie oraz graf $G(F)$ zawierający $n$ wierzchołków $v_1$,\ldots,$v_n$ takich, że $v_i$ jest sąsiedni z $v_j$ wtedy i tylko wtedy, gdy istnieje punkt $x$ na płaszczyźnie, który widzi przynajmniej jeden punkt na odcinku $S_i$ i $S_j$ tzn. $x$ strzeże oba odcinki $S_i$ oraz $S_j$ \ref{fig:zbior odcinkow rozlacznych}.
Aby udowodnić twierdzenie \ref{straznicy strzezenie} na początku wykażemy, że dla każdego zbioru $F$ rozłącznych odcinków prostych, których jest parzysta liczba $n$, odpowiednio zdefiniowany graf $G(F)$ ma doskonałe skojarzenie (rysunek \ref{fig:zbior odcinkow rozlacznych})
\begin{figure}[ht!]
\centering
\includegraphics{rysunki/g_f.png}
\caption{Zbiór $F$ rozłącznych odcinków oraz odpowiadający mu graf $G(F)$.}
\label{fig:zbior odcinkow rozlacznych}
\end{figure}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment