Recompensa por puntuación alta: NOIP2005: Hay cinco puntos A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1) en el avión. .

La respuesta es D

De hecho, el significado de la pregunta es permitirle elegir algunos puntos para conectar de modo que dos puntos cualesquiera puedan conectarse, y la suma de los longitudes de estas líneas Las más cortas, pruébelo y sabrá cómo conectar AD, BD, CD, EA. Simplemente pruebe las preguntas de opción múltiple (si desea programar computadoras, aprenda el algoritmo de Prim y el algoritmo de Kruskal). /p>

Hay n árboles de expansión mínimos. El árbol de expansión de un gráfico de nodos conectado es un subgrafo mínimamente conectado del gráfico original, contiene los n nodos del gráfico original y tiene el número mínimo de aristas. mantener la conectividad gráfica.

Gráfico completo Un gráfico completo es un gráfico en el que cada par de vértices está conectado exactamente por una arista.

Peso El peso es el valor en la ruta definida. Puede entenderse como la distancia entre nodos.

Si quieres estudiar las imágenes en detalle, lo mejor es comprar un libro. Algunas de las preguntas son muy difíciles.