En teoría de grafos , los grafos serie-paralelo son grafos con dos vértices diferenciados llamados terminales , formados recursivamente mediante dos operaciones de composición simples. Pueden utilizarse para modelar circuitos eléctricos en serie y en paralelo .
En este contexto, el término gráfico significa multigráfico .
Existen varias formas de definir grafos en serie-paralelo. La siguiente definición básicamente sigue la utilizada por David Eppstein . [1]
Un gráfico de dos terminales (TTG) es un gráfico con dos vértices distinguidos, s y t , llamados fuente y sumidero , respectivamente.
La composición paralela Pc = Pc(X,Y) de dos TTG X e Y es un TTG creado a partir de la unión disjunta de los grafos X e Y fusionando las fuentes de X e Y para crear la fuente de Pc y fusionando los sumideros de X e Y para crear el sumidero de Pc .
La composición de la serie Sc = Sc(X,Y) de dos TTG X e Y es una TTG creada a partir de la unión disjunta de los grafos X e Y mediante la fusión del sumidero de X con la fuente de Y. La fuente de X se convierte en la fuente de Sc y el sumidero de Y se convierte en el sumidero de Sc .
Un grafo serie-paralelo de dos terminales (TTSPG) es un grafo que puede construirse mediante una secuencia de composiciones en serie y en paralelo a partir de un conjunto de copias de un grafo de arista única K 2 con terminales asignados.
Definición 1. Finalmente, un grafo se denomina serie-paralelo (grafo SP) si es un TTSPG cuando algunos de sus dos vértices se consideran fuente y sumidero.
De manera similar, se pueden definir dígrafos serie-paralelos , construidos a partir de copias de grafos de arco único, con arcos dirigidos desde la fuente hasta el sumidero.
La siguiente definición especifica la misma clase de gráficos. [2]
Definición 2. Un gráfico es un SP-gráfico si puede convertirse en K 2 mediante una secuencia de las siguientes operaciones:
Todo grafo serie-paralelo tiene un ancho de árbol como máximo de 2 y un ancho de rama como máximo de 2. [3] De hecho, un grafo tiene un ancho de árbol como máximo de 2 si y solo si tiene un ancho de rama como máximo de 2, si y solo si cada componente biconectado es un grafo serie-paralelo. [4] [5] Los grafos serie-paralelos máximos , grafos a los que no se pueden agregar aristas adicionales sin destruir su estructura serie-paralela, son exactamente los 2-árboles .
Los grafos en serie-paralelo 2-conectados se caracterizan por no tener ningún subgrafo homeomorfo a K 4 . [3]
Los gráficos en serie paralelos también pueden caracterizarse por sus descomposiciones en orejas . [1]
Los gráficos SP pueden reconocerse en tiempo lineal [6] y su descomposición en serie-paralelo también puede construirse en tiempo lineal.
Además de ser un modelo de ciertos tipos de redes eléctricas, estos grafos son de interés en la teoría de la complejidad computacional , porque una serie de problemas de grafos estándar se pueden resolver en tiempo lineal en grafos SP, [7] incluyendo la búsqueda de la máxima coincidencia , el máximo conjunto independiente , el mínimo conjunto dominante y la completitud hamiltoniana . Algunos de estos problemas son NP-completos para grafos generales. La solución aprovecha el hecho de que si se conocen las respuestas para uno de estos problemas para dos grafos SP, entonces uno puede encontrar rápidamente la respuesta para sus composiciones en serie y en paralelo.
Los grafos serie-paralelos generalizados (grafos GSP) son una extensión de los grafos SP [8] con la misma eficiencia algorítmica para los problemas mencionados. La clase de grafos GSP incluye las clases de grafos SP y grafos outerplanares .
Los grafos GSP pueden especificarse mediante la Definición 2 ampliada con la tercera operación de eliminación de un vértice colgante (vértice de grado 1). Alternativamente, la Definición 1 puede ampliarse con la siguiente operación.
Un árbol SPQR es una estructura de árbol que se puede definir para un grafo conexo de 2 vértices arbitrario . Tiene nodos S, que son análogos a las operaciones de composición en serie en grafos serie-paralelos, nodos P, que son análogos a las operaciones de composición en paralelo en grafos serie-paralelos, y nodos R, que no corresponden a las operaciones de composición en serie-paralelo. Un grafo conexo de 2 vértices es serie-paralelo si y solo si no hay nodos R en su árbol SPQR.