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, los grados siguientes:

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

Como podremos notar el grado de D no es 2, sino 4, ya que el lazo se cuenta 2 veces para el grado de su nodo. Y la suma de los grados del nodo es 12, y una vez más se comprueba el Teorema 1, donde el grado total corresponde al doble de sus segmentos.

Aristas

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.

Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.

Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.

Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.

Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.

Cruce: Son dos aristas que cruzan en un punto.

Vértices

Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

Vértice Aislado: Es un vértice de grado cero.

Vértice Terminal: Es un vértice de grado 1.

Caminos

Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn, y}. En este caso x e y se llaman los extremos del camino.

El número de aristas del camino se llama la longitud del camino. Si los vértices no se repiten el camino se dice propio o simple. Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos. Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.

Llamaremos ciclo a un circuito simple

Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo

TITULO 3. TIPOS DE GRAFOS

Grafos simples:

Se dice que es grafo simple cuando no hay más de una arista entre un par de nodos (no más de una arista dirigida en el caso de gráficas dirigidas).

Ejemplos:

...