En teoría de grafos , los gráficos en series-paralelas son gráficos con dos vértices distinguidos llamados terminales , formados de forma recursiva mediante dos operaciones de composición simples. Se pueden utilizar para modelar circuitos eléctricos en serie y en paralelo .
En este contexto, el término gráfico significa multigrafo .
Hay varias formas de definir gráficos en series paralelas. La siguiente definición sigue básicamente 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 gráficos 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 en serie Sc = Sc(X,Y) de dos TTG X e Y es un TTG creado a partir de la unión disjunta de los gráficos X e Y fusionando el 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 gráfico en serie-paralelo de dos terminales (TTSPG) es un gráfico que puede construirse mediante una secuencia de composiciones en serie y paralelo a partir de un conjunto de copias de un gráfico de un solo borde K 2 con terminales asignados.
Definición 1 . Finalmente, un gráfico se llama serie-paralelo (gráfico SP) si es un TTSPG cuando dos de sus vértices se consideran fuente y sumidero.
De manera similar, se pueden definir dígrafos en serie-paralelo , construidos a partir de copias de gráficos de un solo arco, 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 gráfico SP, si se puede convertir en K 2 mediante una secuencia de las siguientes operaciones:
Cada gráfico en serie-paralelo tiene un ancho de árbol como máximo 2 y un ancho de rama como máximo 2. [3] De hecho, un gráfico tiene un ancho de árbol como máximo 2 si y sólo si tiene un ancho de rama como máximo 2, si y sólo si cada componente biconectado es una serie. gráfico paralelo. [4] [5] Los gráficos de series paralelas máximas , gráficos a los que no se pueden agregar aristas adicionales sin destruir su estructura de series paralelas, son exactamente los 2 árboles .
Los gráficos de series paralelas de 2 conexos se caracterizan por no tener ningún subgrafo homeomorfo a K 4 . [3]
Los gráficos en series paralelas también pueden caracterizarse por sus descomposiciones de oreja . [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 gráficos son de interés en la teoría de la complejidad computacional , porque una serie de problemas de gráficos estándar se pueden resolver en tiempo lineal en gráficos SP, [7] incluida la búsqueda de la máxima coincidencia , el máximo independiente set , set mínimo dominante y finalización hamiltoniana . Algunos de estos problemas son NP-completos para gráficos generales. La solución aprovecha el hecho de que si se conocen las respuestas a uno de estos problemas para dos gráficos SP, entonces se puede encontrar rápidamente la respuesta para sus composiciones en series y paralelos.
Los gráficos generalizados de series-paralelos (gráficos GSP) son una extensión de los gráficos SP [8] con la misma eficiencia algorítmica para los problemas mencionados. La clase de gráficos GSP incluye las clases de gráficos SP y gráficos planos externos .
Los gráficos GSP pueden especificarse mediante la Definición 2 aumentada con la tercera operación de eliminación de un vértice colgante (vértice de grado 1). Alternativamente, la Definición 1 se puede aumentar con la siguiente operación.
Un árbol SPQR es una estructura de árbol que se puede definir para un gráfico arbitrario conectado con 2 vértices . Tiene nodos S, que son análogos a las operaciones de composición de series en gráficos paralelos en serie, nodos P, que son análogos a las operaciones de composición paralela en gráficos paralelos en serie, y nodos R, que no corresponden a gráficos paralelos en serie. operaciones de composición paralelas. Un gráfico biconexo es serie-paralelo si y solo si no hay nodos R en su árbol SPQR.