Grafo bipartito completo

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Grafo bipartito completo
Biclique K 3 5.svg
Un grafo bipartito completo con m = 5 y n = 3
Vértices n + m
Aristas mn
Radio
Diámetro
Cintura (girth)
Automorfismos
Número cromático 2
Índice cromático max{m, n}
[editar datos en Wikidata]

En teoría de grafos un grafo bipartito (o bipartido) completo es aquel grafo bipartito en el que todos los vértices de la partición están conectados a todos los vértices de la partición y viceversa.

Definición[editar]

Un grafo bipartito completo es un grafo bipartito tal que Es decir, un grafo bipartito completo está formado por dos conjuntos disjuntos de vértices y todas las posibles aristas que unen esos vértices.

El grafo completo bipartito con particiones de tamaño y es denotado como .

Ejemplos[editar]


Propiedades[editar]

Sea un grafo bipartito con y , se verifica:

  • posee árboles de expansión.

Véase también[editar]