Diferencia entre revisiones de «Bosque (Grafo)»
(→Definición) |
(→Definición) |
||
| Línea 10: | Línea 10: | ||
Sea un grafo ''G=<V,A>'' se dice que es un '''bosque''' si y solo si: | Sea un grafo ''G=<V,A>'' se dice que es un '''bosque''' si y solo si: | ||
| − | |||
| − | |||
* Es un [[Árbol(Grafo)|árbol]]. | * Es un [[Árbol(Grafo)|árbol]]. | ||
| − | |||
* Es un árbol y un bosque que no coincide con el árbol anterior. | * Es un árbol y un bosque que no coincide con el árbol anterior. | ||
| − | |||
| − | |||
Esta definición recursiva de bosque puede formalizarse como: | 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=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>=0'' (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>=0'' (los árboles de un bosque son obligatoriamente disjuntos). | ||
Revisión del 11:49 13 feb 2016
| ||||||
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=0 (los árboles de un bosque son obligatoriamente disjuntos).
Fuentes
- K. Ribnikov. Análisis Combinatorio. Moscú: Editorial MIR. 1988.
- Árbol en wikipedia. Consultado
