Download TRAJO SOBRE GRAFOS

GRAFOS
CREACIÓN DE ÍNDICES EN GOOGLE DE
LOS SITIOS DE LA RED DE INTERNET
INDICE
1. Introducción
2. Conceptos matemáticos con ejemplos
3. Resolución de ejercicios
4. Ejercicios con Maxima
5. Explicación del modelo ilustrada con un ejemplo
6. Ejercicios propuestos sobre el tema
7. Bibliografía
Tania Guzmán García
Luis González Varela
Alexandre González Rivas
1. Introducción
La teoría de grafos es una disciplina antigua con muchas
aplicaciones modernas. Sus ideales básicos fueron introducidos por el
gran matemático suizo Leonhard Euler (1700-1783) en el siglo XVIII.
L. Euler utilizó los grafos para resolver el famoso problema de los
puentes de Königsberg que se considera el primer trabajo sobre esta
materia.
Los grafos se emplean para resolver problemas de diversas
áreas. Pueden utilizarse, por ejemplo, para determinar si se puede o
no implementar un circuito sobre una placa de una sola capa, para
estudiar la estructura de una red de Internet, para determinar si dos
ordenadores están conectados o no dentro de una red informatizada,
para hallar el camino más corto entre dos ciudades en una red de
transportes, para trazar rutas de vuelo en un espacio aéreo
concreto…
El primer ejemplo de trabajo con grafos fue este trabajo que
surgió para resolver un problema en la ciudad de Königsberg (Rusia).
La ciudad estaba dividida en cuatro partes por dos brazos del río
Pregel estando conectadas por siete puentes.
La pregunta que se hizo L. Euler fue: ¿Es posible recorrer los
siete puentes pasando por todos ellos una única vez, partiendo y
llegando al mismo sitio?
Para intentar resolver este problema representó
esquemáticamente las áreas de tierra por puntos y los puentes por
líneas conectando esos puntos. El resultado fue el siguiente grafo:
e1
B
e3
A
e2
e5
e4
e6
e7
D
V = {A,B,C,D}
C
E = {e1,e2,e3,e4,e5,e6,e7}
e1 = {A,B}…e7 = {C,D}
2. Conceptos matemáticos con ejemplos
Grafo. “Informalmente, un grafo es un 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.” 1
Definición formal. “Un grafo es un par G =
(V,E), donde V es un conjunto finito no
vacío, cuyos elementos se llaman vértices o
nodos y, E es una familia, cuyos elementos
se llaman aristas. Una rasita es un par no
ordenado de vértices de V.” 2
Grafo etiquetado con 6 vértices y 7 aristas.
Tipos de grafos.
1
2

Grafos simples. Un grafo simple es un conjunto de vértices y

Multigrafos. Son grafos que contienen dos aristas que conectan

Pseudografos. Son multigrafos que permiten la existencia de

Grafos dirigidos. Son grafos que, indistintamente de si son
aristas. Las aristas unen pares de vértices, no habiendo dos
aristas que conecten el mismo par.
el mismo par de vértices.
lazos o aristas que unen un vértice consigo mismo.
simples, multigrafos, o pseudografos, tienen aristas con
dirección o aristas dirigidas. Los grafos sin aristas dirigidas son
grafos no dirigidos.
http://es.wikipedia.org/wiki/Grafo
Definición recogida en los apuntes de Matemática Discreta de la FIC (2006-2007), tema 5 pág. 100
Terminologías o propiedades.

Etiquetado. Distinción que se hace a los vértices y/o aristas
mediante una marca que los hace unívocamente distinguibles
del resto, es decir, asignarle a cada vértice o arista un nombre.
Quedan registrados los vértices A y B y la arista que los une
como e1.
e1
A

B
Adyacencia. Se dice que dos vértices son adyacentes si hay una
arista que los conecte entre ellos. A y B son adyacentes.
A

B
Grado de un vértice. El grado de un vértice es un número natural
de 0 al infinito que designa el número de aristas le conectan
con otros vértices. El grado de A es 2.
A
B
C

Incidencia. Una arista es incidente a un vértice si ésta lo une a
otro. E1 es una arista incidente entre A y B.
e1
A

B
Ponderación. Corresponde a una función que a cada arista le
asocia un valor (costo, peso, longitud, etc.), para aumentar la
expresividad del modelo. El valor ponderado de la arista entre
A y B es 6.
6
A
B
9

