Mate Discretas Unidad 6: TEORIA DE GRAFOS

ELEMENTOS Y CARACTERÍSTICAS DE UN GRAFO

Llamaremos grafo, G, al par ordenado formado por un conjunto finito no vacío, V, y un conjunto, A, de pares no ordenados de elementos del mismo.

V es el conjunto de los vértices o nodos del grafo.

A sera el conjunto de las aristas o arcos del grafo.

Utilizaremos la notación G = (V,A) para designar al grafo cuyos conjuntos de vértices y aristas son, Respectivamente, V y A.

El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos podrían ser los siguientes: un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama),grafos matemáticos que representan las relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad.(Véase la figura 1).En cada caso, es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos(vértices)con líneas conectándolos (arcos).

De aquí se podría deducir que un grafo es básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio, es decir, un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices. Por otro lado, y debido a su generalidad y a la gran diversidad de formas que pueden usarse, resulta complejo tratar con todas las ideas relacionadas con un grafo.

Para facilitar el estudio de este tipo de dato, a continuación se realizará un estudio de la teoría de grafos desde el punto de vista de las ciencias de la computación. Considerando que dicha teoría es compleja y amplia, aquí sólo se realizará una introducción a la misma, describiéndose el grafo como un tipo de dato y mostrándose los problemas típicos y los algoritmos que permiten solucionarlos usando un ordenador.

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos grandes bloques:

Grafos Dirigidos.
Grafos no Dirigidos(pueden ser considerados un caso particular de los anteriores).

Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido. Por el contrario, la red de carreteras de un país representa en general un grafo no dirigido, puesto que una misma carretera puede ser recorrida en ambos sentidos. No obstante, podemos dar unas definiciones generales para ambos tipos.

A continuación daremos definiciones de los dos tipos de grafos y de los conceptos que llevan asociados.

DEFINICIONES Y TERMINOLOGÍA FUNDAMENTAL.

Un grafo G es un conjunto en el que hay definida una relación binaria, es decir G=(V,A) tal que V es un conjunto de objetos a los que denominaremos vértices o nodos y es una relación binaria a cuyos elementos denominaremos arcos o aristas.

Dados ,puede ocurrir que:

1. , en cuyo caso diremos que x e y están unidos mediante un arco, y

2. , en cuyo caso diremos que no lo están.

Si las aristas tienen asociada una dirección (las aristas (x, y) y (y, x) no son equivalentes) diremos que el grafo es dirigido, en otro caso ((x, y)=(y, x)) diremos que el grafo es no dirigido.

Definición 1 Un grafo simple G (V,E) consta de V , un conjunto no vacío de vértices, y de E, un conjunto de pares no ordenados de elementos Distintos de V . A esos pares se les llama aristas o lados.

Ejercicio 1 Muestre que si G es simple, entonces " ≤

En algunos casos lo grafos simples no bastan para modelar ciertas situaciones en las cuales se requiere de la existencia de múltiples aristas entre par de Vértices. En este caso no es suficiente definir las aristas como par de vértices;

La definición de multígrafo es un poco más complicada.

Definición 2 Un multígrafo G (V,E) consta de un conjunto V de vértices, un conjunto E de aristas y una función f de E en {{u, v}|u, v ∈ V, u 6= v}. Se dice que las aristas e1, e2 son aristas múltiples o paralelas si f (e1) = f(e2).

Los multígrafos definidos no admiten bucles o lazos (aristas que conectan Un vértice consigo mismo). Usamos en este caso, pseudografos que son más generales que los multígrafos.

Definición 3 Un pseudografo G (V, E) consta de un conjunto V de vértices, un conjunto E de aristas y una función f de E en {{u, v}|u, v ∈ V }. Se dice que una arista e es un bucle o lazo si f (e) = {u, u} = {u} para algún

u ∈ V .

La diferencia entre grafo y dígrafo es que el último tiene los lados dirigidos y se entiende como un grafo dirigido.

Definición 4 Un grafo dirigido o dígrafo G = (V, E) consta de un conjunto

V de vértices, un conjunto E de aristas, que son pares ordenados de elementos de V.

Definimos los multígrafos dirigidos de la siguiente manera

Definición 5 Un multígrafo dirigido G (V,E) consta de un conjunto V de Vértices, un conjunto E de aristas y una función f de E en {(u, v)|u, v ∈ V }.

Se dice que las aristas e1, e2 son aristas múltiples o paralelas si f (e1) =

1.1. Adyacencia de Vértices, Incidencia de Aristas y

