Arboles Y Grafos

Contenido

INTRODUCCION 3

¿QUÉ ES UN GRAFO? 4

VALENCIA 6

TIPOS DE GRAFOS 9

CAMINOS. 11

TIPOS DE CAMINOS. 12

¿QUÉ ES UN ÁRBOL? 14

CARACTERÍSTICAS Y PROPIEDADES DE LOS ÁRBOLES. 16

APLICACIÓN DE GRAFOS Y ÁRBOLES. 17

EJEMPLOS DE APLICACIONES DE GRÁFICAS. 18

CONCLUSIÓN. 20

REFERENCIA BIBLIOGRÁFICA. 21

Enlaces en la red 21

Libros de consulta 21

INTRODUCCIÓN

En esta investigación nos enfocaremos sobre lo que es arboles y grafos, en el cual daremos una explicación de cada uno como están conformados sus propiedades y de alguna manera explicaremos como los podemos aplicar a la computación que es el área que nos compete.

Este ensayo nos dará a conocer que tanto como los grafos y los arboles tienen muchas similitudes en cuanto a su estructura por que poseen nodos, raíces, un hijo izquierdo y un hijo derecho desglosaremos un poco esto mas adelante.

Sabremos que es un bosque con el objetivo de poder identificar las relaciones y diferencias que hay entre grafos, arboles y bosques.

Los arboles y los grafos se aplican en la computación porque gracias a ellos podemos almacenar datos. El trabajo hablara acerca de las estructuras no lineales en específico de los Árboles y Grafos, que se diferencia de las estructuras lineales en la forma de manejo de los datos, las estructuras lineales como su nombre lo indica se lo caracteriza por la linealidad tal así como los arrays que cada elemento iba ordenado secuencialmente uno tras otra en índices continuas en la cual a cada correspondía a otro siguiente.

Estaremos también mencionando los tipos de árboles empleados en la informática y las operaciones que se pueden realizar sobre las mismas y los recorridos que pueden llegar a tener tal así como el recorrido en grafos.

TEMA 1. ¿QUÉ ES UN GRAFO?

Desafortunadamente no existe una terminología estandarizada en la teoría de los grafos, por lo tanto es oportuno aclarar que las presentes definiciones pueden variar ligeramente entre diferentes publicaciones de estructura de datos y de teoría de grafos, pero en general se puede decir que un grafo como indica su nombre lo indica es la representación (para nuestro caso) gráfica de los datos de una situación particular, ejemplo:

Los datos contienen, en algunos casos, relaciones entre ellos que no son necesariamente jerárquicos. Por ejemplo, supongamos que unas líneas aéreas realizan vuelos entre las ciudades conectadas por líneas como se ve en la figura anterior (más adelante se presentaran grafos con estructuras de datos); la estructura de datos que refleja esta relación recibe el nombre de grafo.

Se suelen usar muchos nombres al referirnos a los elementos de una estructura de datos. Algunos de ellos son "elemento", "ítem", "asociación de ítems", "registro", "nodo" y "objeto". El nombre que se utiliza depende del tipo de estructura, el contexto en que usamos esa estructura y quien la utiliza.

En la mayoría de los textos de estructura de datos se utiliza el término "registro" al hacer referencia a archivos y "nodo" cuando se usan listas enlazadas, árboles y grafos.

También un grafo es una terna G = (V,A,j ), en donde V y A son conjuntos finitos, y j es una aplicación que hace corresponder a cada elemento de A un par de elementos de V. Los elementos de V y de A se llaman, respectivamente, "vértices" y "aristas" de G, y j asocia entonces a cada arista con sus dos vértices.

El “gráfico” tiene varios sentidos en matemáticas. Hemos usado el término “gráfica” en el sentido de una relación o de una función. En muchas partes de la ciencia de las computadoras y de la informática aparecen los grafos, especialmente los grafos de árbol, y los grafos dirigidos. Los diagramas de flujo, por ejemplo, son grafos dirigidos.

GRAFOS Y MULTIGRADOS (Lazos y Nodos).

Un grafo consta de dos cosas:

Un conjunto N cuyos elementos se llaman nodos, puntos o vértices. Un conjunto S de parejas no ordenadas de nodos diferentes, llamadas segmentos, aristas o arcos.

Denotaremos un grafo por G =(N, S) cuando queremos destacar las dos partes de G.

Los nodos u y v se llaman adyacentes si hay un segmento {u, v}

Representaremos de una manera natural los grafos por diagramas en el plano. O sea, cada nodo v de

N se representa por un punto (o pequeño círculo) y cada segmento s = {v1, v2} se representa por una curva que conecta sus terminales v1 y v2.

EJEMPLO.

La figura 1.1 representa el G con cuatro vértices, A, B, C y D, y cinco segmentos s1 = {A, B},

s2 = {B, C}, s3 = {C, D}, s4 = {A, C}, s5 = {B, D}. Usualmente denotamos un grafo dibujando su diagrama en lugar de hacer una lista explicita de sus nodos y segmentos.

La figura 1.2 no es un grafo sino un multigrafo. La razón es que s4 y s5 son segmentos múltiples, o sea segmentos que conectan las mismas terminales, y s6 es un lazo, o sea, un segmento cuyas terminales son el mismo nodo. La definición de grafo no permite ni segmentos múltiples o multisegmentos, ni lazos. En otras palabras, podemos definir un grafo como un multigrafo sin multisegmentos ni lazos.

TITULO 2. VALENCIA

Es el número de aristas que salen o entran a un nodo.

GRADO DE UN NODO

Si v es una terminal de un segmento s, decimos que s es incidente en v. El grado de v, escrito gr (v), es igual al número de segmentos que inciden en v. (Un nodo de grado cero, o sea un nodo que no pertenece a ningún segmento, se llama nodo aislado)

Teorema 1.- La suma de los grados de los nodos de un grafo es igual al doble del número de segmentos.

EJEMPLO

Observemos que en la figura 1.1 se tienen por cada vértice, los grados siguientes:

gr(A) = 2, gr(B) = 3, gr(C) = 3, gr(D) = 2

La suma de los grados es 10, que, como dice el Teorema 1, es el doble de segmentos. Se dice que un nodo es par o impar según que su grado sea par o impar. Así A y D son nodos pares, mientras que B y C son nodos impares.

Ahora veamos que en la figura 1.2 se tienen por cada vértice,

...