Hispanopedia Wiki
En teoría de grafos , los grafos serie-paralelo son grafos con dos vértices distintos llamados terminales , formados recursivamente mediante dos operaciones de composición sencillas. Se pueden utilizar para modelar circuitos eléctricos en serie y en paralelo .
Definición y terminología
En este contexto, el término grafo significa multigrafo .
Existen varias formas de definir los grafos serie-paralelo.
Primera definición
La siguiente definición sigue básicamente la utilizada por David Eppstein . [ 1 ]
Un grafo de dos terminales ( TTG ) es un grafo 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 mediante la fusión de las fuentes de X e Y para crear la fuente de Pc y la fusión de 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 grafos X e Y al fusionar 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 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 una sola arista K 2 con terminales asignados.
Definición 1. Finalmente, un grafo se denomina serie-paralelo ( SP ), si es un TTSPG cuando dos de sus vértices se consideran fuente y sumidero.
De manera similar, se pueden definir digrafos serie-paralelo , construidos a partir de copias de grafos de un solo arco, con arcos dirigidos desde el origen hasta el destino.
Segunda definición
La siguiente definición especifica la misma clase de grafos. [ 2 ]
Definición 2. Un grafo es un grafo SP si puede transformarse en K 2 mediante una secuencia de las siguientes operaciones:
- Sustitución de un par de aristas paralelas por una sola arista que conecta sus extremos comunes.
- Sustitución de un par de aristas incidentes a un vértice de grado 2 distinto de s o t por una sola arista.
Propiedades
Todo grafo serie-paralelo tiene un ancho de árbol como máximo 2 y un ancho de rama como máximo 2. [ 3 ] De hecho, un grafo 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 biconectada 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-paralelo, son exactamente los 2-árboles .
Los grafos serie-paralelo 2-conectados se caracterizan por no tener ningún subgrafo homeomorfo a K 4 . [ 3 ]
Los grafos en serie y en paralelo también pueden caracterizarse por sus descomposiciones en orejas . [ 1 ]
Complejidad computacional
Los gráficos SP se pueden reconocer en tiempo lineal [ 6 ] y su descomposición en serie-paralelo también se puede construir 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 , ya que varios problemas estándar de grafos se pueden resolver en tiempo lineal en grafos SP, [ 7 ] incluyendo la búsqueda del emparejamiento máximo , el conjunto independiente máximo , el conjunto dominante mínimo y la completación 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 se puede encontrar rápidamente la respuesta para sus composiciones en serie y en paralelo.
Generalización
Los grafos generalizados serie-paralelo ( 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 exteriores planares .
Los grafos 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 puede aumentarse con la siguiente operación.
- La fusión de fuentes S = M ( 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 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 S respectivamente.
Un árbol SPQR es una estructura de árbol que se puede definir para un grafo arbitrario con 2 vértices conexos . Posee nodos S, análogos a las operaciones de composición en serie de los grafos serie-paralelo; nodos P, análogos a las operaciones de composición en paralelo de los grafos serie-paralelo; y nodos R, que no corresponden a las operaciones de composición en serie-paralelo. Un grafo con 2 vértices conexos es serie-paralelo si y solo si no contiene nodos R en su árbol SPQR.
Véase también
Referencias
- 1 2 Eppstein, David (1992). "Reconocimiento paralelo de grafos serie-paralelo" (PDF) . Information and Computation . 98 (1): 41– 55. doi : 10.1016/0890-5401(92)90041-D .
- ↑ Duffin, RJ (1965). "Topología de redes serie-paralelo" . Journal of Mathematical Analysis and Applications . 10 (2): 303– 313. doi : 10.1016/0022-247X(65)90125-3 .
- 1 2 Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy P. (1999). Clases de grafos: una revisión . Monografías SIAM sobre matemáticas discretas y aplicaciones. Vol. 3. Filadelfia, PA: Society for Industrial and Applied Mathematics . págs. 172–174 . ISBN 978-0-898714-32-6. Zbl 0919.05001 .
- ↑ Bodlaender, H. (1998). "Un k -arboreto parcial de grafos con ancho de árbol acotado". Theoretical Computer Science . 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 ancho de rama tres" . Journal of Combinatorial Theory, Series B. 86 ( 1): 148–171 . doi : 10.1006/jctb.2002.2120 .
- ↑ Valdes, Jacobo; Tarjan, Robert E. ; Lawler, Eugene L. (1982). "El reconocimiento de digrafos paralelos en serie". SIAM Journal on Computing . 11 (2): 289– 313. doi : 10.1137/0211023 .
- ↑ Takamizawa, K.; Nishizeki, T. ; Saito, N. (1982). "Computabilidad en tiempo lineal de problemas combinatorios en grafos serie-paralelo" . Journal of the ACM . 29 (3): 623– 641. doi : 10.1145/322326.322328 . S2CID 16082154 .
- ↑ Korneyenko, NM (1994). "Algoritmos combinatorios en una clase de grafos" . 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, pp. 109–111 (en ruso)
- Familias de grafos
- operaciones gráficas
- Grafos planares
