Árbol de expansión

Esto es, cada vértice está en el árbol, pero no hay ciclos.Por otro lado, todos los puentes de G deben estar contenidos en T. Un árbol de expansión o árbol recubridor de un grafo conexo G puede ser también definido como el mayor conjunto de aristas de G que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices.Si se añade una sola arista a un árbol de expansión, se crea un ciclo: los ciclos de ese tipo se denominan ciclos fundamentales.Hay un ciclo fundamental distinto para cada arista; es decir, hay una correspondencia biyectiva (uno a uno) entre ciclos fundamentales y aristas ausentes del árbol de expansión.Para un grafo conexo con V vértices, cualquier árbol de expansión tiene V-1 aristas, y así, un grafo con E aristas tiene E-V+1 ciclos fundamentales.En cualquier árbol de expansión dado, esos ciclos forman una base del espacio de ciclos.Al eliminar una arista del árbol de expansión, los vértices se dividen en dos conjuntos disjuntos (desconectados).El corte fundamental se define como el conjunto de aristas que deben ser eliminados de un grafo G para llegar a la misma división.Por tanto, hay exactamente V-1 cortes fundamentales en un grafo, uno por cada arista del árbol de expansión.La dualidad entre cortes y ciclos fundamentales se manifiesta al observar que las aristas de un ciclo que no pertenece al árbol de expansión sólo pueden aparecer en los cortes de otras aristas del ciclo, y viceversa: las aristas en un corte sólo pueden aparecer en aquellos ciclos no contenidos en la arista correspondiente al corte.Para un grafo genérico G, el número t(G) puede obtenerse a través del teorema de matriz-árbol de Kirchhoff.Estas fórmulas son también corolarios del teorema matriz-árbol.donde G-e es el multigrafo que se obtiene al eliminar la arista e, y G/e es la contracción de G sobre e, en la que las múltiples aristas de esta contracción no son eliminadas.Un árbol de expansión escogido aleatoriamente, con igual probabilidad, entre todos los árboles de expansión se denomina árbol de expansión uniforme .Este modelo ha sido ampliamente investigado en los ámbitos de la Probabilidad y la Física matemática.El algoritmo clásico de búsquedas no informadas para los árboles de expansión, Depth-First Search (DFS, Búsqueda priorizando la profundidad en español), fue diseñado por Robert Tarjan.Otro algoritmo relevante está basado en la búsqueda priorizando la anchura (Breadth-First Search, BFS).