Grado de los Vértices Dos vértices u, v de un grafo G = (V, E) se dicen adyacentes si {u, v} ∈ E, asimismo dos aristas son adyacentes si tienen un mismo vértice como extremo; análogamente si e = {u, v} decimos que el lado e es incidente a los vértices u y v. El grado de un vértice es el número de lados incidentes a él. El grado de un vértice u se denota gr(u). Denotamos con ± (G) y ¢ (G) el mínimo y el máximo grado de los vértices de G respectivamente.

COMPONENTES DE UN GRAFO

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 está 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

Clasificación de grafos

Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.

Ejemplos

G1 = (V1, A1)

V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

G2 = (V2, A2)

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

G3 = (V3, A3)

V3 = {1, 2, 3} A3 = {<1, 2>, <2, 1>, <2, 3>}

Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:

Algunos de los principales tipos de grafos son los que se muestran a continuación:

Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.

Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular.

Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es

Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.

A continuación pueden verse los dibujos de K3, K4, K5 y K6

Un grafo bipartito regular: se denota Km, n donde m, n es el grado de cada conjunto disjunto de vértices.

A continuación ponemos los dibujos de K1, 2, K3, 3, y K2, 5

Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.

Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.

Grafos Eulerianos.

Para definir un camino euleriano es importante definir un camino euleriano primero. Un camino euleriano se define de la manera más sencilla como un camino que contiene todos los arcos del grafo.

Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano. El primer grafo de ellos no contiene caminos eulerianos mientras el segundo contiene al menos uno.

Grafos Conexos.

Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: "un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une".

Árboles.

Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también a cíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos).

Bosques de árboles.

Los bosques de árboles son un caso similar a los árboles, son a cíclicos, pero no son conexos. Como ejemplo tenemos la siguiente figura.

Recorrido de un grafo.

Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida. Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura; y el recorrido en profundidad.

Recorrido en anchura: El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.

Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente.

Representación de grafos en programas.

Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas.

Representación mediante matrices: La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.

Representación mediante listas: En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.

Representación mediante matrices dispersas: Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.

Dígrafo (grafo dirigido).

A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso.

Aplicaciones de los dígrafos

Una de las aplicaciones más importantes es de hallar el camino más corto hacia un destino, ya sea de una ciudad a otra, de unos departamentos a otros, para el recorrido de árboles, sirve para la representación de algoritmos, etc. Un ejemplo de esto es la tarea de freír un huevo.

Grado de un grafo.

Grado de incidencia positivo: El grado de incidencia positivo de un nodo nj es el número de arcos que tienen como nodo inicial a nj. Ejemplo: El grado de incidencia de 1 es igual a 3.

Grado de incidencia negativo: El grado de incidencia negativo de un nodo nj es el número de arcos que terminan en nj. Ejemplo: El grado de incidencia negativo de 1 es igual a 1.

Grado de un nodo: Paradigrafos es el grado de incidencia positivo menos el grado de incidencia negativo del nodo. Ejemplo: El grado de 1 es igual a 3 –1 = 2, el grado del nodo 4 es 2 –2 = 0. Para grafos no dirigidos es el número de líneas asociadas al nodo.

Ciclo de un grafo.

Ciclo: Es una cadena finita donde el nodo inicial de la cadena coincide con el nodo terminal de la misma.

Ciclo simple: Es el ciclo que a su vez es una cadena simple.

Estructuras no lineales: Grafos

Las estructuras de datos no lineales se caracterizan por no existir una relación de adyacencia, entre sus elementos, es decir, un elemento puede estar relacionado con cero, uno o más elementos.

La estructura no lineal de datos más general es el grafo donde sus nodos pueden relacionarse de cualquier manera sin una relación de orden predefinida.

Estructuras no lineales: Grafos Entre las múltiples aplicaciones que tienen estas estructuras podemos mencionar:

•Para modelar diversas situaciones tales como: sistemas de aeropuertos, flujo de tráfico, y responder a preguntas como: ¿Qué tiempo es más corto?, ¿Cómo es más barato?, o ¿Qué camino es más corto?

•Los grafos también son utilizados para realizar planificación de actividades, tareas del computador, planificar operaciones en lenguaje de máquinas para minimizar tiempo de ejecución. ¿Qué tarea debo hacer primero?

•Para representar circuitos eléctricos, de aguas etc... , y preguntar, están todas las componentes conectadas.

Grafos Los grafos pueden ser utilizados como la estructura básica para múltiples aplicaciones en el área de la Computación. Un grafo G (N, A, f) es un conjunto no vacío, donde:

•N={n1, n2, ... ,nM) es el conjunto de nodos o vértices

•A= {a1, a2,..., a K} es el conjunto de aristas y

• La función f: R →ΜΧΜindica los pares de nodos que esta αn relacionados.

•Grafos Dirigidos (Dígrafos) En estos grafos, las aristas que comunican dos nodos tienen un único sentido, una arista puede ir de x a y, pero no dé y a x. Se expresa gráficamente con flechas que indican el sentido de la relación entre cada par de nodos.

