Trabajo de Investigación de Grafos y Arboles

Integrantes:

González Moreno Armando

López Pulido Ángel

Pech Tovar Luis Gilberto

Concepto de Grafos

Conjunto de objetos llamados vértices o

nodos, unidos por enlaces llamados

aristas o arcos, que permiten representar

relaciones binarias entre elementos de

un conjunto.

Tipos de Grafos

Grafos Simples

Un grafo es simple si a lo mas existe una arista uniendo dos vértices cualesquiera.

Grafo Completo

Es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todos los vértices (a,b) deben tener una arista (e) que los une. El conjunto de los grafos completos es denominado usualmente K, siendo Kn el grafo completo de n vértices. Un Kn tiene exactamente n(n - 1)/2 aristas.

Grafos Orientados o Dirigidos

Los grafos que contienen aristas dirigidas se denominan grafos orientados, en este caso a las aristas se les llaman arcos y se representan como pares para indicar el orden.

V = {A, B, C, D, E}

A = {(E, A), (E, B), (D, C)}

Grafos Bidireccionales

Se les considera a las aristas no orientadas; para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido). Se considera la característica de “grado” positivo o negativo de un vértice, como la cantidad de aristas que llegan y salen de el; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas que tocan ese vértice.

V = {1, 2, 3 ,4 ,5 ,6}

A = {(1, 2), (1, 5), (2, 1), (2, 3), (2, 5), (3, 2), (3, 4), (4, 3), (4, 5), (4, 6), (5, 4), (5, 1), (5, 2), (6, 4)}

Grafos Planos

Se dice que un grafo es plano si puede dibujarse en un plano de tal forma que ningún par de sus aristas se corte. A esto se le llama representación plana del grafo.

Grafos Ponderados o Valorados

Son los grafos a los que se asigna un número a cada una de sus aristas. Este número representa un peso para el recorrido a través de la arista. Este peso podría indicar, por ejemplo: el costo monetario, la distancia recorrida o el tiempo invertido entre otros.

Definimos la longitud del camino de un grafo ponderado como la suma de los pesos de las aristas de ese camino.

Multígrafos

Cuando se permite que haya mas de una arista en los vértices.

Grafos Isomorfos

Es cuando dos grafos tienen la misma forma matemática; lo cual será cuando la única diferencia entre ambos, en cuanto a su estructura, sea la representación grafica de sus vértices y aristas.

Grafos Bipartitos

Un grafo G es bipartido si puede expresarse como:

G = {V1 U V2, A} (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:

1. V1 y V2 son disjuntos (no tienen ningún elemento en común) y no vacíos.

2. Cada arista de A une un vértice de V1 con uno de V2.

3. No existen aristas uniendo dos elementos de V1; analógicamente para V2.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles (rompecabezas), en los que debe unirse un elemento de la columna A con un elemento de la columna B.

Sub Grafos

Un grafo G2 es sub grafo de otro G si todos los vértices de G2 están en G pero no necesariamente todos los vértices de G están en G1.

G2 es un sub grafo de G.

Caminos

Un camino en un grafo es la sucesión finita en la que aparecen alternadamente vértices y aristas de dicho grafo.

Si en un grafo existe un camino que conecta dos vértices distintos, existe un camino simple con extremos en dichos vértices.

Tipos de Caminos

a) Camino euleriano

Es un camino o circuito que contiene todas las aristas apareciendo cada una de ellas exactamente una vez. Un grafo que admite dicho circuito se denomina grafo euleriano, y sus vértices o tienen grado par o dos de los vértices tienen grado impar.

b) Camino hamiltoniano

Es un camino que contiene todos los vértices apareciendo cada uno de ellos exactamente una vez. Un ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano.

Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega).

Conexión

Un grafo no dirigido es llamado conexo si hay un camino entre cada par de vértices distintos del grafo.

Un grafo dirigido es fuertemente conexo si hay un camino de a a b y de b a a para cualesquiera dos vértices a y b del grafo.

Grafo Conexo

Un grafo es conexo si cada par de vértices están conectados. En caso contrario se este es un grafo des conexo.

Grafos Conexos Grafo Des conexos

Representación Matricial

Matriz de Incidencia

El grafo esta representado por una matriz de A (aristas), por V (vértices), donde [arista, vértice] contiene la información de la arista (1 – conectado, 0 – no conectado).

