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 distinto de j) se cumple que <V_i<V_j y A_iA_j (los árboles de un bosque son obligatoriamente disjuntos).

Fuentes

1. K. Ribnikov. Análisis Combinatorio. Moscú: Editorial MIR. 1988.

1. Árbol en wikipedia. Consultado