C
Camino. Un camino es una secuencia de aristas que comienzan
en un vértice del grafo y recorren parte o la totalidad del grafo
conectando vértices adyacentes. E,R,T,Y,U,I es un camino del
grafo.
E
R
T
Y
U
I

Circuito. Cuando existe un camino que empieza y acaba en el
mismo vértice. El siguiente grafo contiene el circuito V,B,N,M,V.
B
V
N
M

Isomorfismo. Si dos grafos son isomorfos sólo varía la
apariencia, es decir, que se mantienen las adyacencias,
estructura, caminos, ciclos, número de vértices y número de
aristas. Los dos grafos son isomorfos.
A
B
E
R
T
C

Conexo. Un grafo es conexo si tiene una única componente
conexa, es decir, todos los vértices del grafo están
relacionados. En el caso contrario sería un grafo disconexo.
A
B
Grafo conexo
C
E
R
Grafo disconexo
T
Y
Familias de grafos simples

Grafo regular. Un grafo simple es regular si todos sus vértices

Grafo completo. El grafo completo es aquel que tiene

Grafo complementario. Un grafo complementario es aquel grafo
tienen el mismo grado.
exactamente una arista entre cada par de vértices.
que contiene todos los vértices del original y las aristas que no
estás.
Grafo original
Grafo complementario

Grafo bipartito. Un Grafo bipartito se denomina en Teoría de

Grafo bipartito completo. Cumple ambas condiciones.
grafos a un grafo no dirigido cuyos vértices se pueden separar
en dos conjuntos disjuntos y teniendo que las aristas siempre
unirán vértices de un conjunto con vértices de otro.
Árboles
Definición de árbol. Un árbol es un grafo conexo y
sin ciclos o lazos, es decir, un grafo simple.
G
Un árbol etiquetado con 6 vértices y 5
aristas
G’
Otros ejemplos de árboles
Terminologías o propiedades.

Definición de bosque. Un árbol es considerado un bosque si sus

Árbol generador. Un árbol generador de un grafo conexo es un

Árbol generador mínimo. El árbol generador mínimo es un árbol

Raíz. Un árbol con raíz es un árbol en el que uno de sus vértices
componentes conexas son árboles.
subgrafo conexo con el menor número posible de aristas y con
todos los vértices del grafo original. No tiene porque ser único.
generador construido sobre un grafo conexo ponderado con un
criterio de selección de aristas definido por su menor peso.
ha sido designado como la raíz y todas las aristas están
colocadas alejándose de dicha raíz.
Raíz

Padre. Se considera padre de un vértice al vértice adyacente

Hijo. Se consideran hijos de un vértice a todos los vértices
superior.
comunicados por una arista y adyacentes que se encuentren
por de este. A es padre de B y C o lo que es lo mismo B y C son
hijos de A
A
B

C
Hoja. Son los vértices que no tienen hijos. En este ejemplo
A,B,C,D,E son hojas del árbol.
A
E
D
B
C
Búsqueda en profundidad y búsqueda en profundidad en grafos dirigidos.

3
Búsqueda en profundidad. ”Una Búsqueda en profundidad es un
algoritmo que permite recorrer todos los nodos de un grafo o
árbol de manera ordenada, pero no uniforme. Su
funcionamiento consiste en ir expandiendo todos y cada uno de
los nodos que va localizando, de forma recurrente, en un
camino concreto. Cuando ya no quedan más nodos que visitar
en dicho camino, regresa, de modo que repite el mismo
proceso con cada uno de los hermanos del nodo ya
procesado”.3
http://es.wikipedia.org/wiki/B%C3%BAsqueda_en_profundidad
Algoritmo de ejemplo de una búsqueda en profundidad 4:
procedure BP(G: grafo conexo de vértices v1,v2,… vn)
T:= árbol que consta sólo del vértice v1
visita(v1)
procedure visita(v: vértice de G)
for cada vértice w adyacente a v y que no esté en T
begin
añadir el vértice w y la arista {v,w} a T
visita(w)
end