Matriz de Adyacencia o Matriz de Vecindades

El grafo está representado por una matriz cuadrada M de tamaño donde n es el numero de vértices. Si hay una arista entre un vértice x y un vértice y entonces el elemento es 1, de lo contrario, es 0.

Concepto de Árbol

Un árbol es un grafo no dirigido, conexo y

sin circuitos simplex.

Sea G = (V, E) un grafo simple, G es un

árbol si y solamente si para cada par de

vértices excite un único camino simple

uniendo u con v.

Propiedades

Dentro de las propiedades podemos mencionar

que un árbol es una gráfica acíclica conexa.

Además en particular un árbol no tiene lazos ni

aristas paralelas.

Si a un árbol se le quitan algunas aristas, pero

manteniendo los vértices, a este árbol se le

llama árbol generador.

Tipos de Árboles

Árboles con Raíz o Enraizados

Un árbol enraizado es cuando exactamente un vértice cuyo grado de entrada sea 0 y los grados entrada de todos los otros vértices sean 1

a) Todo árbol que no es vacío, tiene un único nodo raíz.

b) Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. en este caso es común utilizar la expresión X es hijo de Y.

c) Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. En ese caso es común utilizar la expresión X es padre de Y.

d) Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.

e) Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.

f) Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.

g) Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol, es decir, el grado más alto entre todos los nodos.

h) Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.

i) Altura del árbol es el máximo número de niveles de todos los nodos del árbol.

Características: Árboles Enraizados

Árbol Binario

Es un tipo de árbol ordenado.

Un árbol binario es un árbol enraizado en el cual cada vértice tiene un hijo a la derecha, o un hijo a la izquierda, o un hijo a la derecha y un hijo a la izquierda, o bien ningún hijo.

Un árbol binario completo es un árbol binario en el que cada vértice tiene un hijo a la derecha y otro a la izquierda o bien ningún hijo.

Búsqueda de Primera Profundidad

Un árbol será de búsqueda si todos sus nodos cumplen las siguientes condiciones:

• Todos los nodos situados a su izquierda son menores que él.

• Todos los nodos situados a su derecha son mayores que él.

El recorrido por profundidad sigue primero una trayectoria desde el nodo inicial hasta un nodo terminal, después otra trayectoria desde el mismo punto inicial hasta alcanzar otro final; y así sucesivamente hasta que todos los nodos hayan sido visitados.

Notación Polaca

Puede ser utilizada para describir expresiones que involucren objetos de algunos sistemas y algunas operaciones en los objetos. Las operaciones son normalmente, aunque no siempre, operaciones binarias.

Representación Gráfica1. A es la raíz del árbol.

2. B es hijo de A.

C es hijo de A.

D es hijo de B

E es hijo de B.

L es hijo de H.

3. A es padre de B.

B es padre de D.

D es padre de I.

C es padre de G.

H es padre de L.

4. B y C son hermanos.

D, E y F son hermanos.

G y H son hermanos.

J y K son hermanos.

5. I, E, J, K, G Y L son nodos

de terminales u hojas.

6. B, D, F, C y H son nodos

interiores.

7. El grado del nodo A es 2.

El grado del nodo B es 3.

El grado del nodo C es 2.

El grado del nodo D es 1.

El grado del nodo E es 0.

El grado del árbol es 3

8. El nivel del nodo A es 1.

El nivel del nodo B es 2.

El nivel del nodo D es 3.

El nivel del nodo C es 2.

El novel del nodo L es 4.

9. La altura del árbol es 4.

Árboles Enraizados

Representación Gráfica

Árbol Binario de Búsqueda

Este otro ejemplo, Viola la condición de orden en el nodo 2, ya que a su derecha, 1, no es mayor que el.

Representación Gráfica

Árboles Notación Polaca

En esta expresión se supone que no es posible realizar operaciones como –, +, x, o / hasta evaluar ambos argumentos; Es decir hasta realizar todos los cálculos dentro de los argumentos de la izquierda y de la derecha.

Por lo tanto, no es posible realizar la suma central hasta haber evaluado (3 – (2 • x)) y ((x – 2) – (3 + x)).

No es posible realizar la resta central en ((x-2) – (3+x)).

Hasta haber evaluado ((x – 2) y (3 + x)).

Y así sucesivamente.