UNIVERSIDAD NUR
INGENIERIA DE SISTEMAS
ALGEBRA DISCRETA
INTRODUCCION A LOS GRAFOS
Docente: Ing. Nancy Quiroga Perez
Grupo: #1
Integrantes:
Gerardo Coronado Becerra (jefe de grupo)
Leonardo Ronald Soliz Padilla
Ricardo Guillen Bejarano
Willy Soruco Vargas
Frase Clebre: Si quieres ser exitoso tienes que respetar una
regla:
Nunca Te mientas a ti mismo by: Paulo Coelho.
Santa Cruz Bolivia
GRUPO #7
INTRODUCCION A LOS GRAFOS
En matemticas y ciencias de la computacin, un grafo (del griego
grafos: dibujo, imagen) o grfica es el principal objeto de estudio de la
teora de grafos.
un grafo es un conjunto de objetos llamados vrtices o nodos unidos por
enlaces llamados aristas o arcos, que permiten representar relaciones
binarias entre elementos de un conjunto.
Un grafo se representa grficamente como un conjunto de puntos
(vrtices o nodos) unidos por lneas (aristas).
Aristas o
arcos
Vrtice o
Nodo
Un grafo consta de dos cosas:
Un conjunto N cuyos elementos se llaman nodos, puntos o
vrtices.
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}
EJEMPLO:
El siguiente G consta de cuatro vrtices, A, B, C y D, y cinco
segmentos s1 = {A, B},
s2 = {B, C}, s3 = {C, D}, s4 = {A, C}, s5 = {B, D}.
TIPOS DE GRAFOS
GRAFO SIMPLE:
Un grafo simple G = ( V , E ) consta de:
V un conjunto no vaco de VRTICES.
E un conjunto de pares no ordenados de ELEMENTOS distintos de V.
A estos pares se les llama ARISTAS
MULTIGRAFO:
Un multigrafo G = (V, A) consta de un conjunto V de vrtices, un
conjunto A de aristas y una funcin f de A hacia {{u, v} | u, v
pertenecen a V, u es diferente de v}.
Se dice que las aristas a1 y a2 son aristas mltiples o paralelas si f
(a1) = f (a2).
PSEUDOGRAFO:
Un pseudografo G = (V, A) consta de un conjunto V de vrtices, un
conjunto A de aristas y una funcin f de A hacia {{u, v} | u, v
pertenece a V}. Una arista a es un bucle o lazo, si f(a) = {u; u} =
{u} para algn u pertenece a V.
GRAFO DIRIGIDO:
Un grafo dirigido G, tambin llamado digrafo, es lo mismo que un
multigrafo, solo que cada arista e de G tiene una direccin
asignada o, en otras palabras, cada arista e est identificada por
un par ordenado (u, v) de nodos G en vez del par desordenado [u.
v]. Un grafo dirigido (V, A) consta de un conjunto V de vrtices y
de un conjunto A de aristas, que son pares ordenados de
elementos de V. Utilizamos el par ordenado u , v para indicar
que es una arista dirigida del vrtice u al vrtice v.
V={a, b, c, d}
A={ (a,c) , (a,b) , (b,c) ,
(b,d) , (c,d) }
MULTIGRAFO DIRIGIDO:
Un multigrafo dirigido G = (V, A) consta de un conjunto V de
vrtices, un conjunto A de aristas y una funcin f de A hacia { u ,
v | u, v V }.
Se dice que las aristas a1 y a2 son aristas mltiples o paralelas si f
(a1) = f (a2).
MODELOS CON GRAFOS:
GRAFOS DE SOLAPAMIENTO DE NICHOS EN ECOLOGIA
Los grafos se emplean en muchos modelos que tienen que ver con las
interacciones entre especies animales distintas.
Por ejemplo, la competicin entre especies en un ecosistema puede
representarse mediante un grafo de solapamiento de nichos.
Cada especie se represente por un vrtice. Una arista no dirigida
conecta dos vrtices si las dos especies representadas por esos vrtices
compiten entre s (esto es, si algina de las fuentes de alimento de las
que se nutren son las mismas).
GRAFOS DE CONOCIDOS:
Podemos usar modelos de grafos para representar relaciones entre
personas. Por ejemplo usar un grafo para representar el hecho de que
dos personas se conozcan. Cada persona de un grupo concreto se
representa mediante un vrtice. Se utiliza una arista no dirigida para
conectar dos personas cuando esas dos personas se conocen.
HUMBERTO
STERLING
WILLY
CHAPU
ROCIO
DENNAR
STIFF
HIKARI
POTTER
LEO
I
RICARDO
FRANCHESCO
GONZALO
ENRIQUE
CARLOS
LUDVING
GRAFO DE INFLUENCIA:
Se ha observado en estudios del comportamiento de grupos que ciertas
personas pueden influir en la forma en que piensan otras personas,
pueden usarse un grafo dirigido, llamado grafo de influencia, para
representar este comportamiento. Cada persona del grupo se representa
por un vrtice. Hay una arista dirigida del vrtice A al vrtice B.
GRAFO DE HOLLYWOOD:
Representa a los actores como vrtices y conecta dos vrtices si los
actores representados por dichos vrtices han trabajado juntos en
alguna pelcula. Segn el internet Movie Data base, en noviembre del
2001 el grafo de Hollywood tena 574.724 vrtices que representaban a
actores que haban aparecido en 292.609 pelculas y tenan ms de 16
millones de artistas.
Chole Grace
Selena Gmez
Zac Efron
Seth Rogen
Rose Byme
Cameron Dallas
Dave Franco
TORNEOS DE TODOS CONTRA TODOS:
Un torneo en el que cada equipo se enfrenta exactamente una vez a
cada uno de los restantes se llama torneos de todos contra todos. Estos
torneos se pueden representar usando grafos dirigidos en los que cada
equipo se representan mediante un vrtice. (Ntese que A, B) es una
arista si el equipo A vence al equipo B.
GRAFO DE COLABORACION:
Sirve para modelar la coautora de artculos acadmicos. En un grafo de
colaboracin los vrtices representan personas (restringidas, quizs, a
una cierta comunidad cientfica) y una arista conecta a dos personas si
estas han escrito conjuntamente un artculo. Se ha estimado que el
grafo de colaboracin de las personas que colaboran en artculos de
investigacin matemticas tiene ms de 337.000 vrtices y 496.000
aristas.
GRAFO DE LLAMADAS:
Los grafos se pueden utilizar para representar las llamadas telefnicas
hechas en una red, por ejemplo en una red telefnica de larga distancia.
En particular, puede usarse un multigrado dirigido para representar
llamadas: cada vrtice representa un nmero de telfono y cada arista
representa una llamada. La arista que representa una llamada sale del
nmero de telfono desde el que se hace la llamada y llega al nmero
de telfono que la recibe.
EL GRAFO DE LA RED:
La red de internet (World Wide Web) se puede representar por medio de
un grafo dirigido en el que cada pgina web est representada por un
vrtice y en el que una arista comienza en la pgina a y termina en la
pgina b si hay un enlace en la pgina a que conduce a la pgina b.
GRAFO DE PRECEDENCIA Y PROCESAMIENTO CONCURRENTE:
Los programas informticos pueden ejecutarse ms rpido si ciertas
sentencias se ejecutan simultneamente. Es importante no ejecutar
sentencias que requieran el resultado de sentencias aun no ejecutadas.
PROBLEMAS:
Determinar si el grafo que se muestra es un grafo simple, un multigrafo
(y no un grafo simple), un pseudografo (y no un multigrafo), un grafo
dirigido y no un multigrafo(y no un grafo dirigido).
