Una ruta tiene pesos 4,2,5. Halla coste total.
Suma pesos.
El coste de una ruta se obtiene sumando los pesos de todas las conexiones utilizadas.
Los tres tramos indicados tienen pesos 4,2 y 5, sin que el enunciado añada otro coste.
AB=1,BC=2,AC=6. Halla distancia mínima de A a C.
Compara directo con vía B.
La conexión directa A-C cuesta 6 según el dato AC.
La alternativa A-B-C suma AB+BC=1+2=3 y utiliza las dos conexiones existentes.
Como todos los pesos son positivos y no hay otra ruta simple, el mínimo es 3; repetir ciclos no lo mejora.
Un árbol generador de un grafo de 8 vértices tiene ¿cuántas aristas?
Todo árbol con n vértices tiene n−1.
Un árbol generador contiene todos los vértices del grafo y no tiene ciclos.
Todo árbol con n vértices contiene n−1 aristas, independientemente de sus pesos.
Para los ocho vértices del enunciado, tiene 8−1=7 aristas.
¿Puede aplicarse sin más Dijkstra con una arista negativa?
Revisa su hipótesis.
La garantía de Dijkstra exige que todas las aristas tengan peso no negativo.
Con un peso negativo, una ruta posterior podría mejorar una etiqueta que ya se declaró definitiva.
Por tanto no se aplica sin más; hay que revisar el problema o elegir otro algoritmo compatible con esos pesos.
Un grafo finito, no dirigido y conectado tiene exactamente dos vértices de grado impar. ¿Admite recorrido euleriano abierto?
Usa el criterio de grados.
El grafo cumple las hipótesis de ser finito, no dirigido y conectado.
El criterio euleriano dice que exactamente dos vértices impares permiten un recorrido que usa cada arista una vez y empieza y termina en ellos.
Por tanto sí existe un recorrido euleriano abierto, con esos vértices impares como extremos.