17 lines
1.4 KiB
TeX
17 lines
1.4 KiB
TeX
\chapter{Lista problemów \NPC}
|
|
\begin{table}[H]
|
|
\centering
|
|
\renewcommand{\arraystretch}{1.4}
|
|
\begin{tabularx}{\linewidth}{p{3cm}clX}
|
|
\textbf{Nazwa} & & \textbf{Parametry} & \textbf{Opis} \\ \hline
|
|
\textit{Podziału Zbioru} & \problem{PZ} & $A$ & Czy zbiór $A$ da się podzielić na dwa rozłączne podzbiory tak, żeby suma ich elementów była równa? \\
|
|
\textit{Sumy Podzbioru} & \problem{SP} & $A$, $n \in \mathbb N$ & Czy w zbiorze $A$ istnieje podzbiór, którego elementy sumują się do $n$? \\
|
|
\textit{Kliki} & \problem{KLIKA} & $G$ - graf, $n \in \mathbb N$ & Czy w grafie $G$ znajduje się klika (podgraf pełny) $K_n$? \\
|
|
\textit{Zbioru Niezależnego} & \problem{ZN} & $G$ - graf, $n \in \mathbb N$ & Czy w grafie $G$ znajduje się zbiór niezależny wielkości $n$? \\
|
|
\textit{Ścieżki Hamiltona} & \problem{SH} & $G$ - graf & Czy w grafie $G$ istnieje ścieżka Hamiltona? \\
|
|
\textit{Cyklu Hamiltona} & \problem{CH} & $G$ - graf & Czy w grafie $G$ istnieje cykl Hamiltona? \\
|
|
\textit{Kolorowania Wierzchołkowego} & \problem{KOL} & $G$ - graf, $n$ & Czy graf $G$ da się pokolorować wierzchołkowo za pomocą $n$ kolorów? \\
|
|
\textit{Kolorowania Krawędziowego} & \problem{KOLW} & $G$ - graf, $n$ & Czy graf $G$ da się pokolorować krawędziowo za pomocą $n$ kolorów? \\
|
|
\end{tabularx}
|
|
\end{table}
|