Grafos

•Grafos no dirigidos En estos grafos, las aristas que comunican dos nodos tienen dos sentidos. Si una arista va de x a y, la misma arista va de y a x. Se expresa gráficamente por líneas. La representación gráfica de un grafo se define con un círculo o rectángulo para los nodos y las relaciones con líneas o flechas según sea un grafo no dirigido o un dígrafo, respectivamente.

TIPOS DE GRAFOS.

Grafos Simples

Aquí lidiaremos con grafos simples, es decir en los que hay una arista o lado entre vértices como máximo, y en los que no hay loops o lazos que conectan algún vértice consigo mismo.
El grado de un nodo de un grafo simple es la cantidad de aristas o lados que concurren a él.

Trayectorias y Circuitos

Si en un grafo simple se van recorriendo sucesivamente sus aristas de modo tal que dos sucesivas sean adyacentes, es decir que concurran al mismo vértice por el que se pasa de una a la otra, se está recorriendo o determinando una trayectoria o
camino.
Cuando cierta trayectoria comienza y termina en el mismo nodo decimos que es un circuito.
Cuando una trayectoria pasa sólo una vez por todas y cada una de las aristas o lados se dice que la trayectoria es semi- euleriana, y si esta trayectoria fuera un circuito se la denomina circuito euleriano.

No existe un grafo simple con un sólo nodo de grado impar.
Esto refiere entre otros temas las paridades de los nodos de un grafo simple, es decir cuántos nodos pares e impares tiene.
Dado cierto grafo, al agregarle una arista, a cada nodo de los extremos de esta arista se le suma una unidad a su grado.
Es decir, que si alguno de esos nodos de los extremos tenían grado impar, pasan a tener grado par y viceversa.
Analizando las posibles combinaciones de paridades de estos nodos de los extremos del nuevo vértice:

                                      i) par-par,
                                     ii) par-impar,
                                    iii)impar-impar,

Se nota que la cantidad de nodos con grados impares resulta:
i)o aumentada en dos unidades,
ii)o inalterada,

iii)o reducida en dos unidades.

Para mostrar esto se toma un cierto conjunto de puntos del plano sin vértices que los conecten, y se lo considera un grafo sin vértices. Claramente todo nodo en este caso tiene grado cero.

Cualquier grafo simple puede entonces obtenerse partiendo de unir los nodos de un grafo sin vértices, agregando sucesivamente sus aristas, hasta completarlo.
A partir de esto puede afirmarse que todo grafo simple tiene o ningún nodo de grado impar o por lo menos dos nodos de grado impar.
Es decir, no existe un grafo simple con un sólo nodo de grado impar.

Grafos completos

En teoría de grafos, un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.

Un grafo completo de n vértices tiene n(n − 1) / 2 aristas, y se nota K_n. Es un grafo regular con todos sus vértices de grado n − 1. Ningún grafo completo tiene lazos y está conectado totalmente, por ende, la única forma de hacer disconexo el grafo con una eliminación de vértices es aplicarla a todos.

El teorema de Kuratowski dice que un grafo planar no puede contener K₅ (ó el grafo bipartito completo K_3,3) y todo K_n incluye a K_n_{− 1}, entonces ningún grafo completo K_n con es planar

Los grafos completos de 1 a 12 vértices son los siguientes:

K₁:0

K₂:1

K₃:3

K₄:6

K₅:10

K₆:15

K₇:21

K₈:28

K₉:36

K₁₀:45

K₁₁:55

K₁₂:66

Grafo bipartito

Un Grafo bipartito se denomina en Teoría de grafos a un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V₁ y V₂ y las aristas siempre unen vértices de un conjunto con vértices de otro:

no existe ninguna arista e = x₁,x₂ ni e = y₁,y₂

Siendo V el conjunto que contiene todos los vértices del grafo.

Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.

Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U de azul y los vértices deV de verde obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.

Un grafo bipartito suele con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si los dos subconjuntos tiene la misma cantidad de elementos, decimos que el grafo bipartito G es balanceado.

Ejemplo Grafo bipartito

Representación de grafos. Matriz de incidencia. Matriz de adyacencia.

Definición 1.4.1. Dado un grafo G = (V, E) con n vértices {v1, ..., vn} su matriz de

adyacencia es la matriz de orden n×n, A(G)=(aij) donde aij es el número de aristas que

unen los vértices vi y vj.

Ejemplo 1.4.2.

La matriz de adyacencia de un grafo es simétrica. Si un vértice es aislado entonces la

correspondiente fila (columna) esta compuesta sólo por ceros. Si el grafo es simple

entonces la matriz de adyacencia contiene solo ceros y unos (matriz binaria) y la diagonal esta compuesta sólo por ceros.

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Historia

