¿Cuántos bordes puede tener un gráfico unipático?

19

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 ) .nn12(n1)

¿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 ) ).nO(n)Θ(n2)

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.O(n)

Gilles 'SO- deja de ser malvado'
fuente
Buena pregunta. Deberíamos intentar mejorar tu límite inferior o mi límite superior :).
RB

Respuestas:

12

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)n2/4

Considere un gráfico bipartito completo, con aristas orientadas . Este gráfico es antipático y no tiene ciclo: todas sus rutas tienen longitud 1 . Tiene 2 m de vértices y m 2 aristas.(i,j)[1,m]2,aibj12mm2

(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).

Gilles 'SO- deja de ser malvado'
fuente
"cualquier borde que agregue entre los nodos existentes romperá la propiedad unipática" ¿Cómo agregaría el borde rompería la propiedad? b1a1
mitchus
@mitchus a2b1a1b2
Gilles 'SO- deja de ser malvado'
1
Supongo que mi mente era de alguna manera antipática ese día :) En cuanto a la maximidad, la relación puede ir a 1/4 para grande , pero para n { 2 , 3 , 4 , 5 , 6 } la lista doblemente enlazada tiene más aristas que n 2 / 4 . nn{2,3,4,5,6}n2/4
mitchus
0

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 den2n24Son posibles 2 +3bordes:n22+3

Suponga por contradicción que es un gráfico unipático tal que | E | n 2G=(V,E).|E|n22+3

Por el principio del casillero, existe tal que d en ( v ) nvV

din(v)n2+1

Denote U={uV(u,v)E}

Observe que si hubiera un vértice tal que u 1u 2U : ( x , u 1 ) , ( x , u 2 ) ExV{v}

u1u2U:(x,u1),(x,u2)E

Entonces el gráfico no sería antipático (ya que y ( x u 2v ) son rutas válidas).(xu1v)(xu2v)

Esto significa que (agregando los bordes de ): | E ( V × U ) | 2 | U |{v}×U

|E(V×U)|2|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

|E|=|E(V×U)|+|E(V×(VU))|
2|U|+n|VU|2(n2+1)+n(n21)<n22+3

RB
fuente