Ciclo periférico

En teoría de grafos , un ciclo periférico (o circuito periférico ) en un grafo no dirigido es, intuitivamente, un ciclo que no separa ninguna parte del grafo de ninguna otra parte. Los ciclos periféricos (o, como se los llamó inicialmente, polígonos periféricos , porque Tutte llamó a los ciclos "polígonos") fueron estudiados por primera vez por Tutte (1963), y juegan papeles importantes en la caracterización de grafos planares y en la generación de los espacios de ciclos de grafos no planares. ^[1]

Definiciones

Un ciclo periférico en un gráfico se puede definir formalmente de una de varias maneras equivalentes: ${\estilo de visualización C}$ ${\estilo de visualización G}$

${\estilo de visualización C}$ es periférico si es un ciclo simple en un gráfico conexo con la propiedad de que, para cada dos aristas y en , existe un camino en que comienza con , termina con y no tiene vértices interiores pertenecientes a . ^[2] $estilo de visualización e_{1}$ $Estilo de visualización e_{2}$ $G\setmenos C$ ${\estilo de visualización G}$ $estilo de visualización e_{1}$ $Estilo de visualización e_{2}$ ${\estilo de visualización C}$
Si es cualquier subgrafo de , un puente ^[3] de es un subgrafo minimal de que es disjunto en sus aristas con y que tiene la propiedad de que todos sus puntos de unión (vértices adyacentes a las aristas tanto en como ) pertenecen a . ^[4] Un ciclo simple es periférico si tiene exactamente un puente. ^[5] ${\estilo de visualización C}$ ${\estilo de visualización G}$ ${\estilo de visualización C}$ ${\estilo de visualización B}$ ${\estilo de visualización G}$ ${\estilo de visualización C}$ ${\estilo de visualización B}$ $G\setmenos B$ ${\estilo de visualización C}$ ${\estilo de visualización C}$
En un grafo conexo que no sea un grafo theta , los ciclos periféricos no pueden tener cuerdas, porque cualquier cuerda sería un puente, separado del resto del grafo. En este caso, es periférico si se trata de un ciclo inducido con la propiedad de que el subgrafo formado al eliminar las aristas y vértices de es conexo. ^[6] ${\estilo de visualización C}$ $G\setmenos C$ ${\estilo de visualización C}$

La equivalencia de estas definiciones no es difícil de ver: un subgrafo conexo de (junto con las aristas que lo unen a ), o una cuerda de un ciclo que hace que no se lo induzca, debe ser en cualquier caso un puente, y también debe ser una clase de equivalencia de la relación binaria en las aristas en la que dos aristas están relacionadas si son los extremos de un camino sin vértices interiores en . ^[7] $G\setmenos C$ ${\estilo de visualización C}$ ${\estilo de visualización C}$

Propiedades

Los ciclos periféricos aparecen en la teoría de grafos poliédricos , es decir, grafos planos conexos con 3 vértices . Para cada grafo plano , y cada incrustación plana de , las caras de la incrustación que son ciclos inducidos deben ser ciclos periféricos. En un grafo poliédrico, todas las caras son ciclos periféricos, y cada ciclo periférico es una cara. ^[8] De este hecho se deduce que (salvo la equivalencia combinatoria, la elección de la cara exterior y la orientación del plano) cada grafo poliédrico tiene una incrustación plana única. ^[9] ${\estilo de visualización G}$ ${\estilo de visualización G}$

En los grafos planos, el espacio de ciclos es generado por las caras, pero en los grafos no planos los ciclos periféricos juegan un papel similar: para cada grafo finito conexo por 3 vértices, el espacio de ciclos es generado por los ciclos periféricos. ^[10] El resultado también se puede extender a grafos localmente finitos pero infinitos. ^[11] En particular, se deduce que se garantiza que los grafos 3-conexos contienen ciclos periféricos. Existen grafos 2-conexos que no contienen ciclos periféricos (un ejemplo es el grafo bipartito completo , para el cual cada ciclo tiene dos puentes) pero si un grafo 2-conexo tiene un grado mínimo de tres, entonces contiene al menos un ciclo periférico. ^[12] $Estilo de visualización K_{2,4}$

Los ciclos periféricos en grafos 3-conexos pueden calcularse en tiempo lineal y se han utilizado para diseñar pruebas de planaridad. ^[13] También se extendieron a la noción más general de descomposiciones de orejas no separadoras. En algunos algoritmos para probar la planaridad de grafos, es útil encontrar un ciclo que no sea periférico, para dividir el problema en subproblemas más pequeños. En un grafo biconexo de rango de circuito menor que tres (como un grafo de ciclo o un grafo theta ) cada ciclo es periférico, pero cada grafo biconexo con rango de circuito tres o más tiene un ciclo no periférico, que puede encontrarse en tiempo lineal. ^[14]

Generalizando los grafos cordales , Seymour y Weaver (1984) definen un grafo estrangulado como un grafo en el que cada ciclo periférico es un triángulo. Caracterizan estos grafos como sumas de clique de grafos cordales y grafos planos maximalistas . ^[15]

Conceptos relacionados

Los ciclos periféricos también se han denominado ciclos no separadores, ^[2] pero este término es ambiguo, ya que también se ha utilizado para dos conceptos relacionados pero distintos: ciclos simples cuya eliminación desconectaría el gráfico restante, ^[16] y ciclos de un gráfico topológicamente incrustado de modo que cortar a lo largo del ciclo no desconectaría la superficie en la que está incrustado el gráfico. ^[17]