a
Búsqueda en profundidad en grafos dirigidos. La búsqueda en
grafos dirigidos es muy similar a la búsqueda sobre un grafo
no-dirigido, sin embargo, el resultado final no tiene porque ser
un árbol generador del grafo original sino que puede ser un
bosque. 5
b
c
f
g
e
d
a
d
b
h
h
j
i
c
f
g
e
l
Una búsqueda de ejemplo en un grafo dirigido.
4
5
l
k
Rosen, Kenneth H. Matemática discreta y sus aplicaciones, página 632.
Rosen, Kenneth H. Matemática discreta y sus aplicaciones, página 637.
k
j
j
3. Resolución de ejercicios
4. Ejercicios con Maxima
1. Escribe el nombre del paquete de Maxima que incorpora las funciones
relacionadas con Teoría de Grafos.
El paquete graphs permite trabajar con estructuras de grafos y
digrafos en Maxima.
2. Escribe las funciones de dicho paquete que:
Define y crea los grafos.
create_graph
Devuelve un ciclo de n vértices.
cycle_graph
Devuelve un camino de n vértices.
path_graph
Devuelve un árbol aleatorio de n vértices.
. random_tree
Determina si un grafo es conexo.
is_connected (Devuelve true si el grafo gr es conexo y false
en caso contrario)
Devuelve las componentes conexas de un grafo.
connected_components
Determina si un grafo es un árbol.
is_tree (Devuelve true si es un arbol y false en caso contrario)
Devuelve un árbol generador de un grafo.
min_edge_cut
Dibuja un grafo.
draw_graph
3. Utilizando Maxima:
Crea los grafos de los ejercicios del Rosen, pág. 509: 3, 4, 5, 7, 8.
Rosen, pág. 538: Ejercicios 3, 4, 5, 6.
Rosen, pág. 598-599: Ejercicio 1.
Obtén un árbol generador para cada uno los grafos de los ejercicios del
Rosen, pág. 638: 2, 3, 13.
/* [wxMaxima batch file version 1] [ DO NOT EDIT
BY HAND! ]*/
/* [ Created with wxMaxima version 0.8.6 ] */
/* [wxMaxima: input
load(graphs);
/* [wxMaxima: input
start ] */
end
] */
/* [wxMaxima: input
"EJERCICIO 3";
/* [wxMaxima: input
start ] */
end
] */
/* [wxMaxima: input start ] */
load(graphs)$
g:create_graph([1,2,3,4],
[[1,2],[2,3],[1,3],[2,4]])$
print_graph(g)$
draw_graphs(g);
/* [wxMaxima: input end ] */
/* [wxMaxima: input
"EJERCICIO 4";
/* [wxMaxima: input
start ] */
/* [wxMaxima: input
"EJERCICIO 5";
/* [wxMaxima: input
start ] */
/* [wxMaxima: input
"EJERCICIO 7";
/* [wxMaxima: input
start ] */
/* [wxMaxima: input
"EJERCICIO 8";
/* [wxMaxima: input
start ] */
end
end
end
end
] */
] */
] */
] */
/* [wxMaxima: input start ] */
"EJERCICIO 3 PAG 538";
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
load(graphs)$
g:create_graph([1,2,3], [[1,2],[2,3]])$
print_graph(g)$
is_connected(g);
/* [wxMaxima: input
end
] */
/* [wxMaxima: input start ] */
load(graphs)$
g:create_graph([1,2,3,4],[[1,4],[3,4]])$
print_graph(g)$
is_connected(g);
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
"EJERCICIO 4 PAG 538";
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
load(graphs)4
g:create_graph([1,2,3,4,5,6,7,8,9,10,11],[[1,2],[1,
3],[2,8],[3,7],[3,9],[4,8],[4,10],[5,9],[5,11],[6,10]
])$
print_graph(g)$
is_connected(g);
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
"EJERCICIO 5 PAG 538";
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
load(graphs)$
g:create_graph([1,2,3,4,5,6],[[1,5],[1,3],[2,6],[2,4
],[3,5],[4,6]])$
print_graph(g)$
is_connected(g);
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
"EJERCICIO 6 PAG 538";
/* [wxMaxima: input end ] */
/* [wxMaxima: input
"3";
/* [wxMaxima: input
start ] */
end
] */
/* [wxMaxima: input start ] */
load(graphs)$
g:create_graph([1,2,3], [[1,2],[2,3]])$
print_graph(g)$
connected_components(g);
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
load(graphs)$
g:create_graph([1,2,3,4],[[1,4],[3,4]])$
print_graph(g)$
connected_components(g);
/* [wxMaxima: input end ] */
/* [wxMaxima: input
"4";
/* [wxMaxima: input
start ] */
end
] */
/* [wxMaxima: input start ] */
load(graphs)4
g:create_graph([1,2,3,4,5,6,7,8,9,10,11],[[1,2],[1,
3],[2,8],[3,7],[3,9],[4,8],[4,10],[5,9],[5,11],[6,10]
])$
print_graph(g)$
connected_components(g);
/* [wxMaxima: input end ] */
/* [wxMaxima: input
start ] */
"5";
/* [wxMaxima: input
end
] */
/* [wxMaxima: input start ] */
load(graphs)$
g:create_graph([1,2,3,4,5,6],[[1,5],[1,3],[2,6],[2,4
],[3,5],[4,6]])$
print_graph(g)$
connected_components(g);
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
"EJERCICIO 1 pag 598";
/* [wxMaxima: input end ] */
/* [wxMaxima: input
"a";
/* [wxMaxima: input
start ] */
end
/* [wxMaxima: input
start ] */
] */
load(graphs)$
g:create_graph([1,2,3,4,5,6],[[1,4],[2,4],[2,5],[3,5
],[3,6]])$
print_graph(g)$
is_tree(g);
/* [wxMaxima: input end ] */
/* [wxMaxima: input
"b";
/* [wxMaxima: input
start ] */
end
] */
/* [wxMaxima: input start ] */
load(graphs)$
g:create_graph([1,2,3,4,5,6],[[1,4],[2,4],[3,5],[3,6
]])$
print_graph(g)$
is_tree(g);
/* [wxMaxima: input
/* [wxMaxima: input
"c";
/* [wxMaxima: input
end
] */
start ] */
end
] */
/* [wxMaxima: input start ] */
load(graphs)$
g:create_graph([1,2,3,4,5,6],[[1,4],[2,5],[2,3],[3,6
],[4,5]])$
print_graph(g)$
is_tree(g);
/* [wxMaxima: input end ] */
/* [wxMaxima: input
"d";
/* [wxMaxima: input
start ] */
end
] */
/* [wxMaxima: input start ] */
load(graphs)$
g:create_graph([1,2,3,4,5,6],[[1,4],[2,4],[2,5],[3,5
],[3,6],[4,5]])$
print_graph(g)$
is_tree(g);
/* [wxMaxima: input end ] */
/* [wxMaxima: input
"e";
/* [wxMaxima: input
start ] */
end
] */
/* [wxMaxima: input start ] */
load(graphs)$
g:create_graph([1,2,3,4,5,6,7],[[1,4],[2,4],[3,4],[5
,4],[6,4],[7,4]])$
print_graph(g)$
is_tree(g);
/* [wxMaxima: input
/* [wxMaxima: input
"f";
/* [wxMaxima: input
end
] */
start ] */
end
] */
/* [wxMaxima: input start ] */
load(graphs)$
g:create_graph([1,2,3,4,5,6],[[1,4],[1,6],[2,4],[2,5
],[3,5],[3,6]])$
print_graph(g)$
is_tree(g);
/* [wxMaxima: input end ] */
/* Maxima can't load/batch files which end with a
comment! */
"Created with wxMaxima"$
5. Explicación del modelo ilustrada con un ejemplo
Conceptos previos.

