Conocimiento

¿Qu´ es un grafo?
e
Ejemplos de la vida real
Grafos Perfectos
Grafos clique-perfectos

Pintar mapas, organizar fiestas... en el fondo, es
s´lo teor´ de grafos
o
ıa
Flavia Bonomo
Grupo de Teor´ de Grafos
ıa
Departamento de Computaci´n
o
FCEyN - UBA

Charla de Borrachos
Noviembre 2004

Flavia Bonomo

Pintar mapas, organizar fiestas...

teor´ de grafos
ıa

¿Qu´ es un grafo?e
Ejemplos de la vida real
Grafos Perfectos
Grafos clique-perfectos

¿Qu´ es un grafo?
e
Un grafo est´ formado por un conjunto de v´rtices y un
a
e
conjunto de aristas que unen pares de v´rtices.
e

Es un objeto matem´tico abstracto pero se usa para modelar
a
problemas reales.
Flavia Bonomo

Pintar mapas, organizar fiestas...

teor´ de grafos
ıa

¿Qu´ es un grafo?
eEjemplos de la vida real
Grafos Perfectos
Grafos clique-perfectos

Seg´n el problema que uno quiera modelar, uno puede permitir
u
aristas que unan un v´rtice con si mismo (pseudografo) o m´s de
e
a
una arista que una el mismo par de v´rtices (multigrafo).
e

Flavia Bonomo

Pintar mapas, organizar fiestas...

teor´ de grafos
ıa

¿Qu´ es un grafo?
e
Ejemplos de la vida real
GrafosPerfectos
Grafos clique-perfectos

O tambi´n puede necesitar un hipergrafo, donde las aristas no
e
involucran 2 v´rtices sino que son subconjuntos no vac´ de
e
ıos
v´rtices (de cualquier cardinalidad).
e

Flavia Bonomo

Pintar mapas, organizar fiestas...

teor´ de grafos
ıa

¿Qu´ es un grafo?
e
Ejemplos de la vida real
Grafos Perfectos
Grafos clique-perfectos

Rutasargentinas
Eligiendo novio... ♥
C´mo organizar una fiesta
o

Rutas argentinas

Flavia Bonomo

Pintar mapas, organizar fiestas...

teor´ de grafos
ıa

¿Qu´ es un grafo?
e
Ejemplos de la vida real
Grafos Perfectos
Grafos clique-perfectos

Rutas argentinas
Eligiendo novio... ♥
C´mo organizar una fiesta
o

Rutas argentinas
Si nos quedamos con el “subgrafo inducido” por Buenos Aires,R´
ıo
Negro, La Pampa y Neuqu´n, podemos buscar ahi el camino
e
m´
ınimo entre Buenos Aires y Bariloche.
5
205
2
152

33

226

22

237
23

Flavia Bonomo

Pintar mapas, organizar fiestas...

teor´ de grafos
ıa

¿Qu´ es un grafo?
e
Ejemplos de la vida real
Grafos Perfectos
Grafos clique-perfectos

Rutas argentinas
Eligiendo novio... ♥
C´mo organizar una fiesta
oEligiendo novio... ♥

Flavia Bonomo

Pintar mapas, organizar fiestas...

teor´ de grafos
ıa

¿Qu´ es un grafo?
e
Ejemplos de la vida real
Grafos Perfectos
Grafos clique-perfectos

Rutas argentinas
Eligiendo novio... ♥
C´mo organizar una fiesta
o

Eligiendo novio... ♥

Flavia Bonomo

Pintar mapas, organizar fiestas...

teor´ de grafos
ıa

¿Qu´ es un grafo?
e
Ejemplos dela vida real
Grafos Perfectos
Grafos clique-perfectos

Rutas argentinas
Eligiendo novio... ♥
C´mo organizar una fiesta
o

Eligiendo novio... ♥

G

Flavia Bonomo

Pintar mapas, organizar fiestas...

teor´ de grafos
ıa

¿Qu´ es un grafo?
e
Ejemplos de la vida real
Grafos Perfectos
Grafos clique-perfectos

Rutas argentinas
Eligiendo novio... ♥
C´mo organizar una fiesta
oEligiendo novio... ♥

G

Flavia Bonomo

Pintar mapas, organizar fiestas...

teor´ de grafos
ıa

¿Qu´ es un grafo?
e
Ejemplos de la vida real
Grafos Perfectos
Grafos clique-perfectos

Rutas argentinas
Eligiendo novio... ♥
C´mo organizar una fiesta
o

Eligiendo novio... ♥

G
Lo que buscamos es un conjunto independiente m´ximo en el grafo
a
G . El cardinal de ese conjuntose nota α(G ).
Flavia Bonomo

Pintar mapas, organizar fiestas...

teor´ de grafos
ıa

¿Qu´ es un grafo?
e
Ejemplos de la vida real
Grafos Perfectos
Grafos clique-perfectos

Rutas argentinas
Eligiendo novio... ♥
C´mo organizar una fiesta
o

C´mo organizar una fiesta
o
Queremos organizar varias reuniones invitando a cada una gente
que se conozca entre si. ¿Cu´l es la m´
a...