En teoría de grafos , los grafos en serie-paralelos son grafos con dos vértices distinguidos llamados terminales , formados recursivamente por dos operaciones de composición simples. Se pueden utilizar para modelar circuitos eléctricos en serie y en paralelo .
Definición y terminología
En este contexto, el término gráfico significa multigraph .
Hay varias formas de definir gráficos en serie-paralelos. 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 que se distinguen, s y t llamado 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 al fusionar las fuentes de X e Y para crear la fuente de Pc y fusionar los sumideros de X e Y para crear el fregadero de Pc .
La composición de la serie Sc = Sc (X, Y) de dos GTT X y Y es un TTG creado a partir de la unión de la desunión de gráficos X y Y mediante la fusión de la pileta 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 en 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.
Definición alternativa
La siguiente definición especifica la misma clase de gráficos. [2]
Definición 2 . Un gráfico es un gráfico SP, si puede convertirse en K 2 mediante una secuencia de las siguientes operaciones:
- Reemplazo de un par de bordes paralelos con un solo borde que conecta sus puntos finales comunes
- La sustitución de un par de bordes incidente a un vértice de grado 2 distinto de s o t con un solo borde.
Propiedades
Cada gráfico 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 solo si tiene un ancho de rama como máximo 2, si y solo si cada componente biconectado es una serie– gráfico paralelo. [4] [5] Los gráficos en serie-paralelos máximos , gráficos a los que no se pueden agregar bordes adicionales sin destruir su estructura en serie-paralelo, son exactamente los 2 árboles .
Los gráficos en serie-paralelo de 2 conexiones se caracterizan por no tener un subgrafo homeomorfo para K 4 . [3]
Los gráficos en serie paralelos también se pueden caracterizar por la descomposición de sus orejas . [1]
Complejidad computacional
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 los gráficos SP, [7] incluida la búsqueda de la máxima coincidencia , máxima independiente set , set mínimo dominante y finalización hamiltoniana . Algunos de estos problemas son NP-completos para gráficos generales. La solución se basa en el hecho de que si se conocen las respuestas para uno de estos problemas para dos gráficos SP, entonces se puede encontrar rápidamente la respuesta para sus composiciones en serie y en paralelo.
Generalización
Los gráficos serie-paralelos generalizados ( 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 aumentados con la tercera operación de supresión de un vértice colgante (vértice de grado 1). Alternativamente, la Definición 1 puede aumentarse con la siguiente operación.
- La combinación de fuente S = M (X, Y) de dos GTT X y Y es un TTG creado a partir de la unión de la desunión de gráficos X y Y mediante la fusión de la fuente de X con la fuente de Y . La fuente y el sumidero de X se convierten en la fuente y el sumidero de P respectivamente.
Un árbol SPQR es una estructura de árbol que se puede definir para un gráfico arbitrario conectado a 2 vértices . Tiene S-nodos, que son análogos a las operaciones de composición en serie en series-gráficos paralelos, P-nodos, que son análogos a las operaciones de composición en paralelo en series-gráficas paralelas, y R-nodos, que no corresponden a series- operaciones de composición paralelas. Un gráfico de 2 conexiones es serie-paralelo si y solo si no hay nodos R en su árbol SPQR.
Ver también
Referencias
- ↑ a b Eppstein, David (1992). "Reconocimiento paralelo de series-gráficas paralelas" (PDF) . Información y Computación . 98 (1): 41–55. doi : 10.1016 / 0890-5401 (92) 90041-D .
- ^ Duffin, RJ (1965). "Topología de redes serie-paralelo". Revista de Análisis y Aplicaciones Matemáticas . 10 (2): 303–313. doi : 10.1016 / 0022-247X (65) 90125-3 .
- ^ a b Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy P. (1999). Clases de gráficos: una encuesta . Monografías SIAM de Matemática Discreta. y aplicaciones. 3 . Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas . págs. 172-174 . ISBN 978-0-898714-32-6. Zbl 0919.05001 .
- ^ Bodlaender, H. (1998). "Un k -arboretum parcial de gráficos con ancho de árbol acotado". Informática Teórica . 209 (1–2): 1–45. doi : 10.1016 / S0304-3975 (97) 00228-4 . hdl : 1874/18312 .
- ^ Hall, Rhiannon; Oxley, James; Semple, Charles; Whittle, Geoff (2002). "Sobre matroides de tres ramas de ancho". Revista de Teoría Combinatoria, Serie B . 86 (1): 148-171. doi : 10.1006 / jctb.2002.2120 .
- ^ Valdés, Jacobo; Tarjan, Robert E .; Lawler, Eugene L. (1982). "El reconocimiento de dígrafos paralelos en serie". Revista SIAM de Computación . 11 (2): 289–313. doi : 10.1137 / 0211023 .
- ^ Takamizawa, K .; Nishizeki, T .; Saito, N. (1982). "Computabilidad en tiempo lineal de problemas combinatorios en gráficos serie-paralelos". Revista de la ACM . 29 (3): 623–641. doi : 10.1145 / 322326.322328 . S2CID 16082154 .
- ^ Korneyenko, NM (1994). "Algoritmos combinatorios sobre una clase de gráficos". Matemáticas aplicadas discretas . 54 (2-3): 215-217. doi : 10.1016 / 0166-218X (94) 90022-1 .Traducido de Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci. , (1984) no. 3, págs. 109-111 (en ruso)