1 Algunas definiciones.

1.1 Grafo

Un grafo \(G=(V,E)\) viene dado por dos conjuntos finitos:
- Conjunto de vértices \(V\).
- Conjunto de aristas \(E\).
  .
Cada arista \(E\) asocia un par de vértices de \(V\).
Decimos que un grafo \(G\) es no orientado cuando cada arista \(e \in E\) es un par no ordenado, esto es \(e=(a,b)=(b,a)\). Es decir no tienen dirección.
Los grafos reciben esos nombres porque permiten representaciones gráficas de las relaciones entre los vértices.
En la representación gráfica de un grafo no orientado , los vértices son representados por círculos, y cada arista por una linea que conecta el par de vértices correspondiente.
Ejemplo:

\[ V= \{a,b,c,d,e\} \\ E= \{(a,b), (a,c), (b,c), (b,d), (c,d), (c,e), (d,e) \}\]

Dada una arista \(e=(a,b)\), decimos que los vertices \(a\) y \(b\) son extremos de la arista y que \(a\) y \(b\) son vertices adyacentes.
Decimos también que una arista \(e\) es incidente hacia los vértices \(a\) y \(b\) , y que los vértices \(a\) y \(b\) son incidente a la arista \(e\).

Un lazo es una arista con ambos extremos en un mismo vértice.
Dos o mas aristas son paralelas o multiples cuando tienen el mismo par de vértices como extremos.
Decimos que un grafo es simple cuando no posee ni aristas paralelas.

Denotamos por \(|V|\) y \(|E|\) la cardinalidad de los conjuntos de vértices y aristas de un grafo \(G\) respectivamente.
En el ejemplo de abajo tenemos \(|V|=5\) y \(|E|=7\).

El grado de un vertice \(v\), denotado por \(d(v)\) es el numero de aristas incidentes a \(v\), con lazos contados dos veces.
Ejemplo:
- \(d(a)=2\)
- \(d(b)=3\)
- \(d(c)=6\)
- \(d(d)=5\)
- \(d(e)=4\)

\[ \sum_{v \in V} d(v)= 2|E| \]

El grado mínimo de \(G\), denotado \(\delta(G)\), es el grado del vértice de menor grado de \(G\).
Analogicamente, el grado máximo de \(G\), denotado \(\Delta(G)\), es el grado del vértice de mayor grado de \(G\).
- \(d(a)=2\)
- \(d(b)=3\)
- \(d(c)=6\)
- \(d(d)=5\)
- \(d(e)=4\)

Un paseo \(P\) de \(v_0\) a \(v_n\) en el grafo \(G\) es una secuencia finita y no vacia \((v_0, e_1, v_1, ..., e_n,v_n)\), cuyos elementos son alternadamente vértices y aristas, tal que para todo \(1 \leq i \leq n, v_{i-1} \; y \; v_i\) son extremos de \(e_i\).
La longintud de un paseo \(P\) viene dado por su número de aristas, es decir, \(n\).

Un sendero es un paseo en el que no hay repetición de las aristas en la secuencia, mas puede haber repeticiones de vértices.
Un camino o camino simple es un paseo en el que no hay repetición de vértices ni de aristas en la secuencia.
Un ciclo es un camino en el que \(: v_0 = v_n\).
La longitud de un ciclo \(C\) está dado por su numero de aristas (y de vértices), es decir \(n\).

Decimos que un grafo es conexo si, para cualquier par de vertices \(u\) y \(v\) de \(G\), existe un camino de \(u\) a \(v\) en \(G\).
Caso contrario, un grafo es no conexo o desconexo.
Dos vèrtices \(u\) y \(v\) de \(G\) están en el mismo componente conexo de \(G\) si ha terminado de \(u\) a \(v\) en \(G\).
Un grafo conexo tiene un unico componente conexo, mietras que un grafo no conexo tiene al menos dos componenetes conexos.
ejemplo.

