Grafo bipartito

Grafo bipartito
Ejemplo de grafo bipartito.

Un Grafo bipartito se denomina en Teoría de grafos a un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen vértices de un conjunto con vértices de otro:

  • V_1 \cup V_2 = V
  • V_1 \cap V_2 = \empty
  • \forall x_1,x_2 \in V_1, \forall y_1,y_2 \in V_2 no existe ninguna arista e = x1,x2 ni e = y1,y2


Siendo V el conjunto que contiene todos los vértices del grafo.

Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.

Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U de azul y los vértices deV de verde obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.

Un grafo bipartito suele con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si los dos subconjuntos tiene la misma cantidad de elementos, decimos que el grafo bipartito G es balanceado.

Ejemplos

  • Todo grafo sin ciclos con cantidad de nodos impar es bipartito. Como consecuencia de esto:
    • Todo árbol es bipartito.
    • Los grafos cíclicos con un número par de vértices son bipartitos.
    • Todo grafo planar donde todas las caras tienen un número par de aristas es bipartito.

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Grafo bipartito completo — 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 V1 están conectados a todos los vértices de la partición V2 y viceversa. Definición Un grafo bipartito completo es …   Wikipedia Español

  • Grafo completo — K7, grafo completo de 7 vértices. Vértices n Aristas …   Wikipedia Español

  • Grafo — Para otros usos de este término, véase Grafo (desambiguación). Para la teoría en torno a este objeto matemático, véase Teoría de grafos. Grafo etiquetado con 6 vértices y 7 aristas. En matemáticas y ciencias de la computación, un grafo (del …   Wikipedia Español

  • Grafo ciclo — Ciclo Cn C6: Un Grafo Ciclo de longitud 6. Vertices: n Aristas: n …   Wikipedia Español

  • Grafo plano — Grafos de ejemplo Plano No plano …   Wikipedia Español

  • Grafo perfecto — El grafo Paley de orden 9, coloreado con tres colores, mostrando un clique de tres vértices. En este grafo y cada uno de sus subgrafos inducidos, el número cromático es igual al número de clique, por lo que es un grafo perfecto. En teoría de… …   Wikipedia Español

  • Grafo cúbico — El Grafo de Petersen es un grafo cúbico. En teoría de grafos, un grafo cúbico o grafo trivalente es un grafo cuyos vértices son todos incidentes a exactamente tres aristas. En otras palabras, un grafo cúbico es un grafo 3 regular. Un grafo… …   Wikipedia Español

  • Grafo de Petersen — El grafo de Petersen es comúnmente dibujado como un pentágono con una estrella de 5 puntas dentro. Nombre en honor a Julius Petersen …   Wikipedia Español

  • Anexo:Glosario de teoría de grafos — Grafo simple no dirigido, con 6 vértices y 7 aristas. A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los… …   Wikipedia Español

  • Teoría de grafos — Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”