En los matroides , un circuito no separador es un circuito del matroide (es decir, un conjunto dependiente mínimo) tal que al eliminar el circuito queda un matroide más pequeño que está conectado (es decir, que no se puede escribir como una suma directa de matroides). ^[18] Estos son análogos a los ciclos periféricos, pero no son lo mismo incluso en los matroides gráficos (los matroides cuyos circuitos son los ciclos simples de un grafo). Por ejemplo, en el grafo bipartito completo , cada ciclo es periférico (tiene solo un puente, un camino de dos aristas) pero el matroide gráfico formado por este puente no está conectado, por lo que ningún circuito del matroide gráfico de es no separador. $Estilo de visualización K_{2,3}$ $Estilo de visualización K_{2,3}$

Referencias

^ Tutte, WT (1963), "Cómo dibujar un gráfico", Actas de la London Mathematical Society , Tercera serie, 13 : 743–767, doi :10.1112/plms/s3-13.1.743, MR 0158387.
^ ab Di Battista, Giuseppe; Eades, Peter ; Tamassia, Roberto ; Tollis, Ioannis G. (1998), Dibujo de gráficos: algoritmos para la visualización de gráficos , Prentice Hall , págs. 74-75, ISBN 978-0-13-301615-4.
^ No debe confundirse con puente (teoría de grafos) , un concepto diferente.
^ Tutte, WT (1960), "Representaciones convexas de grafos", Actas de la London Mathematical Society , Tercera serie, 10 : 304–320, doi :10.1112/plms/s3-10.1.304, MR 0114774.
^ Esta es la definición de ciclos periféricos utilizada originalmente por Tutte (1963). Seymour y Weaver (1984) utilizan la misma definición de ciclo periférico, pero con una definición diferente de puente que se asemeja más a la definición de ciclo inducido para los ciclos periféricos.
^ Esta es, en esencia, la definición utilizada por Bruhn (2004). Sin embargo, Bruhn distingue el caso en el que hay vértices aislados de las desconexiones causadas por la eliminación de . ${\estilo de visualización G}$ ${\estilo de visualización C}$
^ Véase, por ejemplo, el Teorema 2.4 de Tutte (1960), que muestra que los conjuntos de vértices de los puentes están conexos por trayectorias; véase Seymour y Weaver (1984) para una definición de puentes utilizando cuerdas y componentes conexos, y también véase Di Battista et al. (1998) para una definición de puentes utilizando clases de equivalencia de la relación binaria en los bordes.
^ Tutte (1963), Teoremas 2.7 y 2.8.
^ Véanse las observaciones posteriores al teorema 2.8 en Tutte (1963). Como observa Tutte, esto ya lo sabían Whitney, Hassler (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society , 34 (2): 339–362, doi : 10.2307/1989545 , JSTOR 1989545, MR 1501641.
^ Tutte (1963), Teorema 2.5.
^ Bruhn, Henning (2004), "El espacio de ciclo de un grafo localmente finito 3-conectado es generado por sus circuitos periféricos finitos e infinitos", Journal of Combinatorial Theory , Serie B, 92 (2): 235–256, doi : 10.1016/j.jctb.2004.03.005 , MR 2099143.
^ Thomassen, Carsten ; Toft, Bjarne (1981), "Ciclos inducidos no separables en grafos", Journal of Combinatorial Theory , Serie B, 31 (2): 199–224, doi : 10.1016/S0095-8956(81)80025-1 , MR 0630983.
^ Schmidt, Jens M. (2014), "La secuencia de Mondshein", Actas del 41.º Coloquio internacional sobre autómatas, lenguajes y programación (ICALP'14) , Lecture Notes in Computer Science, vol. 8572, págs. 967–978, doi :10.1007/978-3-662-43948-7_80, ISBN 978-3-662-43947-0.
^ Di Battista y col. (1998), Lema 3.4, págs. 75–76.
^ Seymour, PD ; Weaver, RW (1984), "Una generalización de los grafos cordales", Journal of Graph Theory , 8 (2): 241–251, doi :10.1002/jgt.3190080206, MR 0742878.
^ Véase, por ejemplo, Borse, YM; Waphare, BN (2008), "Ciclos no separadores disjuntos de vértices en gráficos", The Journal of the Indian Mathematical Society , New Series, 75 (1–4): 75–92 (2009), MR 2662989.
^ Véase, por ejemplo, Cabello, Sergio; Mohar, Bojan (2007), "Encontrar ciclos no separables y no contráctiles más cortos para grafos topológicamente embebidos", Geometría discreta y computacional , 37 (2): 213–235, doi : 10.1007/s00454-006-1292-5 , MR 2295054.
^ Maia, Bráulio, Junior; Lemos, Manoel; Melo, Tereza RB (2007), "Circuitos no separables y cocircuitos en matroides", Combinatoria, complejidad y azar , Oxford Lecture Ser. Math. Appl., vol. 34, Oxford: Oxford Univ. Press, págs. 162–171, doi :10.1093/acprof:oso/9780198571278.003.0010, ISBN 978-0-19-857127-8, Sr. 2314567{{citation}}: CS1 maint: varios nombres: lista de autores ( enlace ).