Bosque (Grafo)

Bosque grafo

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.

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=V₁UV₂U...UV_n y A=A₁UA₂U...UA_n donde G=G₁UG₂U...UG_n, G_i=<V_i,A_i> es un árbol tal que para cualquier otro componente G_j=<V_j,A_j> (i≠j) se cumple que V_i^V_j={} y A_i^A_j={} (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.

This article is issued from Ecured. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.