Resumen:
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.
Abstract:
Given a graph G, a clique of G is a maximal complete induced subgraph, while a biclique of G is a maximal bipartite complete induced subgraph. The study of bicliques becomes interesting because of the possible different applications in several areas, such as genetics, biology, social networks, artificial intelligence, etc. Besides they have theoretical interest because of their relationship with some very deeply studied subjects, such as Helly disks and retracts. Given a family of sets H, the intersection graph of H is the graph that has the members of H as vertices, and there is an edge between two sets E; F ∈ H when E and F have non-empty intersection. Intersection graphs have been widely studied in the literature.We can mention as examples,interval graphs (where H is a family of intervales) and line graphs (where H is the family of edges of G), among others. The clique graph of G, denoted by K(G), is the interection graph of the family of cliques of G. There exists a characterization theorem for the clique graphs given by Roberts and Spencer. However, it does not lead to an efficient algorithm for the recognition problem. In 2002, it was proved that the recognition problem for clique graph is NP-Complete. In other words, there is no polynomial algorithm to solve this problem (if P 6≠NP). Considering the clique graph as an operator, the iterated clique graph k៱k (G) is the graph that results of applying k times the \\clique operator" to G. The iterated clique graph has been widely studied. There is no characterization of its behaviour for a general graph, but there are results restricted to some classes. The biclique graph of G, KB(G), is the intersection graph of the bicliques of G. This graph was recently defined and characterized. However, the question of the existence of an efficient algorithm for the recognition of biclique graphs is still an open problem. In this work we study the \\biclique graph" operator. We prove that there are only two possible behaviours of the iterated biclique graph: divergence and convergence, and we characterize each of them. In particular, we prove that a graph diverges if and only if KB(G) contains a gem, a house or K_5 as induced subgraphs. Furthermore, this characterization helped us to derive an algorithm that solves the problem of deciding the behaviour of a graph under the biclique operator in polynomial time.
Citación:
---------- APA ----------
Montero, Leandro P.. (2008). Convergencia y divergencia del grafo biclique iterado. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000340_Montero
---------- CHICAGO ----------
Montero, Leandro P.. "Convergencia y divergencia del grafo biclique iterado". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2008.https://hdl.handle.net/20.500.12110/seminario_nCOM000340_Montero
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000340_Montero.pdf
Distrubución geográfica
