Árboles.

Grafo conexo que no contienen ningún ciclo, existiendo siempre entre dos vértices una cadena. Igualmente se denomina así a un procedimiento  frecuentemente utilizado para tratar problemas de enumeración y probabilidad.

Elementos de un árbol.

Raíz: Vértice del que salen uno o más arcos pero no entran.

Brote: Vértice en el que termina uno o más arcos, pero del que no sale ninguno.

Nodo raíz: Es cuando salen más arcos de los que entran.

Nodo brote: Es cuando entran más arcos de los que salen.

Nodo eslabón: Nodo del que salen y entran igual cantidad de arcos.

Nodo eslabón simple: Es el que entra en un arco y sale en otro.

Propiedades de los árboles.

a) El grafo es conexo.

b) El grafo no tiene ciclos.

c) Si 'v' es el número de vértices; V-1 será el número de aristas.

d) Si suprimimos una arista cualquiera, el grafo deja de ser conexo.

e) Si se agrega una arista entre los dos vértices no adyacentes se forma un ciclo.

f) Para cada par de vértices hay una sóla cadena que los conecte.

En cumplimiento  de dos cuales quiera de estas propiedades define a un árbol. 

Isomorfismo.

Las siguientes instrucciones se dan a dos personas que no pueden ver el papel de la otra: Dibuje y etiquete 5 vertices con las siguientes letras: a, b, c, d, e. Conecte a con b, b con c, c con d, d con e y e con a.

Las gráficas producidas se aprecian en las siguientes figuras, sin duda estas figuras definen la misma gráfica aún cuando parezcan diferentes, se dice que estas gráficas son isomorfas.

La gráfica G1 yG2 son isomorfas si existe una función d 1 a 1 y sobre de los vértices de G1 a los vértices de G2, de manera que una arista E es insidente en v y w en G1 si sólo si la arista G (E) es insidente en f(v) y f(w) en G2. El par de funciones de f y g reciben el nombre de isomorfismo de G1 y G2.

Tres ciudades C1, C2 y C3 deberan conectars en forma directa mediante autopistas como cada una de las otras 3 ciudades C4, C5 y C6. Puede diseñarse este sistema de carreteras de manera que la autopista no se crucen. La siguiente figura ilustra un sistema en el que las autopistas se cruzan.

Una gráfica es plana si se puede dibujar en el plan sin que sus aristas se crucen.

Al diseñar circuitos impresos es deseable tener el menor número de cruces posibles, así el diseñador de circuitos impresos se enfrenta con el problema de gráficas planas.

Si una gráfica plana conexa se dibuja en el plano, este se divide en regiones contiguas llamadas caras. Una cara se caracteriza por el ciclo que forma su frontera. Por ejemplo, en la siguiente gráfica, la cara a tiene como un límite el ciclo (5, 2, 3, 4, 6, 1) y en el límite de la cara c es el ciclo (1, 2, 5,1). La cara exterior d se considera limida  por el ciclo (1, 2, 3, 4, 6, 1) La gráfica de la figura tiene f= 4 caras, e= 8 aristas. v= 6 vertices.

Obserbe que f, e y v satisfacen la ecuación f =  e - v + 2.

En 1752 Euler provó que la ecuación se cumple para cualquier gráfica con hexapiana.

Problemas de los puentes de Königsberg

El primer artículo referente a la teoría de gráficas fue de Leonard Euler en 1736. El artículo presentaba una teoría general que incluía una solución a lo que ahora se llama el proble de los puentes de Königsberg.

Dos islas en el río Pregel en Königsberg estaban conectados entre sí y con las orillas de ríos por puentes, como se aprecia en la siguiente figura. El problema es comenzar en cualquier lugar de A, B, C ó D; cruzar cada puente exactamente una vez; luego regresar al lugar de inició.

La configuración de los puentes se puede modelar como una gráfica, como se ve en la siguiente figura: Los vértices representan los lugares y las aristas representan los puentes. El problema de los puentes de Königsberg ahora se reduce a encontrar un ciclo en la figura que incluya todas las aristas y todos los vértices. En honor a Euler, un ciclo es una gráfica que incluye todas las aristas y vértices de g se llama ciclo de Euler.

A partir del análisis en la sección se ve que no hay un circuito de Euler en la gráfica de la figura porque hay un número impar de aristas, incidentes en cada vértice.