Teoria De Árboles y Gráfos

Grafo
Un grafo es una pareja de conjuntos G = (V, A), donde V es el conjunto de vértices, y A es el conjunto de aristas.

En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.
Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad.

Sub grafo
Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H (dependiendo de las necesidades de la situación).
El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de vértices de G.
Definición:
Sea G= (V, A). G’= (V’, A’) se dice subgrafo de G si:
1- V’ V
2- A' A
3- (V’, A’) es un grafo
• Si G’=(V’,A’) es subgrafo de G, para todo v G se cumple gr (G’,v)≤ gr (G, v)

Caracterización de grafos
Grafos simples
Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.
Un grafo que no es simple se denomina Multigráfica o Grafo múltiple.
Grafos conexos
Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.
Un grafo es fuertemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.
Grafos completos
Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.
El conjunto de los grafos completos es denominado usualmente , siendo el grafo completo de n vértices.
Homeomorfismo de grafos
Dos grafos G1 y G2 son homeomorfismo si ambos pueden obtenerse a partir del mismo grafo con una sucesión de subdivisiones elementales de aristas.

Grafos planos
Cuando un grafo o multigrafo se puede dibujar en un plano sin que dos segmentos se corten, se dice que es plano.

ARBOL
Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas, y hay nn-2 árboles posibles. Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas. Un importante campo de aplicación de su estudio se encuentra en el análisis filogenético, el de la filiación de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguación del parentesco entre especies; aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas.

En teoría de grafos, un árbol es un grafo en el que dos vértices están conectados por exactamente un camino. Un bosque es un grafo en el que dos vértices cualquiera están conectados por como máximo un camino.
Una definición equivalente es que un bosque es una unión disjunta de árboles (de aquí el nombre). Un árbol a veces recibe el nombre de árbol libre.
Un árbol es un grafo simple unidireccional G que satisface alguna de las siguientes condiciones equivalentes:
• G es conexo y no tiene ciclos simples.
• G no tiene ciclos simples y, si se añade alguna arista se forma un ciclo simple.
• G es conexo y si se le quita alguna arista deja de ser conexo.
• G es conexo y el grafo completo de 3 vértices K3 no es un menor de G.
• Dos vértices cualesquiera de G están conectados por un único camino simple.