Puentes de Königsberg.

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología.

En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos.

En 1852 Francis Guthrie planteó el problema de los cuatro colores que plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appely Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.

Estructuras de datos en la representación de grafos

Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.

Estructura de lista

Grafo de lista de adyacencia.

lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.

lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.

En esta estructura de datos la idea es asociar a cada vértice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vértices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.

Estructuras matriciales

Matriz de incidencia - El grafo está 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 - El grafo está representado por una matriz cuadrada M de tamaño n², donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento m_x_,y es 1, de lo contrario, es 0.

Definiciones

Vértice

Los vértices constituyen uno de los dos elementos que forman un grafo. Como ocurre con el resto de las ramas de las matemáticas, a la Teoría de Grafos no le interesa saber qué son los vértices.

Diferentes situaciones en las que pueden identificarse objetos y relaciones que satisfagan la definición de grafo pueden verse como grafos y así aplicar la Teoría de Grafos en ellos.

Grafo

En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.

Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que . Para simplificar, notaremos la arista (a,b) como ab.

En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.

Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad.

Subgrafo

Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H (dependiendo de las necesidades de la situación).

El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de vértices de G.

Definición:

Sea G=(V, A). G’=(V’,A’) se dice subgrafo de G si:

1- V’ V

2- A' A

3- (V’,A’) es un grafo

Si G’=(V’,A’) es subgrafo de G, para todo v G se cumple gr (G’,v)≤ gr (G, v)

G2 es un subgrafo de G.

Aristas dirigidas y no dirigidas

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus direcciones únicas. El conjunto de aristas será ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a, b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos orientados, como el siguiente:

Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).

En el grafo anterior se ha utilizado una arista que tiene sus dos extremos idénticos: es un lazo (o bucle), y aparece también una arista bidireccional, y corresponde a dos aristas orientadas.

Aquí V = { a, b, c, d, e }, y A = { (a, c), (d, a), (d, e), (a, e), (b, e), (c, a), (c, c), (d, b) }.

Se considera la característica de "grado" (positivo o negativo) de un vértice v (y se indica como (v)), como la cantidad de aristas que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas incidentes a este vértice. Por ejemplo, el grado positivo (salidas) de d es 3, mientras que el grado negativo (llegadas) de d es 0.

Según la terminología seguida en algunos problemas clásicos de Investigación Operativa (p.ej.: el Problema del flujo máximo), a un vértice del que sólo salen aristas se le denomina fuente (en el ejemplo anterior, el vértice d); tiene grado negativo 0. Por el contrario, a aquellos en los que sólo entran aristas se les denomina pozo o sumidero (en el caso anterior, el vértice e); tiene grado positivo 0. A continuación se presentan las implementaciones en maude de grafos no dirigidos y de grafos dirigidos.En los dos casos, las especificaciones incluyen, además de las operaciones generadoras, otras operaciones auxiliares.

Ciclos y caminos hamiltonianos

Ejemplo de un ciclo hamiltoniano.

Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. 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).

Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas).

Se habla también de camino hamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada. Por ejemplo, un caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano. Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro.

Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en tiempo polinómico, siendo la búsqueda por fuerza bruta de todos los posibles caminos u otros métodos excesivamente costosos. Existen, sin embargo, métodos para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeños.

El problema de determinar la existencia de ciclos hamiltonianos, entra en el conjunto de los NP-completos.

Caracterización de grafos

Grafos simples

Un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

Un grafo que no es simple se denomina multigrafo.

Grafos conexos

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

Grafos completos

Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.

El conjunto de los grafos completos es denominado usualmente

, siendo

el grafo completo de n vértices.

, es decir, grafo completo de n vértices tiene exactamente

aristas.

La representación gráfica de los

como los vértices de un polígono regular da cuenta de su peculiar estructura.

Grafos bipartitos