Todo árbol con menos de dos vertices tiene al menos una hoja.
Teorema: Un grafo \(G\) es un árbol si y solo si:
- Es conexo con \(|V|-1\) aristas.
- Es conexo y al eliminar cualquier arista se desconecta del grafo.
- Para todo par de vertices \(u,v\) de \(G\), existe exactamente un camino de \(u\) a \(v\) en \(G\).

Un subgrafo \(H=(V',E')\) de un grafo \(H=(V,E)\) es un grafo tal que \(V' \subseteq V, E' \subseteq E\).
Un subgrafo generador \(H=(V',E')\) de \(G\) es un subgrafo \(H\) con \(V'=V\).
ejemplo.

Todo grafo conexo tiene al menos um subgrafo generador que es un arbol generador.

Un grafo orientado o grafo direccionado es definido de forma semejante a un grafo no orientado, con la diferencia de que cada arista \(e \in E\) es dada por un par ordenado, esto es, \(e=(a,b) \neq (b,a)\).
En la representación gráfica, usamos flechas para indicar el orden de los vértices en el par ordenado.
Ejemplo

En un grafo orientado, grado de salida de un vértice \(v\), denotado por \(d^+(v)\) es el numero de aristas orientadas saliendo del vértice \(v\).
Analogicamente, grado de entrada de unvértice, denotado por \(d^-(v)\) es el numero de aristas orientadas entrado en el vértice \(v\).
Ejemplo:
- \(d^+(a)=0\) \(\quad\) \(d^-(a)=2\)
- \(d^+(b)=2\) \(\quad\) \(d^-(b)=1\)
- \(d^+(c)=1\) \(\quad\) \(d^-(c)=3\)
- \(d^+(d)=2\) \(\quad\) \(d^-(d)=1\)
- \(d^+(e)=2\) \(\quad\) \(d^-(e)=0\)
  .

Dado un grafo direccionado \(G\), el grado minimo de salida o el grado minimo de entrada, denotado por \(\delta^+(G\) y \(\delta^-(G)\), son los grados de salida y de entrada de los vertices de menor grado de salida y de entrada de \(G\).
Analógicamente, el grado máximo de salida o el grado máximo de entrada, denotados \(\Delta^+(G)\) y \(\Delta^-(G)\), son los grados de salida y de entrada de los vertices de mayor grado de salida y de entrada de \(G\), respectivamente.
Ejemplo
- \(\delta^+(G)=0\) \(\quad\) \(\delta^-(G)=0\)
- \(\Delta^+(G)=2\) \(\quad\) \(\Delta^-(G)=3\)
  .

Un árbol orientado \(G\) es un grafo orientado en el que \(d^-(v)\leq 1, \forall \; v \in V\), ya que hay un unico vértice \(r\) con \(d^-(r)=0\).
El vertice especial \(r\) con \(d^-(r)=0\) es llamado raiz de \(G\).
Todo vértice \(v\) con \(d^+(r)=0\) es una hoja de \(G\).
Ejemplo.

Para cada arista \((u,v)\) de un arbol orientado \(G\), decimos que \(u\) es un padre de \(v\) y que \(v\) es un hijo de \(u\).
Si eliminamos la raíz r, obtendremos sub-árboles de \(G\). Cada hijo \(v\) de \(r\) es raiz de uno de esos sub-árbol
Un árbol binario \(G\) es un árbol orientado enel que \(d^+(v)\leq 2 \; \forall \; v \in V\), esto es, cada vertice tiene como maximo dos hijos.
Ejemplo.

La altura de un árbol binario \(G\), denotado por\(h(G)\), es definida inductivamente de la siguiente forma:
- Si \(G\) no tiene raiz, entonces \(h(G)=0\).
- Si tiene raiz \(r\), y \(G_e\), \(G_d\) son sub-arboles raíz, entonces \(h(G)= max(h(G_e),h(G_d))+1\)
Ejemplo.

Un árbol binario lleno \(G\) es un árbol binário en el que casa vértice tiene cero o dos hijos.
ejemplo.

Unárbol binario completo \(G\) es el que los sub-arboles ligados a un mismo vértice con la misma altura.
ejemplo.