El grafo de red. ”La Red de Internet se puede representar por
medio de un grafo dirigido en el que cada página web está
representada por un vértice y en el que una arista comienza
en la página a y termina en la b si hay un enlace en la página
a que conduce a la b.[…]” 6
a
b

Ejemplo de un grafo de red
Arañas web. “Para indexar los sitios de la red de Internet,
buscadores como Google, Hotbot y Lycos exploran
sistemáticamente la Red comenzando en sitios conocidos.
Estos buscadores utilizar los contenidos. Las arañas web
utilizan tanto la búsqueda en anchura como en profundidad
para crear índices. […]” 7
Otra definición. “Una araña web (o araña de la web) es un programa
que inspecciona las páginas del World Wide Web de forma metódica y
automatizada. Uno de los usos más frecuentes que se les da consiste
en crear una copia de todas las páginas web visitadas para su
procesado posterior por un motor de búsqueda que indexa las
páginas proporcionando un sistema de búsquedas rápido. Las arañas
web suelen ser bots (el tipo más usado de éstos).
Las arañas web comienzan visitando una lista de URL’s, identifica los
hiperenlaces en dichas páginas y los añade a la lista de URL’s a visitar
de manera recurrente de acuerdo a determinado conjunto de reglas.
6
7
Rosen, Kenneth H. Matemática discreta y sus aplicaciones, página 508.
Rosen, Kenneth H. Matemática discreta y sus aplicaciones, página 637.
La operación normal es que se le da al programa un grupo de
direcciones iniciales, la araña descarga estas direcciones, analiza las
páginas y busca enlaces a páginas nuevas. Luego descarga estas
páginas nuevas, analiza sus enlaces, y así sucesivamente.”8
Ejemplo de búsqueda en profundidad en un grafo dirigido.
Partiendo del siguiente grafo explicaremos una búsqueda en
9
profundidad :
a
b
c
f
g
e
d
h
j
i
k
l
Elegimos empezar por el vértice a para mantener un orden alfabético,
podría empezarse por cualquier vértice del árbol en este caso, en otro
árbol en el que la raíz fuera más clara debería ser el vértice raíz el
primero.
Siguiendo las aristas dirigidas de a nos encontramos con los
siguientes caminos: 1) (a,b,c,g) y (a,b,f,e) lo que nos da como
resultado el siguiente árbol:
a
b
8
9
c
f
g
e
De a la arista dirigida nos lleva a b,
de b, tenemos dos caminos,
escogemos primero por orden
alfabético ir a c y de este vértice a g;
como no tenemos más caminos,
volvemos a b y continuamos de b a f
y de f a e. Nuevamente no tenemos
por donde seguir. Esta parte está
completa.
http://es.wikipedia.org/wiki/Ara%C3%B1a_web
Rosen, Kenneth H. Matemática discreta y sus aplicaciones, página 632.
Ahora elegimos el vértice d, nuevamente por orden alfabético para
continuar nuestra búsqueda. El camino resultante es (d,h,l,k,j).
d
h
Esta vez es mucho más sencillo
encontrar el camino, de d a h, de h
a l, de l a k y de k a j.
l
k
j
j
El único vértice no recogido por nuestros dos árboles es i, para este
resultado de una búsqueda los árboles son los mostrados; una
búsqueda que comenzara en otro vértice daría lugar a otros árboles.
6. Ejercicios propuestos sobre el tema
1.- De que tipo son los siguientes grafos.
a)
e)
A
B
b)
f)
C
D
E
R
T
Y
c)
g)
a
d)
b
c
f
g
d
h)
e
h
j
i
k
l
2.- Partiendo del siguiente árbol indica:
a
c
b
e
d
f
g
i
h
j
a) ¿Cuál es el vértice raíz?
b) ¿Qué vértices son hojas?
c) ¿Qué vértices son hijos de b?
d) ¿Qué vértice es padre de d?
e) ¿Cuáles son hermanos de e?
f) ¿Qué vértices son los antecesores de j?
g) ¿Cuáles son los posibles caminos de árbol?
3.- En un juego de ordenador en 2D, los usuarios gestionan una
ciudad, diseñando y estructurando sus recursos e infraestructuras.
Un amigo nuestro que juega a ese juego se ha encontrado con un
problema que no consigue solucionar, tiene que enviar agua, luz y
gas a seis viviendas desde las distintas estaciones que se la
proporcionan pero no encuentra la manera de hacerlo. ¿Serías
capaz de ayudarle teniendo en cuenta que el mundo es un plano y
por lo tanto las tuberías y los cables no se pueden cruzar?
Luz
Agua
Gas
0
1
2
3
4
5
7. Bibliografía







Rosen, Kenneth H. Matemática discreta y sus aplicaciones. Edición 5ª .
McGraw-Hill, 2004 (Hay varios ejemplares disponibles en la biblioteca del
Campus).
García Merayo, Félix Matemática discreta. Edición 2ª ed. Paraninfo, D.L.
2005.
Kolman, Bernard Estructuras de matemáticas discretas para la
computación. Edición 3ª. Prentice Hall, 1997.
Apuntes de Matemática Discreta de la Facultad de informática de Coruña
(2006-2007)
Poli Abascal Fuentes, Teoría de Grafos.
http://enol.epsig.uniovi.es/matdisc/materiales/trgrafosalu.pdf
Introducción a la Teoría de Grafos de Reinaldo Giudici Espinoza y
Angeles Bris Lluch, editorial Equinoccio, Universidad Simón Bolívar,
Caracas, Venezuela, 1997. http://teoriadegrafos.blogspot.com/
Un ejemplo de búsqueda en profundidad en grafos no dirigidos:
http://translate.google.es/translate?hl=es&langpair=en|es&u=http://en.wi
kipedia.org/wiki/Depth-first_search