Diferencia entre revisiones de «Grafo bipartido»
(→Fuentes.) |
m (Texto reemplazado: «<div align="justify">» por «») |
||
| Línea 1: | Línea 1: | ||
{{Definición|nombre=Grafo bipartido|imagen=k23.png|concepto=Grafo simple sin lazos de forma ''G=<V<sub>1</sub> U V<sub>2</sub>,A>'' donde ''V<sub>1</sub>'' y ''V<sub>2</sub>'' forman una [[partición]] de ''V'' tal que todas las aristas tienen su origen en ''V<sub>1</sub>'' y terminan en ''V<sub>2</sub>''}} | {{Definición|nombre=Grafo bipartido|imagen=k23.png|concepto=Grafo simple sin lazos de forma ''G=<V<sub>1</sub> U V<sub>2</sub>,A>'' donde ''V<sub>1</sub>'' y ''V<sub>2</sub>'' forman una [[partición]] de ''V'' tal que todas las aristas tienen su origen en ''V<sub>1</sub>'' y terminan en ''V<sub>2</sub>''}} | ||
| − | + | ||
'''Grafo bipartido'''. Dícese de todo [[grafo]] simple sin [[lazos]] cuyo conjunto de vértices puede dividirse en dos [[Conjunto disjunto|subconjuntos disjuntos]] no vacíos de manera que los vértices que los componen solo tengan aristas o arcos con vértices del otro subconjunto, nunca con ningún vértice del mismo conjunto. | '''Grafo bipartido'''. Dícese de todo [[grafo]] simple sin [[lazos]] cuyo conjunto de vértices puede dividirse en dos [[Conjunto disjunto|subconjuntos disjuntos]] no vacíos de manera que los vértices que los componen solo tengan aristas o arcos con vértices del otro subconjunto, nunca con ningún vértice del mismo conjunto. | ||
última versión al 00:36 22 ago 2019
| ||||||
Grafo bipartido. Dícese de todo grafo simple sin lazos cuyo conjunto de vértices puede dividirse en dos subconjuntos disjuntos no vacíos de manera que los vértices que los componen solo tengan aristas o arcos con vértices del otro subconjunto, nunca con ningún vértice del mismo conjunto.
Definición.
Un grafo G=<V,A> se dice bipartido o bipartito si y solo si existe una partición de V=V1 U V2 tal que para toda arista (x,y) de A se cumple que x es un vertice de V1 e y está en V2 o simplemente que A será un subconjunto no nulo de V1xV2.
Cuando A=V1xV2 se dice que el grafo es bipartido completo.
Ejemplos.
- El grafo bipartido trivial es K2.
- G=<{a,b}U{c,d,e}, {(a,c),(b,d),(b,e}> es bipartito:
- Un de los grafos de Kuratowvski, K3,3 es bipartido.
- Todos los Kn,m son bipartidos.
Fuentes.
- K. Ribnikov. Análisis Combinatorio. Editorial Mir. Moscú, 1988. Páginas 17-23.
- Artículo:Grafo bipartito en Wikipedia.Disponible en "es.wikipedia.org". Consultado 29 de noviembre de 2011.
