Gráfico bipartido completo - Complete bipartite graph
Grafo bipartido completo | |
---|---|
Vértices | n + m |
Arestas | mn |
Raio | |
Diâmetro | |
Cilha | |
Automorfismos | |
Número cromático | 2 |
Índice cromático | máx { m , n } |
Espectro | |
Notação | |
Tabela de gráficos e parâmetros |
No campo matemático da teoria dos grafos , um grafo bipartido completo ou biclique é um tipo especial de grafo bipartido em que cada vértice do primeiro conjunto está conectado a cada vértice do segundo conjunto.
A própria teoria dos grafos é tipicamente datada do início do trabalho de Leonhard Euler de 1736 nas Sete Pontes de Königsberg . No entanto, os desenhos de gráficos bipartidos completos já foram impressos já em 1669, em conexão com uma edição das obras de Ramon Llull editada por Athanasius Kircher . O próprio Lúlio havia feito desenhos semelhantes de gráficos completos três séculos antes.
Definição
Um grafo bipartido completo é um grafo cujos vértices podem ser particionados em dois subconjuntos V 1 e V 2 de modo que nenhuma aresta tenha ambos os pontos finais no mesmo subconjunto, e cada aresta possível que poderia conectar vértices em subconjuntos diferentes faz parte do gráfico. Isto é, é um grafo bipartido ( V 1 , V 2 , E ) de tal modo que, para cada dois vértices v 1 ∈ V 1 e v 2 ∈ V 2 , v 1 v 2 é uma vantagem em E . Um gráfico bipartido completo com partições de tamanho | V 1 | = m e | V 2 | = n , é denotado por K m, n ; cada dois gráficos com a mesma notação são isomórficos .
Exemplos
- Para qualquer k , K 1, k é chamado de estrela . Todos os gráficos bipartidos completos que são árvores são estrelas.
- O gráfico K 1,3 é chamado de garra e é usado para definir os gráficos sem garras .
- O gráfico K 3,3 é denominado gráfico de utilidade . Esse uso vem de um quebra-cabeça matemático padrão no qual três utilitários devem ser conectados cada um a três edifícios; é impossível resolver sem cruzamentos devido à não planaridade de K 3,3 .
- Os bicliques máximos encontrados como subgráficos do dígrafo de uma relação são chamados de conceitos . Quando uma rede é formada tomando encontros e junções desses subgráficos, a relação tem uma rede de conceito induzida . Este tipo de análise de relações é denominado análise de conceito formal .
Propriedades
K 3,3 | K 4,4 | K 5,5 |
---|---|---|
3 cores de borda |
4 cores de borda |
5 cores de borda |
Polígonos complexos regulares da forma 2 {4} p têm grafos bipartidos completos com 2 p vértices (vermelho e azul) ep 2 2 arestas. Eles também podem ser desenhados como p cores de borda. |
- Dado um grafo bipartido, testar se ele contém um subgrafo bipartido completo K i , i para um parâmetro i é um problema NP-completo .
- Um gráfico planar não pode conter K 3,3 como menor ; um grafo planar externo não pode conter K 3,2 como menor (estas não são condições suficientes para planaridade e planaridade externa, mas necessárias). Por outro lado, todo gráfico não plano contém K 3,3 ou o gráfico completo K 5 como um menor; este é o teorema de Wagner .
- Cada gráfico bipartido completo. K n , n é um gráfico de Moore e uma ( n , 4) - gaiola .
- Os grafos bipartidos completos K n , n e K n , n +1 têm o número máximo possível de arestas entre todos os grafos livres de triângulos com o mesmo número de vértices; este é o teorema de Mantel . O resultado de Mantel foi generalizado para grafos k -partidos e grafos que evitam cliques maiores como subgráficos no teorema de Turán , e esses dois grafos bipartidos completos são exemplos de grafos de Turán , os grafos extremos para este problema mais geral.
- O grafo bipartido completo K m , n tem um vértice cobrindo o número de min { m , n } e uma aresta cobrindo o número de max { m , n }.
- O grafo bipartido completo K m , n tem um conjunto máximo independente de tamanho max { m , n }.
- A matriz de adjacência de um grafo bipartido completo K m , n tem autovalores √ nm , - √ nm e 0; com multiplicidade 1, 1 e n + m −2 respectivamente.
- A matriz Laplaciana de um grafo bipartido completo K m , n tem autovalores n + m , n , m e 0; com multiplicidade 1, m −1, n −1 e 1 respectivamente.
- Um grafo bipartido completo K m , n tem m n −1 n m −1 árvores geradoras .
- Um grafo bipartido completo K m , n tem uma correspondência máxima de tamanho min { m , n }.
- Um grafo bipartido completo K n , n tem uma coloração n -aresta adequada que corresponde a um quadrado latino .
- Todo grafo bipartido completo é um grafo modular : cada triplo de vértices tem uma mediana que pertence aos caminhos mais curtos entre cada par de vértices.
Veja também
- Gráfico livre de Biclique , uma classe de gráficos esparsos definidos evitando subgráficos bipartidos completos
- O gráfico da coroa , um gráfico formado pela remoção de uma combinação perfeita de um gráfico bipartido completo
- Grafo multipartido completo , uma generalização de grafos bipartidos completos para mais de dois conjuntos de vértices
- Ataque Biclique