Un grafo G es bipartito si puede expresarse como (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:

V₁ y V₂ son disjuntos y no vacíos.
Cada arista de A une un vértice de V₁ con uno de V₂.
No existen aristas uniendo dos elementos de V₁; análogamente para V₂.

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 en los que debe unirse un elemento de la columna A con un elemento de la columna B.

Operaciones en Grafos

Subdivisión elemental de una arista

se convierte en

Se reemplaza la arista

por dos aristas

y un vértice w.

Después de realizar esta operación, el grafo queda con un vértice y una arista más.

Eliminación débil de un vértice

y g(v) = 2 (Sea v un vértice del grafo y de grado dos) eliminarlo débilmente significa reemplazarlo por una arista que une los vértices adyacentes a v.

se convierte en

Entonces e' y e'' desaparecen y aparece

Homeomorfismo de grafos

Dos grafos G₁ y G₂ son homeomorfos si ambos pueden obtenerse a partir del mismo grafo con una sucesión de subdivisiones elementales de aristas.

Árboles

Ejemplo de árbol.

Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas, y hay n^n-2árboles posibles. Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas. Un importante campo de aplicación de su estudio se encuentra en el análisis filogenético, el de la filiación de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguación del parentesco entre especies; aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas.

Grafos ponderados o etiquetados

En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así un grafo valuado.
Formalmente, es un grafo con una función v: A → R₊.

Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la valuación será la distancia entre ellas.
Y, de momento, no se conocen métodos generales para hallar un ciclo de valuación mínima, pero sí para los caminos desde a hasta b, sin más condición.

Teorema de los cuatro colores

En 1852 Francis Guthrie planteó el problema de los cuatro colores.

Otro problema famoso relativo a los grafos: ¿Cuántos colores son necesarios para dibujar un mapa político, con la condición obvia que dos países adyacentes no puedan tener el mismo color? Se supone que los países son de un solo pedazo, y que el mundo es esférico o plano. En un mundo en forma de toroide; el teorema siguiente no es válido:

Cuatro colores son siempre suficientes para colorear un mapa.

El mapa siguiente muestra que tres colores no bastan: Si se empieza por el país central a y se esfuerza uno en utilizar el menor número de colores, entonces en la corona alrededor de a alternan dos colores. Llegando al país h se tiene que introducir un cuarto color. Lo mismo sucede en i si se emplea el mismo método.

La forma precisa de cada país no importa; lo único relevante es saber qué país toca a qué otro. Estos datos están incluidos en el grafo donde los vértices son los países y las aristas conectan los que justamente son adyacentes. Entonces la cuestión equivale a atribuir a cada vértice un color distinto del de sus vecinos.

Hemos visto que tres colores no son suficientes, y demostrar que con cinco siempre se llega, es bastante fácil. Pero el teorema de los cuatro colores no es nada obvio. Prueba de ello es que se han tenido que emplear ordenadores para acabar la demostración (se ha hecho un programa que permitió verificar una multitud de casos, lo que ahorró muchísimo tiempo a los matemáticos). Fue la primera vez que la comunidad matemática aceptó una demostración asistida por ordenador, lo que ha creado una fuerte polémica dentro de la comunidad matemática, llegando en algunos casos a plantearse la cuestión de que esta demostración y su aceptación es uno de los momentos que han generado una de las más terribles crisis en el mundo matemático.

Coloración de grafos

Colores en los vértices.

Definición: Si G=(V, E) es un grafo no dirigido, una coloración propia de G, ocurre cuando coloreamos los vértices de G de modo que si {a, b} es una arista en G entonces a y b tienen diferentes colores. (Por lo tanto, los vértices adyacentes tienen colores diferentes). El número mínimo de colores necesarios para una coloración propia de G es el número cromático de G y se escribe como C (G). Sea G un grafo no dirigido sea λ el número de colores disponibles para la coloración propia de los vértices de G. Nuestro objetivo es encontrar una función polinomial P (G,λ), en la variable λ, llamada polinomio cromático de G , que nos indique el número de coloraciones propias diferentes de los vértices de G, usando un máximo de λ colores.

Descomposición de polinomios cromáticos. Si G=(V, E) es un grafo conexo y e pertenece a Ε , entonces: P (G,λ)=P (G+e,λ)+P (G/e,λ), donde G/e es el grafo se obtene por contracción de aristas.

Para cualquier grafo G, el término constante en P (G,λ) es 0

Sea G=(V, E) con |E|>0 entonces, la suma de los coeficientes de P (G,λ) es 0.

Sea G=(V, E), con a, b pertenecientes al conjunto de vértices V pero {a, b}=e, no perteneciente a al conjunto de aristas E. Escribimos G+e para el grafo que se obtiene de G al añadir la arista e={a, b}. Al identificar los vértices a y b en G, obtenemos el subgrafo G++e de G.

Grafos planos

Un grafo es plano si se puede dibujar sin cruces de aristas. El problema de las tres casas y los tres pozos tiene solución sobre el toro, pero no en el plano.

Cuando un grafo o multigrafo se puede dibujar en un plano sin que dos segmentos se corten, se dice que es plano.

Un juego muy conocido es el siguiente: Se dibujan tres casas y tres pozos. Todos los vecinos de las casas tienen el derecho de utilizar los tres pozos. Como no se llevan bien en absoluto, no quieren cruzarse jamás. ¿Es posible trazar los nueve caminos que juntan las tres casas con los tres pozos sin que haya cruces?

Cualquier disposición de las casas, los pozos y los caminos implica la presencia de al menos un cruce.

Sea K_n el grafo completo con n vértices, K_{n, p} es el grafo bipartito de n y p vértices.

El juego anterior equivale a descubrir si el grafo bipartito completo K_3,3 es plano, es decir, si se puede dibujar en un plano sin que haya cruces, siendo la respuesta que no. En general, puede determinarse que un grafo no es plano, si en su diseño puede encontrase una estructura análoga (conocida como menor) a K₅ o a K_3,3.

Establecer qué grafos son planos no es obvio, y es un problema que tiene que ver con topología.

Diámetro

En la figura se nota que K₄ es plano (desviando la arista ab al exterior del cuadrado), que K₅ no lo es, y que K₃,₂ lo es también (desvíos en gris).

En un grafo, la distancia entre dos vértices es el menor número de aristas de un recorrido entre ellos. El diámetro, en una figura como en un grafo, es la mayor distancia entre dos puntos de la misma.

El diámetro de los K_n es 1, y el de los K_n,_p es 2. Un diámetro infinito puede significar que el grafo tiene una infinidad de vértices o simplemente que no es conexo. También se puede considerar el diámetro promedio, como el promedio de las distancias entre dos vértices.

El mundo de Internet ha puesto de moda esa idea del diámetro: Si descartamos los sitios que no tienen enlaces, y escogemos dos páginas web alazar: ¿En cuántos clics se puede pasar de la primera a la segunda? El resultado es el diámetro de la Red, vista como un grafo cuyos vértices son los sitios, y cuyas aristas son lógicamente los enlaces.

En el mundo real hay una analogía: tomando al azar dos seres humanos del mundo, ¿En cuántos saltos se puede pasar de uno a otro, con la condición de sólo saltar de una persona a otra cuando ellas se conocen personalmente? Con esta definición, se estima que el diámetro de la humanidad es de... ¡ocho solamente!

Este concepto refleja mejor la complejidad de una red que el número de sus elementos.

Algoritmos importantes

Algoritmo de búsqueda en anchura (BFS)
Algoritmo de búsqueda en profundidad (DFS)
Algoritmo de búsqueda A*
Algoritmo del vecino más cercano
Ordenación topológica de un grafo
Algoritmo de cálculo de los componentes fuertemente conexos de un grafo
Algoritmo de Dijkstra
Algoritmo de Bellman-Ford
Algoritmo de Prim
Algoritmo de Ford-Fulkerson
Algoritmo de Kruskal
Algoritmo de Floyd-Warshall

Aplicaciones

Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en toda las áreas de Ingeniería.

Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.

Para la administración de proyectos, utilizamos técnicas como PERT en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.

La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red. Esta medida permite cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse gráficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el poder se transmite y a quiénes.

Los grafos son importantes en el estudio de la biología y hábitat. El vértice representa un hábitat y las aristas (o "edges" en inglés) representa los senderos de los animales o las migraciónes. Con esta información, los científicos pueden entender cómo esto puede cambiar o afectar a las especies en su hábitat.

Investigadores relevantes en Teoría de grafos

Leonhard Euler
Edsger Dijkstra
Paul Erdős
Frank Harary
Dénes König
Kazimierz Kuratowski
Gerhard Ringel
W.T. Tutte

ALGORITMOS DE RECORRIDOS Y DE BUSQUEDA.

Al visitar los nodos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente los nodos de un árbol.

Los ordenamientos más importantes son llamados: preorden, post-orden y en-orden y se definen recursivamente como sigue:

Si un árbol T es nulo, entonces, la lista vacía es el listado preorden, post-orden y en-orden del árbol T.

Si T consiste de un sólo nodo n, entonces, n es el listado preorden, post-orden y en-orden del árbol T.

Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes:

• visitar el nodo raíz

• recorrer el subárbol izquierdo

• recorrer el subárbol derecho

Estas tres acciones llevadas a cabo en distinto orden proporcionan los distintos recorridos del árbol.

Recorrido en PRE-ORDEN:

• Visitar el raíz

• Recorrer el subárbol izquierdo en pre-orden

• Recorrer el subárbol derecho en pre-orden

Recorrido EN-ORDEN

• Recorrer el subárbol izquierdo en en-orden• Visitar el raíz• Recorrer el subárbol derecho en en-orden

Recorrido en POST-ORDEN

• Recorrer el subárbol izquierdo en post-orden

• Recorrer el subárbol derecho en post-orden

• Visitar el raíz

Recorridos

Si T es un árbol con raíz n y subárboles T1, T2, . . . , Tk, entonces, El listado pre-orden de los nodos de T es la raíz n, seguida por los nodos de T1 en pre-orden, después los nodos de T2 en preorden, y así, hasta los nodos de Tk en pre-orden.

El listado post-orden de los nodos de T es los nodos de T1 en postorden, seguidos de los nodos de T2 en post-orden, y así hasta los nodos de Tk en post-orden, todos ellos seguidos de n. El listado en-orden de los nodos de T es los nodos de T1 en-orden, seguidos por n, seguidos por los nodos de T2, . . . , Tk, cada grupo.

Recorreremos el Árbol Siguiente:

Recorrido Pre Orden (RID)

El recorrido en Pre Orden del árbol es el siguiente: 15, 6, 4, 10, 20, 17, 22

Recorrido En Orden(IRD)

El recorrido en En Orden del árbol es el siguiente: 4, 6, 10, 15, 17, 20, 22

Recorrido Post Orden(IDR)

El recorrido en Post Orden del árbol es el siguiente: 4, 10, 6, 17, 22, 20, 15

En este tema trataremos las diferentes formas de hacer recorridos de un árbol de una expresión algebraica, con el fin de poder cambiar de manera algorítmica una expresión en sufijo a forma de prefijo o posfijo.

Se llama recorrido de un árbol al proceso que permite acceder una sola vez a cada uno de los elementos del árbol para examinar el conjunto completo. Primeramente se ven los algoritmos para construir el árbol, para la expresión dada en sufijo, prefijo o posfijo y también se presentan algoritmos para reconocer si una expresión está correcta cuando esta dada en prefijo o posfijo.

Recorridos

Al visitar los elementos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente. Los ordenamientos más importantes son llamados: prefijo, sufijo y posfijo.

Los algoritmos de recorrido de un árbol presentan tres tipos de actividades:

* visitar el nodo raíz

* recorrer el subárbol izquierdo

* recorrer el subárbol derecho

Estas tres acciones llevadas a cabo en distinto orden proporcionan los distintos recorridos del árbol.

Recorrido en PREFIJO:

* Visitar la raíz

* Recorrer el subárbol izquierdo en prefijo

* Recorrer el subárbol derecho en prefijo

Recorrido SUFIJO:

* Recorrer el subárbol izquierdo en sufijo

* Visitar la raíz

* Recorrer el subárbol derecho en sufijo

Recorrido en POSFIJO:

* Recorrer el subárbol izquierdo en postfijo

* Recorrer el subárbol derecho en postfijo

* Visitar la raíz

Algoritmo de búsqueda

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La variante más simple del problema es la búsqueda de un número en un vector.

Árboles binarios

Un árbol binario representado con nodos ligados:
Como lo indica su nombre, estos árboles esta formados por nodos que pueden tener un máximo de 2 hijos.

DEFINICIONES:

Árbol relleno: Cuando todo nodo tiene 2 hijos bien es hoja.

Árbol binario completo: Un árbol binario rellenen dónde todas las hojas tienen la misma profundidad.

Métodos para recorrer un árbol binario:

a) Pre-orden (perder):

