Grafos
Objetivo:
Comprenderá y resolverá problemas de la teoría de grafos.
Introducción
Hoy en día podemos ver muchas cosas que nos pueden parecer de lo mas cotidianas, carreteras, líneas telefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas, automóviles, y tantas cosas mas; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos.
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras.
Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.
Los árboles forman una de las subclases de gráficas que más se utilizan. En particular, la ciencia de la computación hace uso de los árboles ampliamente. En computación, los árboles son útiles para organizar y relacionar datos en una base de datos.
Concepto
N = nodo
Por lo general, los nodos son entes de procesamiento o estructuras que contienen algún tipo de información y las líneas o flechas son conexiones o relaciones entre estos entes.
Es un conjunto de nodos unidos por un conjunto
de líneas o flechas.
S = arista
La forma de representar los grafos es:G(N,S)
y los segmentos serán:S = {u, v}
Ejemplo:Representa un grafo plano con 5 nodos llamados a, b, c, d y e; y 6 segmentos unidos de la siguiente forma: s1={a,b}, s2={c,d}, s3={b,e}, s4={e,c}, s5={e,d}, s6={a,c}
a
b
c
d
e
s1
s2
s3
s4
s5
s6
Valencia: También llamado grado de un vértice v, es el número de lados incidentes en v. Por definición, si v tiene un lazo, entonces este contribuye en 2 a la valencia del v. El grado máximo de un grafo G es denotado por Δ(G) y el grado mínimo de un grafo G es denotado por δ(G).
Camino: Es un recorrido que tiene aristas diferentes, o sea, que no use la misma arista mas de una vez.
Sendero: es un camino en el cual todos los segmentos son diferentes
Trayectoria: es un camino en el cual todos los nodos son diferentes
Lazo: bucle es una arista que relaciona al mismo nodo; es decir, es aquél que va dirigido a sí mismo.
Ramas paralelas: Las ramas paralelas o segmentos múltiples: son aristas que conectan las mismas terminales. Es decir, que del mismo vértice parten 2 o más aristas a otro.
Tipos de Grafos
Grafo no dirigido
Son aquellos en los cuales los lados no están orientados (No son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).
Grafo dirigido
A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso.
Grafo regular
Es un grafo donde cada vértice tiene el mismo grado o valencia. Un grafo regular con vértices de grado k es llamado grafo k-regular o grafo regular de grado k.
Los Grafos regulares de grado hasta 2 son fáciles de clasificar: Un grafo 0-regular consiste en un grafo con vértices desconectados, un grafo 1-regular consiste en un grafo con aristas desconectadas, y un grafo 2-regular consiste en un ciclo.
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.
Grafo completo
Aquel con una arista entre cada par de vértices.
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 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”.
Grafos eulerianos
Un camino euleriano contiene todos los arcos del grafo.
Grafos hamilyaneano
Un camino hamiltoneano contiene todos los nodos del grafo.
Grafos rotulado
Un grafo rotulados es aquel en el a sus segmentos se les asigna
un dato, es decir un número no negativo l(s), llamado peso o longitud de s
a
b
c
d
e
1
2
3
4
1
2
a
b
c
d
e
1
2
3
4
1
2
Grafos árbol
Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.
Relación en Di-grafos o Grafos dirigidos
Una relación R de un grafo es el subconjunto de elementos que pertenezcan al grafo, es decir los elementos del conjunto A están relacionados con A. La forma de representar una relación de un di-grafo y en la siguiente:
Matriz de Relación: se representa
MR = [mij}, mij =
Ejemplo:
Sea A = { 1, 2, 3, 4}, y R = {(1,1), (1,2), (2,1), (2,2), (2,3), (2,4), (3,4), (4,1)}Genera la matriz de relación y el grafo dirigido
1 Si (ai, aj) R
0 Si (ai, aj) R
Serie de ejercicios:
1.- del libro Matemáticas discretas , Kolma hacer:
Página 116, del 19 al 22
2.- del libro Matemáticas discretas , Johnsonbaugh
Página 116, del 1 al 3 y el 7
Matriz de adyacencia
Es una matriz cuadrada en la cual los nodos del grafo se indican como renglones y como columnas. El orden de los nodos es el mismo que guardan los renglones y las columnas de la matriz. Se coloca 1 como elemento de la matriz cuando existe una relación entre uno y otro vértice, o bien un 0 cuando no exista relación alguna. En una matriz de adyacencia no es posible representar lados paralelos.
Ejemplos
Matriz de incidencia
En esta matriz se colocan los nodos del grafo como renglones y las aristas como columnas. En esta matriz si es posible representar lados paralelos. Al sumar los elementos de cada una de los renglones se obtiene la valencia de los nodos, al sumar las columnas es posible distinguir cuando se trata de un lazo ya que su suma es 1.
Serie de ejercicios:
1.- del libro Matemáticas discretas , Johnsonbaugh
Página 348, del 1, 3, 5 y el 7, 9, 14, 22 gpo APágina 355 1, 4, 9
Página 348 el 2, 4, 6 y el 8, 13, 16, 26 gpo BPágina 355 el 3, 8, 10
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.
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.