Diferencia entre revisiones de «Bosque (Grafo)»
m (Texto reemplazado: «<div align="justify">» por «») |
|||
| (No se muestra una edición intermedia de otro usuario) | |||
| 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. | ||
| Línea 12: | Línea 12: | ||
Sea un grafo ''G=<V,A>'' se dice que es un '''bosque''' si y solo si ''V=V<sub>1</sub>UV<sub>2</sub>U...UV<sub>n</sub>'' y ''A=A<sub>1</sub>UA<sub>2</sub>U...UA<sub>n</sub>'' donde ''G=G<sub>1</sub>UG<sub>2</sub>U...UG<sub>n</sub>'', ''G<sub>i</sub>=<V<sub>i</sub>,A<sub>i</sub>>'' es un árbol tal que para cualquier otro componente ''G<sub>j</sub>=<V<sub>j</sub>,A<sub>j</sub>>'' (''i≠j'') se cumple que ''V<sub>i</sub>^V<sub>j</sub>={}'' y ''A<sub>i</sub>^A<sub>j</sub>={}'' (los árboles de un bosque son obligatoriamente disjuntos). | Sea un grafo ''G=<V,A>'' se dice que es un '''bosque''' si y solo si ''V=V<sub>1</sub>UV<sub>2</sub>U...UV<sub>n</sub>'' y ''A=A<sub>1</sub>UA<sub>2</sub>U...UA<sub>n</sub>'' donde ''G=G<sub>1</sub>UG<sub>2</sub>U...UG<sub>n</sub>'', ''G<sub>i</sub>=<V<sub>i</sub>,A<sub>i</sub>>'' es un árbol tal que para cualquier otro componente ''G<sub>j</sub>=<V<sub>j</sub>,A<sub>j</sub>>'' (''i≠j'') se cumple que ''V<sub>i</sub>^V<sub>j</sub>={}'' y ''A<sub>i</sub>^A<sub>j</sub>={}'' (los árboles de un bosque son obligatoriamente disjuntos). | ||
| + | |||
| + | También puede decirse que un grafo unidireccional simple sin ciclos es un bosque. | ||
==Fuentes== | ==Fuentes== | ||
ú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.