1. Primero se recorre la raíz

2. Segundo se recorre el subárbol izquierdo en pre-orden

3. Tercero se recorre el subárbol derecho en pre-orden

b) En-orden (inorder)

1. Primero se recorre el subárbol izquierdo en-orden

2. Segundo se recorre la raíz

3. Tercero se recorre el subárbol derecho en-orden

c) Post-orden (postorder)

1. Primero se recorre el subárbol izquierdo en post-orden

2. Segundo se recorre el subárbol derecho en post-orden

3. Tercero se recorre la raíz

Intercambiando izquierda por derecha en los tres métodos anteriores se obtienen tres métodos a los cuales se les llama:

1. Pre-orden converso

2. En-orden converso

3. Post-orden converso

Observando el ejemplo de la figura:

Recorriendo a este árbol con en los diferentes métodos se obtendrían las siguientes cadenas:

pre-orden : 32 1 5 1 8 11 17 23 56 43 41 53 72 64 80
en-orden : 1 5 8 1 17 11 23 32 41 43 53 56 64 72 80
post-orden : 1 8 5 17 23 11 1 41 53 43 64 80 72 56 32

PROPIEDADES

Todo árbol es a su vez un grafo bipartito. Todo árbol con sólo un conjunto numerable de vértices es además un grafo plano.

Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G.

