Algoritmos

Algoritmo de fuerza bruta
 Solución por fuerza bruta o búsqueda exhaustiva, se utiliza para denominar algoritmos que exploran todas las posibles combinaciones para alcanzar la solución óptima consiste en verificar, en todas las posiciones en el texto entre 0 y n - m, ya sea una ocurrencia del patrón comienza allí o no. Luego, después de cada intento, se desplaza el patrón por exactamente unaposición a la derecha. La complejidad de tiempo de esta fase de búsqueda es O (m n) 

Algoritmo ambicioso
Algoritmo ambicioso (“greedy”) son algoritmos simplistas que toman decisiones en base a la información disponible de forma inmediata y que es pre-definida. Esto permite que sean eficientes, fáciles de desarrollar e implantar, pero su simplicidad no se adapta a muchas situaciones de la vidareal y, por tanto, típicamente su solución no es óptima. Su uso principal son los problemas de optimización tales como la ruta más corta o el costo más bajo. 

Algoritmo aproximado
Un algoritmo de aproximación es un algoritmo que entrega una solución con una garantía teórica de cercanía al óptimo. Más aun, es frecuente que estos algoritmos posean un desempeño práctico muy superior a su garantíateórica.
ALGORITMO AMBICIOSO REPETITIVO
Consisten en repetir varias veces el proceso para encontrar un circuito de Hamilton del algoritmo ambicioso.
Escoge cualquier vértice X. Aplica el algoritmo ambicioso usando X como vértice inicial y calcula el costo total del circuito obtenido.
Repite el proceso usando cada uno de los vértices restantes de la gráfica como vértice inicial.
De loscircuitos de Hamilton obtenidos, escoge el mejor inicial.

ALGORITMO DE MÍNIMA CONEXIÓN
Empieza eligiendo la arista de menor peso, sin que importe dónde se encuentre. Después de a ver hecho esto, elegimos la siguiente arista de menor peso, dondequiera que se encuentre. Continua haciendo esto, cada vez eligiendo la arista de menor peso de entre las que están disponibles, y observando rigurosamente lassiguientes dos prohibiciones:
1. No permitas que se formen circuitos excepto al final
2. No permitas que se unan tres aristas en un vértice

SUBGRÁFICA.
Significa que todos los vértices y aristas están contenidos en la gráfica original, y la observación de que debe incluir todos los vértices se formalizara diciendo que la subgráfica es generadora
SUBGRÁFICA GENERADORA
Incluye a todos losvértices de una gráfica
ÁRBOL
Árbol es un grafo en el que existe un único nodo desde el que se puede acceder a todos los demás y cada nodo tiene un único predecesor, excepto el primero, que no tiene ninguno. También podemos definir un árbol como: Un grafo conexo y sin ciclos. Un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices. Grado de un nodo en un árbol es el número desubárboles de aquel nodo. 
CARACTERÍSTICAS DE LOS ÁRBOLES
Sea G(V,E) un grafo. Son equivalentes
a) G es un árbol
b) Cada par de vértices distintos de V esta conectado por un único camino.
c) G es conexo y toda arista de G es de separación
d) G no tiene ciclos y |V| = |E| + 1
e) G es conexo y |V| = |E| + 1
f) G no tiene ciclos pero al añadirle una arista a G se crea un único circuito
Todo árboles a su vez un grafo bipartito. Todo árbol con sólo un conjunto numerable de vértices es además un grafo plano.
Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G.
Dado n vértices etiquetados, hay n n−2 maneras diferentes de conectarlos para construir un grafo. El resultado se llama fórmula de Cayley. El número deárboles con n vértices de grado d1,d2,...,dn es:
Que es un coeficiente multinomial.
Contar el número de árboles no etiquetados es un problema complicado. De hecho, no se conoce ninguna fórmula para el número de árboles t(n) con n vértices (debe entederse aquí el número de árboles diferentes salvo isomorfismo de grafos). Los primeros valores de t(n) son 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235,...