En teoría de grafos, los grafos secuenciales paralelos son grafos con dos vértices diferentes, que se denominan terminales , formados recursivamente mediante dos operaciones simples [1] . Estos gráficos se pueden utilizar para modelar conexiones en serie y en paralelo de circuitos eléctricos .
En este contexto, el concepto de un gráfico implica un multigrafo .
Hay varias formas de definir grafos secuenciales paralelos. La siguiente definición se basa principalmente en la definición [2] de David Eppstein .
Un gráfico con un par de terminales (STP) es un gráfico que tiene dos vértices distintos s y t etiquetados , llamados fuente y sumidero , respectivamente.
Una conexión paralela Pc = Pc(X,Y) de dos gráficos GTP X e Y que no se intersecan es un gráfico con un par de terminales, creado al combinar los gráficos X e Y mediante la fusión de las fuentes X e Y para formar la fuente Pc y la fusión de los sumideros X e Y para formar sumidero del grafo Pc .
La conexión en serie Sc = Sc(X,Y) de dos gráficos GST X e Y que no se cruzan es el gráfico GST creado por la unión de los gráficos X e Y al fusionar el sumidero X con la fuente Y . La fuente del gráfico X se convierte en la fuente de Sc , y el sumidero del gráfico Y se convierte en el sumidero de Sc .
Un gráfico en serie-paralelo con un par de terminales (gráfico PSPP) es un gráfico que se puede obtener como resultado de conexiones en serie y en paralelo de un conjunto de copias de gráficos de un solo borde K 2 con vértices terminales asignados.
Definición 1 . Se dice que un grafo es serial-paralelo si es un POTP y dos de sus vértices están etiquetados como fuente y sumidero.
De manera similar, se pueden definir dígrafos paralelos en serie , que se construyen a partir de copias de gráficos dirigidos con un arco, en cuyo caso el arco se dirige desde la fuente hasta el sumidero.
La siguiente definición da la misma clase de grafos [3] .
Definición 2 . Un grafo es serial-paralelo si puede transformarse en un grafo K 2 usando una secuencia de las siguientes operaciones:
Cualquier gráfico secuencial paralelo tiene un ancho de árbol y un ancho de ramificación que no excede 2 [4] . De hecho, un gráfico tiene un ancho de árbol como máximo de 2 si y solo si tiene un ancho de rama como máximo de 2, y también si y solo si cualquier componente biconectado es un gráfico paralelo-serie [5] [6] . Los gráficos paralelos-serie máximos, gráficos a los que no se pueden agregar bordes adicionales sin destruir la estructura serie-paralelo, son exactamente 2-trees .
Los grafos secuenciales paralelos se caracterizan por la ausencia de un subgrafo homeomorfo al grafo K 4 [4] .
Los gráficos secuenciales paralelos se pueden caracterizar por su descomposición en orejas [2] .
Los gráficos secuenciales paralelos se pueden reconocer en tiempo lineal [7] y sus descomposiciones secuenciales paralelas también se pueden construir en tiempo lineal.
Además de modelar algunos tipos de circuitos eléctricos, estos gráficos son de interés en la teoría de la complejidad computacional , ya que muchos problemas estándar en gráficos se resuelven en tiempo lineal en gráficos GTT [8] , incluida la búsqueda de la máxima coincidencia , el máximo conjunto independiente , el mínimo dominante conjunto y complemento hamiltoniano . Algunos de estos problemas generales de grafos son NP-completos . La razón de esto es el hecho de que si se conocen las respuestas a estos problemas para dos gráficos paralelos en serie, uno puede encontrar rápidamente la respuesta para sus conexiones en serie y paralelo.
El problema de gráficos en serie-paralelo se refiere al problema de enumerar gráficos y pregunta sobre la cantidad de gráficos en serie paralelos que se pueden formar a partir de un número determinado de aristas.
Los gráficos secuenciales paralelos generalizados (GPP-graphs) son una generalización de los gráficos secuenciales paralelos [9] en los que los gráficos tienen la misma eficiencia algorítmica para los problemas mencionados. La clase de gráficos OPP incluye gráficos paralelos en serie y gráficos planos exteriores .
Los gráficos OPP se pueden definir agregando una tercera operación para eliminar los vértices colgantes (vértices de grado 1) en la Definición 2 . De la misma manera, se puede agregar la siguiente operación a la Definición 1 .
Un árbol SPQR es una estructura que se puede definir para un gráfico arbitrario conectado por 2 vértices . La estructura tiene nodos S que son análogos a una conexión en serie en gráficos en serie paralelo, nodos P que son análogos a una conexión en paralelo en gráficos en serie paralelo y nodos R que no corresponden a las operaciones de gráficos en serie paralelo. Un grafo conectado en 2 es secuencial paralelo si y solo si no hay nodos R en el árbol SPQR.