5.7: Una digresión hacia la teoría de la complejidad

Última actualización
Guardar como PDF

Page ID: 118431

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Ya hemos introducido en el Capítulo 4 algunas nociones sobre algoritmos eficientes. También discutimos la dificultad de determinar el número cromático de una gráfica y el número de camarilla anteriormente en este capítulo. Concluimos con una breve discusión de algunos temas que involucran complejidad computacional para otros problemas discutidos en este capítulo.

Comencemos con algunos problemas para los que existen algoritmos polinomiales de tiempo. Supongamos que se le da una gráfica sobre\(n\) los vértices y se le pregunta si la gráfica está conectada o no. Aquí una respuesta positiva puede justificarse proporcionando un árbol de expansión. Por otro lado, una respuesta negativa puede justificarse proporcionando una partición de los conjuntos de vértices\(V=V_1 \cup V_2\) con\(V_1\) y subconjuntos\(V_2\) no vacíos y no teniendo bordes con un punto final adentro\(V_1\) y el otro adentro\(V_2\). En el Capítulo 12 discutiremos dos algoritmos eficientes que encuentran árboles de expansión en gráficas conectadas. Se pueden modificar fácilmente para producir una partición que muestre que la gráfica está desconectada.

Si se le pregunta si una gráfica conectada es euleriana, entonces se puede justificar una respuesta positiva produciendo la secuencia apropiada. Damos un algoritmo para hacer esto antes en el capítulo. Una respuesta negativa puede justificarse produciendo un vértice de grado impar, y nuestro algoritmo identificará dicho vértice si existe. (Dependiendo de las estructuras de datos utilizadas para representar la gráfica, puede ser más eficiente simplemente buscar vértices de grado impar sin usar el algoritmo para encontrar un circuito euleriano).

En la superficie, el problema de determinar si una gráfica es hamiltoniana se parece al de determinar si la gráfica es euleriana. Ambos requieren una secuencia de vértices en la que cada par de vértices consecutivos está unido por un borde. Por supuesto, cada problema tiene un requisito adicional en los certificados de sí. No obstante, justificar una respuesta negativa a la pregunta de si una gráfica es hamiltoniana no es sencillo. El teorema 5.18 sólo da una manera de confirmar que una gráfica es hamiltoniana; hay muchas gráficas no hamiltonianas que no satisfacen su hipótesis. En este momento, nadie sabe cómo justificar eficientemente una respuesta negativa, al menos no en el caso general.