sábado, 24 de marzo de 2012

Árboles

Un árbol es un grafo conexo sin ciclos.
Árboles con raíz : un árbol con raíz "r"  (a "r" llamaremos raíz del árbol). Existe una única trayectoria de r a cualquier otro vértice "v", esto da una dirección a los arcos de r. La longitud de la trayectoria que va de r a v se   llama nivel o profundidades de "v"(vértice). Aquellos vértices con grado uno distintos de "r", se llaman hojas del árbol con raíz. Una trayectoria  dirigida de un vértice a una hoja se llama rama.
ejemplo:
la figura de arriba es un árbol con raíz "r". Este árbol tiene 5 hojas: d,f,h,i y j. El nivel de "a" es 1, el nivel de "f" es 2 y el nivel de "j" es 3. Cualquier árbol puede convertirse en un árbol con raíz eligiendo simplemente uno de sus vértices como raíz.

¿para que sirve un árbol con raíz?.
Un árbol con raíz es una ayuda útil para enumerar todas las posibilidades lógicas de una sucesión de sucesos  donde cada suceso  puede ocurrir de un numero finito de maneras.


Instituto Tecnologico de Apizaco.
Autor: Elizabeth Sola Lira.




lunes, 19 de marzo de 2012

Grafos planos, formula de Euler y Teorema de Kuratowski.

Un grafo o multigrafo que se puede dibujar en el plano sin que se crucen sus arcos se llama plano. Aunque el grafo completo de K4 se suele dibujar con arcos que se cruzan como en la figura 6.1(a), también se puede dibujar sin que se crucen sus arcos como en la figura 6.1(b). Luego K4 es un grafo plano.
Formula de Euler: Euler dio una formula que relacionaba el numero de V de vértices, el numero E de arcos y el numero R de regiones de un mapa conexo. V-E+R=2. Es muy importante que el grafo correspondiente al mapa sea conexo, pues en caso contrario la formula no es cierta. En la siguiente figura tenemos  V=6, E=9 y R=5 y como afirma la formula de euler: V-E+R=6-9+5=2.


Teorema de Kuratowski:Un grafo es no plano si y solo si contiene un subgrafo homeomorfo a K3,3 o K5.

 

Intituto Tecnologico de Apizaco.
Autor: Elizabeth Sola Lira