Dado n vértices etiquetados, hay n ⁿ⁻² maneras diferentes de conectarlos para construir un grafo. El resultado se llama fórmula de Cayley. El número de árboles con n vértices de grado d₁,d₂,...,d_nes:

que es un coeficiente multinomial.

Contar el número de árboles no etiquetados es un problema complicado. De hecho, no se conoce ninguna fórmula para el número de árboles t(n) con n vértices (debe entederse aquí el número de árboles diferentes salvo isomorfismo de grafos). Los primerlos valores de t(n) son 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, ... (sucesión A000055 en OEIS). Otter (1948) probó que

Una fórmula más exacta para el comportamiento asintótico de t(n) implica que hay dos números α y β (α ≈ 3 y β ≈ 0.5) tales que:

Los árboles son una clase de grafos. Un claro ejemplo de un árbol es el siguiente:

Consideremos cuatro parejas de chismosos {a, A, b, B, c, C, d, D} donde a, b, c y d son los esposos y A, B, C y D son sus esposas respectivamente. Supongamos que a llama a su esposa para contarle algún chisme, entonces ella llama a las otras señoras para difundir el chisme, y cada una de ellas a su vez llama a su esposo para comunicárselo. El siguiente grafo muestra la propagación del chisme:

Un árbol es un grafo no dirigido conexo que no contiene circuitos, es decir que no existen dos o más paseos sobre un par de vértices.

