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 \left\{\begin{array}{ll}1 & m = 1 \vee n = 1\\ 2 & \text{en otro caso}\end{array}\right.
Diámetro \left\{\begin{array}{ll}1 & m = n = 1\\ 2 & \text{en otro caso}\end{array}\right.
Cintura (girth) \left\{\begin{array}{ll}\infty & m = 1 \vee n = 1\\ 4 & \text{en otro caso}\end{array}\right.
Automorfismos \left\{\begin{array}{ll}2 m! n! & n = m\\ m! n! & \text{en otro caso}\end{array}\right.
Número cromático 2
Índice cromático max{m, n}

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 V_1 están conectados a todos los vértices de la partición V_2 y viceversa.

Definición[editar]

Un grafo bipartito completo G:=(V_1 \cup V_2, E)\, es un grafo bipartito tal que \forall v_1 \in V_1, \forall\ v_2 \in V_2 \Rightarrow e(v_1, v_2) \in E.\, 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 \left|V_1\right|=m y \left|V_2\right|=n, es denotado como K_{m,n}\,.

Ejemplos[editar]

Véase también[editar]