Grafo bipartido completo
Aspeto mover para a barra lateral ocultar| 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 | K m , n {\displaystyle K_{m,n}} |
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.
Definição
Um grafo bipartido completo, G := (V1 + V2, E), é um grafo bipartido tal que para quaisquer dois vértices, v1 ∈ V1 e v2 ∈ V2, v1v2 é uma aresta em G. O grafo bipartido completo com partições de tamanho |V1|=m e |V2|=n, é denotado Km,n.
Exemplos
Os grafos estrela S3, S4, S5 e S6.
O grafo de utilidade K3,3
- Para qualquer k, K1,k é chamado uma estrela. Todos os grafos bipartidos completos que são árvores são estrelas.
- O grafo K1,3 é chamado uma garra, e é usado para definir os grafos sem garra.
- O grafo K3,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 K3,3.
Propriedades
- Dado um grafo bipartido completo, ele possui dois autovalores simétricos (o índice e o seu simétrico) e os demais nulos.
- Dado um grafo bipartido, encontrar o seu subgrafo bipartido completo Km,n com o número máximo de arestas mn é um problema NP-completo.
- Um grafo planar não pode conter K3,3 como um menor; um grafo periplanar não pode conter K3,2 como um menor (Estas não são condições suficientes de planaridade e planaridade exterior, mas necessárias).
- Um grafo bipartido completo Kn,n é um grafo de Moore e uma (n,4)-gaiola.
- Um grafo bipartido completo Kn,n ou Kn,n+1 é um grafo de Turán.
- Um grafo bipartido completo Km,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 Km,n tem um conjunto independente máximo de tamanho max{m,n}.
- A matriz de adjacência de um grafo bipartido completo Km,n tem autovalores √(nm), −√(nm) e 0; com multiplicidade 1, 1 e n+m−2 respectivamente.
- A matriz laplaciana de um grafo bipartido completo Km,n tem autovalores n+m, n, m, e 0; com multiplicidade 1, m−1, n−1 e 1 respectivamente.
- Um grafo bipartido completo Km,n tem mn−1 nm−1 árvores de extensão.
- Um grafo bipartido completo Km,n tem um acoplamento máximo de tamanho min{m,n}.
- Um grafo bipartido completo Kn,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
Referências
- ↑ BOAVENTURA NETTO, Paulo Oswaldo (2001). Grafos. Teoria, Modelos Algoritmos. São Paulo: Edgard Blücher. p. 263. ISBN 85-212-0292-X