Grafo bipartido completo

No campo da matemática da teoria dos grafos, um grafo bipartido completo ou biclique é um tipo especial de grafo bipartido onde cada vértice do primeiro conjunto está associado a cada vértice do segundo conjunto.

Grafo bipartido completo
Um grafo bipartido completo com m = 5 n = 3
vértices	n + m
arestas	mn
Cintura	4
Automorfismos	2m!n! se m=n, caso contrário m!n!
Número cromático	2
Índice cromático	max{m, n}
Notação	${\displaystyle K_{m,n}}$

Definição

Um grafo bipartido completo, G := (V₁ + V₂, E), é um grafo bipartido tal que para quaisquer dois vértices, v₁ ∈ V₁ e v₂ ∈ V₂, v₁v₂ é uma aresta em G. O grafo bipartido completo com partições de tamanho |V₁|=m e |V₂|=n, é denotado K_m,n.

Exemplos

Os grafos estrela S₃, S₄, S₅ e S₆.

O grafo de utilidade K_3,3

• Para qualquer k, K_1,k é chamado uma estrela. Todos os grafos bipartidos completos que são árvores são estrelas.
• O grafo K_1,3 é chamado uma garra, e é usado para definir os grafos sem garra.
• O grafo K_3,3 é chamado de grafo de utilidade. Esta prática vem de um quebra-cabeça matemático tradicional, no qual três utilidades devem ser ligadas a cada três edifícios; é impossível de resolver sem cruzamentos, devido à não-planaridade de K_3,3.

Propriedades

• Dado um grafo bipartido completo, ele possui dois autovalores simétricos (o índice e o seu simétrico) e os demais nulos.^[1]
• Dado um grafo bipartido, encontrar o seu subgrafo bipartido completo K_m,n com o número máximo de arestas mn é um problema NP-completo.
• Um grafo planar não pode conter K_3,3 como um menor; um grafo periplanar não pode conter K_3,2 como um menor (Estas não são condições suficientes de planaridade e planaridade exterior, mas necessárias).
• Um grafo bipartido completo K_n,n é um grafo de Moore e uma (n,4)-gaiola.
• Um grafo bipartido completo K_n,n ou K_n,n+1 é um grafo de Turán.
• Um grafo bipartido completo K_m,n tem um número de cobertura de vértice do min{m,n} e um número de cobertura de aresta de max{m,n}.
• Um grafo bipartido completo K_m,n tem um conjunto independente máximo 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^m−1 árvores de extensão.
• Um grafo bipartido completo K_m,n tem um acoplamento máximo de tamanho min{m,n}.
• Um grafo bipartido completo K_n,n tem uma n-coloração-de-arestas correspondente ao quadrado latino.
• Os dois últimos resultados são corolários do teorema do casamento aplicado a um grafo bipartido k-regular.

Ver também

• Grafo ciclo
• Grafo caminho
• Grafo coroa
• Grafo completo
• Grafo nulo
• Matriz de adjacência

Referências

1. BOAVENTURA NETTO, Paulo Oswaldo (2001). Grafos. Teoria, Modelos Algoritmos. São Paulo: Edgard Blücher. p. 263. ISBN 85-212-0292-X