Diferencia entre revisiones de «Bosque (Grafo)»
m (Texto reemplazado: «<div align="justify">» por «») |
|||
| Línea 1: | Línea 1: | ||
{{Definición|nombre=Bosque grafo|imagen=BosqueGrafo.gif|concepto=[[Grafo]] que representa una colección de árboles no coincidentes.}} | {{Definición|nombre=Bosque grafo|imagen=BosqueGrafo.gif|concepto=[[Grafo]] que representa una colección de árboles no coincidentes.}} | ||
| − | + | ||
'''Bosque(Grafo)'''. Dícese del [[grafo]] que contiene un árbol o varios árboles disjuntos. | '''Bosque(Grafo)'''. Dícese del [[grafo]] que contiene un árbol o varios árboles disjuntos. | ||
última versión al 01:32 28 jul 2019
| ||||||
Bosque(Grafo). Dícese del grafo que contiene un árbol o varios árboles disjuntos.
Definición
Sea un grafo G=<V,A> se dice que es un bosque si y solo si:
- Es un árbol.
- Es un árbol y un bosque que no coincide con el árbol anterior.
Esta definición recursiva de bosque puede formalizarse como:
Sea un grafo G=<V,A> se dice que es un bosque si y solo si V=V1UV2U...UVn y A=A1UA2U...UAn donde G=G1UG2U...UGn, Gi=<Vi,Ai> es un árbol tal que para cualquier otro componente Gj=<Vj,Aj> (i≠j) se cumple que Vi^Vj={} y Ai^Aj={} (los árboles de un bosque son obligatoriamente disjuntos).
También puede decirse que un grafo unidireccional simple sin ciclos es un bosque.
Fuentes
- K. Ribnikov. Análisis Combinatorio. Moscú: Editorial MIR. 1988.
- Árbol en wikipedia. Consultado el 12 de febrero de 2016.