Un conjunto de árboles disjuntos es llamado bosque. Un vértice de grado 1 en un árbol se llama hoja o un nodo terminal, y un vértice de grado mayor que 1 recibe el nombre de rama o nodo interno. Por ejemplo, son hojas: b, c, d y los vértices a, A, B, C, D son nodos rama.

Las propiedades de los árboles son:

Existe un único paseo entre dos vértices cualesquiera de un árbol.

El número de vértices es mayor en uno al número de aristas de un árbol.

Un árbol con dos o más vértices tiene al menos dos hojas.

Un árbol T (libre) es una gráfica simple que satisface lo siguiente; si v y w son vértices en T, existe

CLASIFICACIÓN POR ALTURA Y NÚMERO DE NODOS

Árbol general: Es una estructura jerárquica aplicada sobre una colación de elementos u objetos llamados nodos, uno de los cuales es conocido como raíz y en conjunto tienen una relación o parentesco entre ellos

Árbol binario: Es un conjunto Finito de nodos en el cual cada nodo tiene como máximo 2 sub árboles, llamados sub árbol izquierdo y derecho.

Árbol binario formal:

1.- t es vacío en cuyo caso se llama árbol nulo

2.- T Tiene un nodo Distinguido de R llamado raíz de Y los restantes nodos de T forman un par ordenado de árboles binarios T1 que es el subárbol izquierdo y T2 el subárbol derecho.

Clasificación de árboles binarios:

1.-arbol binario distinto: Se dice que un árbol es distinto cuando su estructura grafica es diferente.

2.-arbol binario similar.- Se dice que un árbol es similar cuando su estructura grafica es idéntica pero la información que contiene entre sus nodos es diferente.

3.-arbol binario equivalente.-Son aquellos que su estructura grafica es idéntica pero además la información entre sus nodos.

4.-arbol binario completo.-son aquellos en el que todos sus nodos excepto el último nivel tienen sus dos hijos.

5.-arbol binario lleno: es aquel que tiene su número máximo de posibles nodos.

APLICACIONES DE GRAFOS Y ARBOLES

En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.

Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad.

]Subgrafo

El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de vértices de G.

Definición:

Sea G=(V, A). G’=(V’,A’) se dice subgrafo de G si:

1- V’ V

2- A' A

3- (V’,A’) es un grafo

Si G’=(V’,A’) es subgrafo de G, para todo v G se cumple gr (G’,v)≤ gr (G, v)

G2 es un subgrafo de G.

Aristas dirigidas y no dirigidas

Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).

En el grafo anterior se ha utilizado una arista que tiene sus dos extremos idénticos: es un lazo (o bucle), y aparece también una arista bidireccional, y corresponde a dos aristas orientadas.

Aquí V = { a, b, c, d, e }, y A = { (a, c), (d, a), (d, e), (a, e), (b, e), (c, a), (c, c), (d, b) }.

Ejemplo de árbol.

Grafos ponderados o etiquetados

Programación no numérica - Grafos

Definición de 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 es necesariamente jerárquica. 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 termino “registro” al hacer referencia a archivos y “nodo” cuando se usan listas enlazadas, arboles 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.

Esta definición da lugar a una representación gráfica, en donde cada vértice es un punto del plano, y cada arista es una línea que une a sus dos vértices.

Si el dibujo puede efectuarse sin que haya superposición de líneas, se dice que G es un grafo plano. Por ejemplo, el siguiente es un grafo plano:

puesto que es equivalente a este otro:

Representación de un grafo :

Existen dos formas de mantener un grafo “G” en la memoria de una computadora, una se llama Representación secuencial de G, la cual se basa en la matriz de adyacencia A; la otra forma, es la llamada Representación enlazada de G y se basa en listas enlazadas de vecinos. Independientemente de la forma en que se mantenga un grafo G en la memoria de una computadora, el grafo G normalmente se introduce en la computadora por su definición formal: Un conjunto de nodos y un conjunto de aristas.

Representación secuencial de un grafo :

aplicación de grafos y arboles

Mate Discretas Unidad 6

jueves, 1 de diciembre de 2011

TEORIA DE GRAFOS

3 comentarios: