Diámetro máximo posible de un gráfico no dirigido dado el número de aristas y nodos

Question

El título se explica por sí mismo. Si tengo $V$ nodos y $E$ aristas en un grafo no dirigido conectado, ¿existe una fórmula para determinar un límite superior del diámetro máximo posible? El gráfico exacto es desconocido, pero el número de aristas y el número de vértices sí. Sí sé que cuando $E=V(V-1)/2$ (gráfico completo), el diámetro máximo posible es $1$ y cuando $E=V-1$ (gráfico de líneas), el diámetro máximo posible es $V-1$ pero no tengo ni idea de lo que hay entre medias.

Answer 1

Suponemos que $v \geq n-1$ y $v \leq \frac{n(n-1)}{2}$

Dado $v$ bordes y $n$ nodos, calculemos el número mínimo de nodos $u$ necesario para gastar el exceso de bordes en un agujero de gasto $SH$ :

Sabemos que la saturación de $u$ necesidades de los nodos $\frac{n(n-1)}{2}$ bordes y se mantiene $w = n-u$ aristas para constituir un grafo lineal generador de largas distancias.

En primer lugar, vamos a tratar de minimizar $u$ y maximizar $w$ en :

• $n = w + u$
• $v = w-1 + 1 + \frac{u(u-1)}{2}$

donde $w-1$ es para el subgrafo de larga distancia , $\frac{u(u-1)}{2}$ por el agujero del gasto $SH$ y $1$ borde para unirse a ellos.

• $=> u' = \frac{(3+\sqrt{(8(v-n)+9)})}{2}$
• $=> u = \lceil {u'} \rceil = \lceil {\frac{(3+\sqrt{(8(v-n)+9)})}{2} }\rceil$ ,

$ceil(u')$ porque tratamos con números enteros y $u'$ era sólo un límite calculado.

A continuación, calculamos los nodos restantes $n-u$ , tomamos de la $SH$ tantas aristas como sean necesarias para alcanzar $n-u$ y podemos calcular la distancia $d = n-u +1$ que hay que añadir $1$ si el $SH$ está saturado, es decir, si $\frac{u(u-1)}{2}-u= v-n$ .

Aplicación numérica :

/*
main(5,true) :
5 nodes :

for v=4 : 2 nodes will consume 1 edges from 1 ; it remains 3 nodes 3 edges,d =4

      5 : 3                    3               3 ;            2       2             3

      6 : 4                    5               6 ;            1       1             3
      7 : 4                    6               6 ;            1       1             2

      8 : 5                    8              10 ;            0       0             2
      9 : 5                    9              10 ;            0       0             2
     10 : 5                   10              10 ;            0       0             1

Observe cómo la distancia $d$ cambios con los bordes en exceso y cómo disminuye por $1$ cuando el $SH$ está saturado. Recuerdo que el número de aristas está acotado por la pregunta y no podemos tener aristas dobles, ni aristas sin nodos.

function main(n,all)
{
    var u , spent , spentmax , v , V = n*(n-1)/2 , res = n+" nodes :\n" , exm = -1,d , firstline = true ;

    for ( v = n-1 ; v <= V ; v ++ )
    {
        u = Math.ceil( (3+Math.sqrt(8*(v-n)+9))/2 ) ;
        spentmax = (u*(u-1)/2)  ;
        spent = (v-n+u) ;
        if(u!=exm || all )
        {
            if(u!=exm )
            {
                if( all ) res += "\n" ;
                exm = u ;               
            }

            d = 1 + n-u + ( spentmax == spent ? 0 : 1 );
            if( firstline )
                res += ( "for v="+v+" : "+u +" nodes will consume "+spent+" edges from "+spentmax+" ; it remains "+(n-u)+" nodes " + (v-spent) +
                                " edges,d ="+d+"\n" ) ;
            else
                res += ( "      "+v+" : "+u +"                    "+spent+"               "+spentmax+" ;            "+(n-u)+"       " + (v-spent) +
                                "             "+d+"\n" ) ;

            firstline = false ;
        }
    }
    return res ;
}

// scratchpad formalism to get the result by typing CTRL L at the end of the script
var z1 , z2 = main(5,false) ;     // number of nodes and true to get all the intermediate edges steps
z1=z2;

/*
main(12,false) :
12 nodes :
for v=11 : 2 nodes will consume 1 edges from 1 ; it remains 10 nodes 10 edges,d =11
      12 : 3                    3               3 ;            9       9            10
      13 : 4                    5               6 ;            8       8            10
      15 : 5                    8              10 ;            7       7             9
      18 : 6                   12              15 ;            6       6             8
      22 : 7                   17              21 ;            5       5             7
      27 : 8                   23              28 ;            4       4             6
      33 : 9                   30              36 ;            3       3             5
      40 : 10                  38              45 ;            2       2             4
      48 : 11                  47              55 ;            1       1             3
      57 : 12                  57              66 ;            0       0             2    */

Aunque la prueba no es fundamentalmente detallada, se puede ver que la construcción es mínima, partiendo de un gráfico lineal con $v = n-1$ y añadiendo los bordes en exceso en un agujero de gasto ( o un ovillo de lana si se prefiere ). Cuando éste se satura, "sacrificamos" un nuevo nodo hasta una nueva saturación. Cuando todas las aristas en exceso han utilizado un mínimo de nodos, queda un trozo de grafo lineal que se une al $SH$ por una arista a un nodo.

La misma pregunta con la posibilidad de no conexión es interesante también ... Este tipo de problemas tiene muchas aplicaciones cuando el algoritmo puede añadir nodos a su conveniencia (familia de problemas del árbol de Steiner).

ps : siéntase libre de editar y corregir las traducciones oscuras, TY

Answer 2

No se trata de una respuesta completa, sino más bien de una observación que conduce a buenos resultados en algunos casos especiales. Una familia interesante de gráficos a considerar es la siguiente. Tomemos un gráfico completo $K_k$ y dibujar un camino simple de longitud $v-k$ de uno de sus vértices. Lo que se obtiene tiene $v$ vértices, $v-(k^2-3k)/2$ bordes, y el diámetro $v-k+1$ . (El diámetro se alcanza en un punto más alejado de la trayectoria y cualquier vértice en $K_k$ que no está en el camino). Un cálculo sencillo muestra que se puede obtener un gráfico con diámetro $$V-\left\lceil\sqrt{2E-2V+\frac94}+\frac12\right\rceil,$$ $V$ vértices, y $E$ bordes. Nótese que este límite es asintóticamente el mejor posible cuando no hay demasiadas aristas, es decir, cuando $E=o(V^2)$ porque entonces se obtiene un gráfico con diámetro $V+o(V)$ . Se supone que mi límite no es bueno para los grandes $E$ sin embargo.