Sospecho que el diámetro mínimo es $d = \lfloor \log_2 N \rfloor$ . He probado esto por fuerza bruta para $N \le 16$ y también tengo:
- Una prueba de que $d \ge \lfloor \log_2 N \rfloor$ .
- Un método para añadir un emparejamiento que logre $d \le 2 \lfloor \log_2 N \rfloor$ .
Para la prueba: si se parte de un punto final del camino y se explora el grafo aumentado mediante la búsqueda de amplitud, entonces se tiene $2$ opciones para el primer paso (seguir el camino, o tomar el borde de la coincidencia) y como máximo $2$ para cada paso posterior (cada vértice tiene un grado como máximo $3$ y una de las aristas es la que tomamos para entrar en ella. Así que para cada $k \ge 0$ hay a lo sumo $2^k$ vértices en el $k^{\text{th}}$ nivel del árbol de búsqueda de amplitud. Esto nos da como máximo $2^{k+1} - 1$ vértices dentro del primer $k$ niveles, y si el gráfico tiene un diámetro $d$ sabemos que $N \le 2^{d+1} - 1$ . Esto da un límite inferior de $d \ge \lfloor \log_2 N \rfloor$ .
Con la esperanza de que esto sea ajustado, podemos construir un árbol de búsqueda de amplitud en el que ninguno de los vértices se superponga. Ejemplo para $3$ niveles:
![unfinished graph]()
Esto da un gráfico con $2^{d+1}-1$ vértices, que es al menos un vértice más de los que queremos, posiblemente más. Así que podemos eliminar uno o más vértices y unir los restantes de forma arbitraria. En el ejemplo, podemos tomar el siguiente gráfico:
![finished N=14 graph]()
Esto no necesariamente tendrá diámetro $\lfloor \log_2 N \rfloor$ pero garantiza que cada vértice está dentro de $\lfloor \log_2 N \rfloor$ pasos del vértice más a la izquierda. Así que para ir de cualquier vértice a cualquier otro, podemos encontrar caminos de longitud $\lfloor \log_2 N \rfloor$ de cada uno que se encuentran en el vértice más a la izquierda, para un camino que tiene una longitud total $2\lfloor \log_2 N \rfloor$ .
Probablemente podamos hacerlo mejor mediante una elección inteligente de las aristas coincidentes restantes (así como una elección inteligente de cómo encajar las partes desconectadas del camino).
1 votos
La forma que describes te lleva a un callejón sin salida cuando los únicos dos vértices que quedan ya son adyacentes. Dejemos que $N = 6$ y tienes camino $v_1, v_2, \ldots, v_6$ . En primer lugar se conecta $v_1$ y $v_6$ entonces $v_2$ y $v_5$ y no saben qué hacer con $v_3$ y $v_4$ . También la distancia entre $v_1$ y $v_4$ sigue siendo $3$ mientras que otro conjunto de nuevas aristas da el diámetro $2$ : $v_1v_6$ , $v_2v_4$ y $v_3v_5$ .
1 votos
Aha, ¿tienes un método mejor?