Gráfico bipartido completo - Complete bipartite graph

Grafo bipartido completo
Um gráfico bipartido completo com m = 5 e n = 3
Vértices	n + m
Arestas	mn
Raio	${\ displaystyle \ left \ {{\ begin {array} {ll} 1 & m = 1 \ vee n = 1 \\ 2 & {\ text {caso contrário}} \ end {array}} \ right.}$
Diâmetro	${\ displaystyle \ left \ {{\ begin {array} {ll} 1 & m = n = 1 \\ 2 & {\ text {caso contrário}} \ end {array}} \ right.}$
Cilha	${\ displaystyle \ left \ {{\ begin {array} {ll} \ infty & m = 1 \ lor n = 1 \\ 4 & {\ text {caso contrário}} \ end {array}} \ right.}$
Automorfismos	${\ displaystyle \ left \ {{\ begin {array} {ll} 2m! n! & n = m \\ m! n! & {\ text {caso contrário}} \ end {array}} \ right.}$
Número cromático	2
Índice cromático	máx { m , n }
Espectro	${\ displaystyle \ left \ {0 ^ {n + m-2}, (\ pm {\ sqrt {nm}}) ^ {1} \ right \}}$
Notação	${\ displaystyle K_ {m, n}}$
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 ₁ 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 ₁ , V ₂ , E ) de tal modo que, para cada dois vértices v ₁ ∈ V ₁ e v ₂ ∈ V ₂ , v ₁ v ₂ é uma vantagem em E . Um gráfico bipartido completo com partições de tamanho | V ₁ | = m e | V ₂ | = n , é denotado por K _{m, n} ; cada dois gráficos com a mesma notação são isomórficos .

Exemplos

A estrela representa graficamente K _1,3 , K _1,4 , K _1,5 e K _1,6 .

Um gráfico bipartido completo de K _4,7 mostrando que o problema da fábrica de tijolos de Turán com 4 locais de armazenamento (pontos amarelos) e 7 fornos (pontos azuis) requer 18 cruzamentos (pontos vermelhos)

• 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

Exemplo K _{p , p} gráficos bipartidos completos

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 ₅ 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

Referências