Convergencia y divergencia del grafo biclique iterado
Dado un grafo G, una clique de G es un subgrafo inducido completo maximal, mientras que una biclique de G es un subgrafo inducido bipartito completo maximal de G. El estudio de las bicliques resulta de interés debido a las diferentes aplicaciones en áreas distintas como genética, biología, el estudi...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Tesis de grado publishedVersion |
| Lenguaje: | Español |
| Publicado: |
Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
2008
|
| Acceso en línea: | https://hdl.handle.net/20.500.12110/seminario_nCOM000340_Montero |
| Aporte de: |
| Sumario: | Dado un grafo G, una clique de G es un subgrafo inducido completo maximal, mientras que una biclique de G es un subgrafo inducido bipartito completo maximal de G. El estudio de las bicliques resulta de interés debido a las diferentes aplicaciones en áreas distintas como genética, biología, el estudio de redes sociales, inteligencia artificial, etc. Por otro lado, tiene interés a nivel teórico, ya que están estrechamente relacionadas con temas profundamente estudiados como los grafos discos-Helly y los retractos. Dada una familia de conjuntos H, el grafo de intersección de H es el grafo que contiene como conjunto de vértices a los conjuntos de H, y existe una arista entre dos conjuntos E; F ∈ H cuando E y F se intersecan. Los grafos de intersección fueron estudiados en la literatura. Cabe mencionar a los grafos de intervalos (donde H es una familia de intervalos) y al grafo línea (donde H es la familia de aristas de G), entre otros. El grafo clique de G, denotado por K(G), es el grafo de intersección de la familia de cliques de G. Existe un teorema de reconocimiento de grafos clique dado por Roberts y Spencer, pero este no conduce a un algoritmo eficiente para el reconocimiento de dicha clase. En el 2002, se probó que el problema de reconocimiento de grafos clique es NP-completo, es decir, no existe un algoritmo polinomial para resolver este problema (si P 6 ≠ NP). Pensando al grafo clique como un operador, el grafo clique iterado k៱k (G) es el grafo que resulta de aplicar k veces el operador ”grafo clique" al grafo G. El grafo clique iterado fue estudiado ampliamente y pese a no haberse encontrado una caracterización de su comportamiento para un grafo general, se han presentado resultados restringidos a ciertas clases. El grafo biclique de G, KB(G), es el grafo de intersección de las bicliques de G. Este fue definido y caracterizado recientemente. Sin embargo, aún sigue abierta la pregunta sobre la existencia de un algoritmo eficiente que resuelva el problema de reconocimiento de grafos biclique. En este trabajo estudiamos el operador “grafo biclique". Probamos que los únicos posibles comportamientos del grafo biclique iterado son la convergencia y la divergencia, y caracterizamos cada uno de estos. En particular, probamos que un grafo diverge si y solo sí KB(G) contiene a una gema, una casa o k_5 como subgrafos inducidos. Por otro lado, utilizando esta caracterización, presentamos un algoritmo polinomial que resuelve el problema de decidir el comportamiento de un grafo bajo el operador biclique. |
|---|