Borrachera 2006
Marina Groshaus
Borrachera 2006
Somos mucho
ue dos
Como organizar “fiestitas ” usando
teoría de grafos……
Marina Groshaus
Director: Jayme Szwarcfiter
Borrachera 2006
Mini clase de anatomia:
Atracción: Definición universal:
Fís. La que ejercen entre sí los
cuerpos que componen el universo, principalmente los astros, y que
depende de sus masas y distancias respectivas.
Borrachera 2006
Problema
• Había una vez, un grupo de
personas. Llamaron a Cupido para
armar parejas…
Borrachera 2006
Problema
• Había una vez, un grupo de
personas. Llamaron a Cupido para
armar parejas…
• Resulta que se equivocaron y
enviaron a Diablido
Borrachera 2006
• Maria gustaba de Juan y de Pepe,
• Pepe, quería estar con Maria, Josefa, y Anastasia
• Anastasia,… y si, le gustaban
Borrachera 2006
• Maria gustaba de Juan y de Pepe,
• Pepe, quería estar con Maria, Josefa, y Anastasia
• Anastasia,… y si, le gustaban
Y así es donde entra el tema que nos convoca hoy, “las
partuzas”
Borrachera 2006
• Maria gustaba de Juan y de Pepe,
• Pepe, quería estar con Maria, Josefa, y Anastasia
• Anastasia,… y si, le gustaban
Y así es donde entra el tema que nos convoca hoy, “las
fiestitas”
Borrachera 2006
• Maria gustaba de Juan y de Pepe,
• Pepe, quería estar con Maria, Josefa, y Anastasia
• Anastasia,… y si, le gustaban
Y así es donde entra el tema que nos convoca hoy, “los
grafos”
Borrachera 2006
Lo modelamos con un grafo...
Un grafo es un conjunto de puntos, o vértices, y
un conjunto de aristas que unen algunos
vértices. Podemos pensar a estas aristas como
una “relación “ entre los vértices. Cuando dos
vertices se relacionan, decimos que son
adyacentes.
Borrachera 2006
Lo modelamos con un grafo...
Un grafo es un conjunto de puntos, o vértices, y
una conjunto de aristas que unen algunos
vértices. Podemos pensar a estas aristas como
una “relación “ entre los vértices. Cuando dos
vértices se relacionan, decimos que son
adyacentes.
* Para nuestro modelo, vamos a suponer por un
momento, que tenemos un grupo heterosexual.
* Vamos a suponer también, que vivimos en un mundo
ideal, en el cual si Maria quiere estar con Juan, Juan
quiere estar con Maria!!!
Borrachera 2006
Modelo: bipartito =heterosexual
Borrachera 2006
Looser =
vértice aislado
No importa, Linux
me quiere, he he
Borrachera 2006
… = vértice universal
Pero yo busco el amor….
Borrachera 2006
Condiciones para una “FIESTITA” :
Borrachera 2006
Condiciones para una “FIESTITA” :
• Todos los participantes de distintos
sexos “se gustan”
Borrachera 2006
Condiciones para una “FIESTITA” :
• Todos los participantes de distintos
sexos “se gustan”
• Cuanto más gente pueda participar
mejor !!!!!!!!!!!!!!
Borrachera 2006
“FIESTITA” = BICLIQUE
• Todos los participantes de distintos sexos
“se gustan”
Interpretado
en el grafo
• Todos los vértices de distintas particiones
“son adyacentes”, es decir, es bipartito
completo
Borrachera 2006
“FIESTITA” = BICLIQUE
• Cuanto más gente pueda participar
mejor !!!!
Interpretado
en el grafo
• Es un conjunto maximal, en el sentido
que al agregar cualquier otro vértice no
cumple la condición anterior
Borrachera 2006
“FIESTITA” = BICLIQUE
Una biclique de un grafo es un subgrafo
inducido bipartito completo
maximal
Bipartito Completo: Todos los vértices de
distintas particiones “son adyacentes”
Maximal : Si se agrega otro vértice, no es completo
Borrachera 2006
Ejemplo: Grafo bipartito
Borrachera 2006
Ejemplo:
Bicliques:
Borrachera 2006
Ejemplo:
Bicliques:
Borrachera 2006
Ejemplo:
Bicliques:
Borrachera 2006
Ejemplo:
Bicliques:
Borrachera 2006
Ejemplo:
Bicliques:
Borrachera 2006
Ejemplo:
Bicliques:
Borrachera 2006
Ejemplo:
Bicliques:
Borrachera 2006
Preguntas que podemos hacer:
Borrachera 2006
Preguntas que podemos hacer:
* Cuántas “fiestitas” podemos
organizar
* Cual es la “fiestita” más grande
que podemos organizar
* A cuántas “fiestitas” va Pepe
* Quién es el mas fiestero
Borrachera 2006
Preguntas que podemos hacer:
* Número de bicliques contiene el
grafo
* Tamaño de la biclique máxima
* Cantidad de bicliques a las que
pertenece un vértice v: mb (v)
* Máximo número de bicliques que
tienen un vértice en común:Mb(G)=
max mb (v)
v
Borrachera 2006
Ejemplo:
Bicliques:
Biclique máxima:
Borrachera 2006
Ejemplo:
Bicliques:
Biclique máxima:
Mb(G), Más fiestero:
Borrachera 2006
Ejemplo:
Bicliques:
Biclique máxima:
Mb(G), Más fiestero:
Borrachera 2006
Ejemplo:
Bicliques:
Biclique máxima:
Mb(G)=3, Más fiestero:
Borrachera 2006
Problemas en grafos:
* Número de bicliques contiene el grafo
Resultado bipartitos: 2n/2 (Prisner, 2000)
*Tamaño de la biclique máxima: Resultado,
bipartitos: Polinomial
caso general: NP-completo
* Cantidad de bicliques a las que
pertenece un vértice v: mb (v). (Polinomial
en mb(v))
* Máximo número de bicliques que tienen
un vértice en común:Mb(G)= max mb (v)
v
Borrachera 2006
Listo. Ahora, tenemos que llevar a cabo
nuestro experimento:
• Cada fiestita se realiza durante todo un día
(…sin comentarios…)
Borrachera 2006
Listo. Ahora, tenemos que llevar a cabo
nuestro experimento:
• Cada fiestita se realiza durante todo un día
(…sin comentarios…)
• Contratamos un lugar, que nos cobra por día
Borrachera 2006
Listo. Ahora, tenemos que llevar a cabo
nuestro experimento:
• Cada fiestita se realiza durante todo un día
(…sin comentarios…)
• Contratamos un lugar, que nos cobra por día
• El lugar dispone de muuuchos “salones”, es
decir, ésta no es una restricción
Borrachera 2006
Cuántos días debemos contratar el lugar?
(dos fiestitas que comparten una persona, no
pueden desarrollarse a la vez)
2) Hay alguien que está “ocupado” durante TODO
el experimento?
1)
Borrachera 2006
Cuantas días debemos contratar el lugar?
(dos fiestitas que comparten una persona,
no pueden desarrollarse a la vez)
2) Hay alguien que está “ocupado” durante
todo el experimento?
1)
1) Partición mínima de bicliques en conjuntos
de bicliques independientes Fb(G)
2) Siempre vale que Mb(G) ≤ Fb(G).
Es cierto que Mb(G) = Fb(G) ?
Borrachera 2006
Ejemplo
Borrachera 2006
Todas se intersecan, por lo tanto deben ir a
conjuntos diferentes
Borrachera 2006
Todas se intersecan, por lo tanto deben ir a
conjuntos diferentes
Lunes
Miércoles
Martes
Jueves
Fb=5, Mb =4
Viernes
Borrachera 2006
Top Secret
• En una de estas reuniones, Pedro, uno de
los participantes, cuenta un secreto
propio.
Borrachera 2006
Top Secret
• En una de estas reuniones, Pedro, uno de
los participantes, cuenta un secreto
propio.
•
Al cabo de unos días, este secreto se
había esparcido entre todas las personas
del grupo !(bueno, no, el looser no lo
sabia…)
Borrachera 2006
Top Secret
• En una de estas reuniones, Pedro, uno de
los participantes, cuenta un secreto
propio.
•
Al cabo de unos días, este secreto se
había esparcido entre todas las personas
del grupo !(bueno, no, el looser no lo
sabia…)
Borrachera 2006
Top Secret
• En una de estas reuniones, Pedro, uno de
los participantes, cuenta un secreto
propio.
•
Al cabo de unos días, este secreto se
había esparcido entre todas las personas
del grupo !(bueno, no, el looser no lo
sabia…)
Borrachera 2006
Top Secret
• En una de estas reuniones, Pedro, uno de
los participantes, cuenta un secreto
propio.
•
Al cabo de unas días, este secreto se
había esparcido entre todas las personas
del grupo !(bueno, no, el looser no lo
sabia…)
Borrachera 2006
Top Secret
• En una de estas reuniones, Pedro, uno de
los participantes, cuenta un secreto
propio.
•
Al cabo de unas horas, este secreto se
había esparcido entre todas las personas
del grupo !(bueno, no, el looser no lo
sabia…)
• Queremos que saber si hay soplones, o es
el mismo Pedrito que lo anda contando en
todas sus fiestitas.
Borrachera 2006
- Todo par de fiestitas, tiene un integrante en común.
Esto implica que todas tenían a Pedro?
Borrachera 2006
- Todo par de fiestitas, tiene un integrante en común.
Esto implica que todas tenían a Pedro?
Borrachera 2006
- Todo par de fiestitas, tiene un integrante en común.
Esto implica que todas tenían a Pedro?
Borrachera 2006
- Todo
par de fiestitas, tiene un integrante en común.
Esto implica que todas tenían a Pedro?
Borrachera 2006
- Todo
par de fiestitas, tiene un integrante en común.
Esto implica que todas tenían a Pedrito?
Esta propiedad, es la propiedad de Helly :
Toda subfamilia de conjuntos que se
interseca dos a dos, tiene intersección total
no vacía.
Borrachera 2006
- Todo
par de fiestitas, tiene un integrante en común.
Esto implica que todas tenían a Pedrito?
Pedrito
Problema: Dado un grafo G, es G bicliqueHelly? Polinomial
Borrachera 2006
Grafo de intersección de fiestitas =
Grafo Biclique
• Por cada biclique, ponemos un vértice, y decimos
que dos bicliques se relacionan si las bicliques
tienen un vértice en común:
• Esta construcción genera un grafo que contiene la
información de cómo están relacionadas las
bicliques, en este caso, las fiestitas, entonces, por
ejemplo, podemos buscar “caminos” entre dos
fiestitas, para pasar un mensaje:
Borrachera 2006
Grafo Biclique
Borrachera 2006
Grafo Biclique
Shh, no se lo
digas a
nadie..
Borrachera 2006
Grafo Biclique
Te lo digo a
vos pero a
nadie más
Borrachera 2006
Grafo Biclique
Te lo cuento porque confío
en vos, pero shh
Borrachera 2006
Grafo Biclique
Quéeeeee!!!!
Borrachera 2006
No está buena?
Borrachera 2006
Mundo Bisexual
Borrachera 2006
Mundo Bisexual
Borrachera 2006
Mundo Bisexual
Borrachera 2006
Mundo Bisexual
Borrachera 2006
Mundo Bisexual
Borrachera 2006
Mundo Bisexual
Borrachera 2006
Nos olvidamos de las fiestas por un rato…
Las bicliques también aparecen en
•
•
•
•
Teoría de autómatas
Teoría de lenguajes
Inteligencia artificial
Biología.
Borrachera 2006
Otros problemas en grafos:
•
•
•
•
Coloreo
Partición de Cliques (Otra que “fiestita”)
Matching (Armado de parejas)
Camino mínimo
Grafos de interseción:
- De intervalos,
- de cliques,
- de cuerdas en un círculo,
Borrachera 2006
Los nombres/personajes que
aparecen en esta presentación
son ficticios.
Cualquier similitud con la
realidad, es pura coincidencia
Borrachera 2006
Ventajas de trabajar en grafos…
Mi lugar de trabajo
Borrachera 2006
Descargar

bajar ppt - Universidad de Buenos Aires