Un gráfico unipático es un gráfico dirigido de tal manera que existe como máximo una ruta simple desde cualquier vértice a cualquier otro vértice.
Los gráficos unipáticos pueden tener ciclos. Por ejemplo, una lista doblemente vinculada (¡no circular!) Es un gráfico unipático; si la lista tiene elementos, el gráfico tiene n - 1 ciclos de longitud 2, para un total de 2 ( n - 1 ) .
¿Cuál es el número máximo de aristas en un gráfico unipático con vértices? Un límite asintótico sería suficiente (por ejemplo, O ( n ) o Θ ( n 2 ) ).
Inspirado por Buscar caminos más cortos en un gráfico unipathic pesado ; en mi prueba , inicialmente quería afirmar que el número de aristas era pero luego me di cuenta de que limitar el número de ciclos era suficiente.
fuente
Respuestas:
Un gráfico unipático puede tener aristas. Hay un tipo bien conocido de gráfico que es unipathic y tiene n 2 / 4 bordes.Θ ( n2) norte2/ 4
(Pregunta de seguimiento: ¿es esta relación máxima? Probablemente no, pero no tengo otro ejemplo. Este ejemplo es máximo en el sentido de que cualquier borde que agregue entre los nodos existentes romperá la propiedad antipática).
fuente
No sé si hay un gráfico unipático en más de aristas, pero aquí hay un argumento que muestra que no más den2norte24 4 Son posibles 2 +3bordes:norte22+ 3
Suponga por contradicción que es un gráfico unipático tal que | E | ≥ n 2G = ( V, E) .El | miEl | ≥ n22+ 3
Por el principio del casillero, existe tal que d en ( v ) ≥ nv ∈ V
DenoteU= { u ∈ V∣ ( u , v ) ∈ E}
Observe que si hubiera un vértice tal que ∃ u 1 ≠ u 2 ∈ U : ( x , u 1 ) , ( x , u 2 ) ∈ Ex ∈ V∖ { v }
Entonces el gráfico no sería antipático (ya que y ( x → u 2 → v ) son rutas válidas).( x → u1→ v ) ( x → u2→ v )
Esto significa que (agregando los bordes de ): | E ∩ ( V × U ) | ≤ 2 | U |{ v } × U
Entonces, el promedio en grados de vértices de es como máximo 2, por lo tanto: | E | = | E ∩ ( V × U ) | + | E ∩ ( V × ( V ∖ U ) ) | ≤ 2 | U | + n | V ∖ U | ≤ 2 ( nU
fuente