Diferencia entre revisiones de «Bosque (Grafo)»
(→Definición) |
|||
| 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.}} | ||
| − | |||
<div align="justify"> | <div align="justify"> | ||
| − | |||
'''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. | ||
| − | |||
| − | |||
==Definición== | ==Definición== | ||
| − | |||
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: | ||
| Línea 16: | Línea 11: | ||
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 '' | + | 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). |
==Fuentes== | ==Fuentes== | ||
| − | |||
# K. Ribnikov. Análisis Combinatorio. [[Moscú]]: [[Editorial MIR]]. [[1988]]. | # K. Ribnikov. Análisis Combinatorio. [[Moscú]]: [[Editorial MIR]]. [[1988]]. | ||
| − | + | # [https://es.wikipedia.org/wiki/%C3%81rbol_%28teor%C3%ADa_de_grafos%29 Árbol] en wikipedia. Consultado el [[12 de febrero]] de [[2016]]. | |
| − | # [https://es.wikipedia.org/wiki/%C3%81rbol_%28teor%C3%ADa_de_grafos%29 Árbol] en wikipedia. Consultado | ||
| − | |||
</div> | </div> | ||
| − | |||
[[Categoría:Matemáticas]][[Categoría:Álgebra]] | [[Categoría:Matemáticas]][[Categoría:Álgebra]] | ||
Revisión del 11:51 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={} (los árboles de un bosque son obligatoriamente disjuntos).
Fuentes
- K. Ribnikov. Análisis Combinatorio. Moscú: Editorial MIR. 1988.
- Árbol en wikipedia. Consultado el 12 de febrero de 2016.
