Gráfico de acordes - Chordal graph
Na área matemática da teoria dos grafos , um gráfico de cordas é aquele em que todos os ciclos de quatro ou mais vértices têm uma corda , que é uma aresta que não faz parte do ciclo, mas conecta dois vértices do ciclo. Equivalentemente, cada ciclo induzido no gráfico deve ter exatamente três vértices. Os grafos cordais também podem ser caracterizados como os grafos que possuem ordenações de eliminação perfeita, como os grafos em que cada separador mínimo é um clique e como os grafos de interseção das subárvores de uma árvore. Às vezes, eles também são chamados de gráficos de circuitos rígidos ou gráficos triangulados .
Os gráficos de acordes são um subconjunto dos gráficos perfeitos . Eles podem ser reconhecidos em tempo linear , e vários problemas que são difíceis para outras classes de gráficos, como a coloração de gráficos, podem ser resolvidos em tempo polinomial quando a entrada é cordal. A largura da árvore de um grafo arbitrário pode ser caracterizada pelo tamanho dos cliques nos grafos cordais que o contêm.
Eliminação perfeita e reconhecimento eficiente
Uma ordem de eliminação perfeita em um grafo é uma ordenação dos vértices do grafo de tal forma que, para cada vértice v , ve os vizinhos de v que ocorrem após v na ordem formam um clique . Um gráfico é cordal se e somente se tiver uma ordem de eliminação perfeita.
Rose, Lueker & Tarjan (1976) (ver também Habib et al. 2000 ) mostram que uma ordem de eliminação perfeita de um gráfico de cordas pode ser encontrada de forma eficiente usando um algoritmo conhecido como pesquisa em largura lexicográfica . Este algoritmo mantém uma partição dos vértices do gráfico em uma sequência de conjuntos; inicialmente essa sequência consiste em um único conjunto com todos os vértices. O algoritmo escolhe repetidamente um vértice v do conjunto mais antigo na sequência que contém vértices não escolhidos anteriormente e divide cada conjunto S da sequência em dois subconjuntos menores, o primeiro consistindo nos vizinhos de v em S e o segundo consistindo no não -vizinhos. Quando este processo de divisão for executado para todos os vértices, a sequência de conjuntos terá um vértice por conjunto, no reverso de uma ordem de eliminação perfeita.
Uma vez que tanto esse processo de primeira busca de amplitude lexicográfica quanto o processo de testar se uma ordenação é uma ordenação de eliminação perfeita podem ser realizados em tempo linear, é possível reconhecer gráficos cordais em tempo linear. O problema do sanduíche de gráfico em gráficos de cordas é NP-completo, enquanto o problema de gráfico de sonda em gráficos de cordas tem complexidade de tempo polinomial.
O conjunto de todas as ordenações de eliminação perfeita de um gráfico de cordas pode ser modelado como as palavras básicas de um antimatróide ; Chandran et al. (2003) usam essa conexão com antimatróides como parte de um algoritmo para listar de forma eficiente todas as ordens de eliminação perfeitas de um dado gráfico de cordas.
Cliques máximos e coloração de gráfico
Outra aplicação de ordenações de eliminação perfeita é encontrar um clique máximo de um grafo cordal em tempo polinomial, enquanto o mesmo problema para grafos gerais é NP-completo . De forma mais geral, um gráfico de cordas pode ter apenas muitos cliques máximos linearmente , enquanto os gráficos não cordais podem ter muitos exponencialmente. Para listar todos os cliques máximos de um grafo de cordas, simplesmente encontre uma ordem de eliminação perfeita, forme um clique para cada vértice v junto com os vizinhos de v que são posteriores a v na ordem de eliminação perfeita e teste se cada um dos cliques resultantes é maximal.
Os gráficos de clique de grafos cordais são os grafos duplamente cordais .
O maior clique máximo é um clique máximo e, como os gráficos cordais são perfeitos, o tamanho deste clique é igual ao número cromático do gráfico cordal. Os gráficos de cordas são perfeitamente ordenáveis : uma coloração ótima pode ser obtida aplicando um algoritmo de coloração gananciosa aos vértices no reverso de uma ordenação de eliminação perfeita.
O polinômio cromático de um gráfico de cordas é fácil de calcular. Encontre uma ordem de eliminação perfeita Seja N i igual ao número de vizinhos de v i que vêm depois de v i nessa ordem. Por exemplo, N n = 0. O polinômio cromático é igual (O último fator é simplesmente x , então x divide o polinômio, como deveria.) Claramente, esse cálculo depende da cordalidade.
Separadores mínimos
Em qualquer gráfico, um separador de vértices é um conjunto de vértices cuja remoção deixa o gráfico restante desconectado; um separador é mínimo se não tiver um subconjunto adequado que também seja um separador. De acordo com um teorema de Dirac (1961) , grafos cordais são grafos nos quais cada separador mínimo é um clique; Dirac usou essa caracterização para provar que os gráficos de cordas são perfeitos .
A família de grafos cordais pode ser definida indutivamente como os grafos cujos vértices podem ser divididos em três subconjuntos não vazios A , S e B , de modo que A ∪ S e S ∪ B ambos formam subgráficos induzidos por cordas , S é um clique, e lá existem arestas de um a B . Ou seja, eles são os gráficos que têm uma decomposição recursiva por separadores de clique em subgráficos menores. Por esse motivo, os gráficos de acordes também são chamados às vezes de gráficos decomponíveis .
Gráficos de intersecção de subárvores
Uma alternativa de caracterização de grafos cordais, devido a Gavril (1974) , envolve árvores e suas subárvores.
De uma coleção de subárvores de uma árvore, pode-se definir um gráfico de subárvore , que é um gráfico de interseção que possui um vértice por subárvore e uma aresta conectando quaisquer duas subárvores que se sobrepõem em um ou mais nós da árvore. Gavril mostrou que os gráficos da subárvore são exatamente os gráficos cordais.
Uma representação de um grafo cordal como uma interseção de subárvores forma uma decomposição em árvore do grafo, com largura da árvore igual a um menor que o tamanho do maior clique no grafo; a decomposição em árvore de qualquer gráfico G pode ser vista dessa forma como uma representação de G como um subgráfico de um gráfico cordal. A decomposição da árvore de um gráfico também é a árvore de junção do algoritmo da árvore de junção .
Relação com outras classes de gráfico
Subclasses
Os gráficos de intervalo são os gráficos de interseção de subárvores de gráficos de caminho , um caso especial de árvores. Portanto, eles são uma subfamília de gráficos cordais.
Gráficos de divisão são gráficos de acordes e complementos de gráficos de acordes. Bender, Richmond & Wormald (1985) mostraram que, no limite à medida que n vai para o infinito, a fração de grafos cordais de n vértices que são divididos se aproxima de um.
Os gráficos ptolomaicos são gráficos que são tanto cordais quanto hereditários à distância . Os gráficos de quase-limiar são uma subclasse dos gráficos ptolomaicos que são cordais e cográficos . Os grafos de blocos são outra subclasse dos grafos ptolomaicos em que cada dois cliques máximos têm no máximo um vértice em comum. Um tipo especial são os gráficos de moinhos de vento , onde o vértice comum é o mesmo para todos os pares de cliques.
Gráficos fortemente cordais são gráficos que são cordais e não contêm n -sun (para n ≥ 3) como um subgráfico induzido. Aqui um n -sun é um n -vertex cordal gráfico G em conjunto com uma colecção de n grau de dois vértices, adjacente aos bordos de um ciclo hamiltoniano em L .
As árvores K são grafos cordais nos quais todos os cliques máximos e todos os separadores de cliques máximos têm o mesmo tamanho. As redes apolíneas são grafos planares máximos cordaisou, equivalentemente, três árvores planas. Máximas gráficos outerplanar são uma subclasse de 2-árvores, e, por conseguinte, também são cordal.
Superclasses
Os gráficos de acordes são uma subclasse dos gráficos perfeitos bem conhecidos . Outros superclasses de grafos cordais incluem gráficos fracamente acordes, gráficos cop-win , gráficos odd-livre de buracos, gráficos, mesmo livre de buracos e gráficos Meyniel . Os gráficos de cordas são precisamente os gráficos que estão livres de buracos ímpares e livres de buracos pares (veja os buracos na teoria dos grafos).
Todo gráfico de cordas é um gráfico estrangulado , um gráfico em que todo ciclo periférico é um triângulo, porque os ciclos periféricos são um caso especial de ciclos induzidos. Grafos estrangulados são grafos que podem ser formados por clique-somas de grafos cordais e grafos planares máximos. Portanto, os gráficos estrangulados incluem gráficos planares máximos .
Conclusões de acordes e largura da árvore
Se G for um gráfico arbitrário, uma conclusão de cordas de G (ou preenchimento mínimo ) é um gráfico de cordas que contém G como um subgráfico. A versão parametrizada de preenchimento mínimo é tratável por parâmetro fixo e, além disso, é solucionável em tempo subexponencial parametrizado. A largura da árvore de G é um a menos que o número de vértices em um clique máximo de uma conclusão de cordas escolhida para minimizar o tamanho desse clique. As k -árvores são os gráficos aos quais nenhuma aresta adicional pode ser adicionada sem aumentar sua largura da árvore para um número maior que k . Portanto, as k- árvores são suas próprias conclusões de acordes e formam uma subclasse dos gráficos de acordes. Os completamentos de acordes também podem ser usados para caracterizar várias outras classes relacionadas de gráficos.
Notas
Referências
- Agnarsson, Geir (2003), "On chordal graphs and its cromáticos polinômios" , Mathematica Scandinavica , 93 (2): 240–246, doi : 10.7146 / math.scand.a-14421 , MR 2009583.
- Bender, EA; Richmond, LB; Wormald, NC (1985), "Quase todos os gráficos cordais divididos", J. Austral. Matemática. Soc. , A, 38 (2): 214–221, doi : 10.1017 / S1446788700023077 , MR 0770128.
- Berge, Claude (1967), "Some Classes of Perfect Graphs", em Harary, Frank (ed.), Graph Theory and Theoretical Physics , Academic Press, pp. 155–165, MR 0232694.
- Berry, Anne; Golumbic, Martin Charles ; Lipshteyn, Marina (2007), "Recognizing chordal probe graphs and cycle-bicolorable graphs", SIAM Journal on Discrete Mathematics , 21 (3): 573–591, doi : 10.1137 / 050637091.
- Bodlaender, HL ; Fellows, MR ; Warnow, TJ (1992), "Two strikes against perfect phylogeny" (PDF) , Proc. of 19th International Colloquium on Automata Languages and Programming , Lecture Notes in Computer Science, 623 , pp. 273-283, doi : 10.1007 / 3-540-55719-9_80 , hdl : 1874/16653.
- Chandran, LS; Ibarra, L .; Ruskey, F .; Sawada, J. (2003), "Enumerando e caracterizando as ordenações de eliminação perfeita de um gráfico de cordas" (PDF) , Theoretical Computer Science , 307 (2): 303-317, doi : 10.1016 / S0304-3975 (03) 00221- 4.
- Dirac, GA (1961), "On rigid circuit graphs" (PDF) , Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 25 (1-2): 71-76, doi : 10.1007 / BF02992776 , MR 0130190 , S2CID 120608513.
- Fomin, Fedor V .; Villanger, Yngve (2013), "Subexponential Parameterized Algorithm for Minimum Fill-In", SIAM J. Comput. , 42 (6): 2197–2216, arXiv : 1104.2230 , doi : 10.1137 / 11085390X , S2CID 934546.
- Fulkerson, DR ; Gross, OA (1965), "Incidence matrices and interval graphs" , Pacific J. Math. , 15 (3): 835-855, doi : 10.2140 / pjm.1965.15.835.
- Gavril, Fănică (1974), "Os gráficos de interseção de subárvores em árvores são exatamente os gráficos cordais", Journal of Combinatorial Theory , Series B, 16 : 47-56, doi : 10.1016 / 0095-8956 (74) 90094-X.
- Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs , Academic Press.
- Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS e refinamento de partição, com aplicações para orientação transitiva, reconhecimento de gráfico de intervalo e testes consecutivos" , Theoretical Computer Science , 234 (1-2): 59-84, doi : 10.1016 / S0304-3975 (97) 00241-7.
- Kaplan, Haim; Shamir, Ron; Tarjan, Robert (1999), "Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs", SIAM J. Comput. , 28 (5): 1906–1922, doi : 10.1137 / S0097539796303044.
- Maffray, Frédéric (2003), "On the coloration of perfect graphs", in Reed, Bruce A .; Sales, Cláudia L. (eds.), Recent Advances in Algorithms and Combinatorics , CMS Books in Mathematics, 11 , Springer-Verlag, pp. 65-84, doi : 10.1007 / 0-387-22444-0_3 , ISBN 0-387-95434-1.
- Parra, Andreas; Scheffler, Petra (1997), "Caracterizações e aplicações algorítmicas de embeddings de grafos cordais", Discrete Applied Mathematics , 79 (1-3): 171-188, doi : 10.1016 / S0166-218X (97) 00041-3 , MR 1478250.
- Patil, HP (1986), "On the structure of k -trees", Journal of Combinatorics, Information and System Sciences , 11 (2-4): 57-64, MR 0966069.
- Rose, D .; Lueker, George; Tarjan, Robert E. (1976), "Algorithmic aspect of vertex elimination on graphs", SIAM Journal on Computing , 5 (2): 266-283, doi : 10.1137 / 0205021 , MR 0408312.
- Seymour, PD ; Weaver, RW (1984), "A generalization of chordal graphs", Journal of Graph Theory , 8 (2): 241-251, doi : 10.1002 / jgt.3190080206 , MR 0742878.
- Szwarcfiter, JL ; Bornstein, CF (1994), "Clique graphs of chordal and path graphs", SIAM Journal on Discrete Mathematics , 7 (2): 331–336, doi : 10.1137 / s0895480191223191 , hdl : 11422/1497.