En la teoría de grafos , un ciclo periférico (o circuito periférico ) en un gráfico no dirigido es, intuitivamente, un ciclo que no separa ninguna parte del gráfico 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 desempeñan un papel importante en la caracterización de gráficos planos y en la generación de espacios cíclicos de gráficos no planos. . [1]
Definiciones
Un ciclo periférico en un gráfico se puede definir formalmente en una de varias formas equivalentes:
- es periférico si es un ciclo simple en un gráfico conectado con la propiedad de que, por cada dos aristas y en , existe un camino en eso comienza con , termina con , y no tiene vértices interiores pertenecientes a . [2]
- es periférico si es un ciclo inducido con la propiedad de que el subgrafo formado eliminando los bordes y vértices de está conectado. [3]
- Si es cualquier subgrafo de , un puente [4] de es un subgrafo mínimo de que es de borde disjunto de y que tiene la propiedad de que todos sus puntos de adjuntos (vértices adyacentes a los bordes en ambos y ) pertenece a . [5] Un ciclo simplees periférico si tiene exactamente un puente. [6]
La equivalencia de estas definiciones no es difícil de ver: un subgrafo conectado de (junto con los bordes que lo unen a ), o una cuerda de un ciclo que hace que no se 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 las que dos aristas están relacionadas si son los extremos de un camino sin vértices interiores en. [7]
Propiedades
Los ciclos periféricos aparecen en la teoría de las gráficas poliédricas , es decir, gráficas planas conectadas a 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 gráfico poliédrico, todas las caras son ciclos periféricos y cada ciclo periférico es una cara. [8] De este hecho se deduce que (hasta la equivalencia combinatoria, la elección de la cara exterior y la orientación del plano) cada gráfico poliédrico tiene una incrustación plana única. [9]
En los gráficos planos, el espacio cíclico es generado por las caras, pero en los gráficos no planos los ciclos periféricos juegan un papel similar: por cada gráfico finito conectado a 3 vértices, el espacio cíclico es generado por los ciclos periféricos. [10] El resultado también se puede extender a gráficos localmente finitos pero infinitos. [11] En particular, se deduce que se garantiza que los gráficos de 3 conexiones contienen ciclos periféricos. Existen 2 gráficos conectados que no contienen ciclos periféricos (un ejemplo es el gráfico bipartito completo , para el cual cada ciclo tiene dos puentes), pero si un gráfico de 2 conexiones tiene un grado mínimo de tres, entonces contiene al menos un ciclo periférico. [12]
Los ciclos periféricos en gráficos conectados en 3 se pueden calcular 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 la oreja sin separación. En algunos algoritmos para probar la planaridad de los gráficos, es útil encontrar un ciclo que no sea periférico para dividir el problema en subproblemas más pequeños. En un gráfico biconectado de rango de circuito menor que tres (como un gráfico de ciclo o gráfico theta ), cada ciclo es periférico, pero cada gráfico biconectado con rango de circuito tres o más tiene un ciclo no periférico, que se puede encontrar en tiempo lineal. [14]
Generalizando grafos cordales , Seymour y Weaver (1984) definen un grafo estrangulado como un grafo en el que cada ciclo periférico es un triángulo. Ellos caracterizan estas gráficas como las sumas de clique de gráficas cordales y gráficas planas máximas . [15]
Conceptos relacionados
Los ciclos periféricos también se han denominado ciclos sin separación, [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 incrustado topológicamente de modo que cortar a lo largo del ciclo no desconectaría la superficie en la que está incrustado el gráfico. [17]
En las matroides , un circuito que no se separa es un circuito de la matroide (es decir, un conjunto dependiente mínimo) de modo que al eliminar el circuito se deja una matroide más pequeña que está conectada (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 los mismos incluso en matroides gráficos (los matroides cuyos circuitos son los ciclos simples de un gráfico). Por ejemplo, en el gráfico bipartito completo , cada ciclo es periférico (tiene un solo puente, una ruta de dos bordes) pero la matroide gráfica formada por este puente no está conectada, por lo que no hay circuito de la matroide gráfica de no se separa.
Referencias
- ^ Tutte, WT (1963), "Cómo dibujar un gráfico", Actas de la Sociedad Matemática de Londres , tercera serie, 13 : 743–767, doi : 10.1112 / plms / s3-13.1.743 , MR 0158387.
- ^ a b 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.
- ^ Ésta es, esencialmente, la definición utilizada por Bruhn (2004) . Sin embargo, Bruhn distingue el caso de que tiene vértices aislados de las desconexiones causadas por la eliminación de .
- ^ No confundir con puente (teoría de grafos) , un concepto diferente.
- ^ Tutte, WT (1960), "Representaciones convexas de gráficos", Proceedings of the London Mathematical Society , Third Series, 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 ciclos periféricos.
- ↑ Véase, por ejemplo, el Teorema 2.4 de Tutte (1960) , que muestra que los conjuntos de puentes de vértices están conectados por caminos, véase Seymour y Weaver (1984) para una definición de puentes que utilizan cuerdas y componentes conectados, y también véase Di Battista et al. (1998) para una definición de puentes usando clases de equivalencia de la relación binaria en los bordes.
- ^ Tutte (1963) , Teoremas 2.7 y 2.8.
- ^ Véanse las observaciones que siguen al teorema 2.8 en Tutte (1963) . Como observa Tutte, esto ya era conocido por Whitney, Hassler (1932), "Gráficos planos y no separables", Transactions of the American Mathematical Society , 34 (2): 339–362, doi : 10.2307 / 1989545 , MR 1501641.
- ^ Tutte (1963) , Teorema 2.5.
- ^ Bruhn, Henning (2004), "El espacio cíclico de un grafo localmente finito conectado en 3 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 sin separación en gráficos", Journal of Combinatorial Theory , Serie B, 31 (2): 199-224, doi : 10.1016 / S0095-8956 (81) 80025-1 , MR 0630983.
- ^ Schmidt, Jens M. (2014), "The Mondshein Sequence", Lecture Notes in Computer Science : 967–978, doi : 10.1007 / 978-3-662-43948-7_80 Parámetro desconocido
|conference=
ignorado ( ayuda ) . - ^ Di Battista y col. (1998) , Lema 3.4, págs. 75–76.
- ^ Seymour, PD ; Weaver, RW (1984), "A generalization of chordal graphs", Journal of Graph Theory , 8 (2): 241-251, doi : 10.1002 / jgt.3190080206 , MR 0742878.
- ^ Por ejemplo, ver Borse, YM; Waphare, BN (2008), "Vertex disjoint no separando ciclos en gráficos", The Journal of the Indian Mathematical Society , New Series, 75 (1–4): 75–92 (2009), MR 2662989.
- ^ Por ejemplo, ver Cabello, Sergio; Mohar, Bojan (2007), "Encontrar ciclos más cortos no separables y no contractibles para gráficos incrustados topológicamente", Geometría discreta y computacional , 37 (2): 213-235, doi : 10.1007 / s00454-006-1292-5 , Señor 2295054.
- ^ Maia, Bráulio, Junior; Lemos, Manoel; Melo, Tereza RB (2007), "Circuitos no separadores y cocircuitos en matroides", Combinatoria, complejidad y azar , Oxford Lecture Ser. Matemáticas. Solicitud, 34 , Oxford: Universidad de Oxford. Prensa, págs. 162-171, doi : 10.1093 / acprof: oso / 9780198571278.003.0010 , MR 2314567.