Matemáticas discretas: árboles generadores y generadores minimales

Matemática discreta. Árbol generador. Grafo ponderado. Vértice, vértices. Algoritmo de Prim y de Kruskal. Educación

  • Enviado por: Cristian Pozo
  • Idioma: castellano
  • País: Chile Chile
  • 3 páginas
publicidad

INFORME DE MATEMATICAS DISCRETAS

TEMA : ARBOLES GENERADORES Y GENERADORES MINIMALES.

I.- Arboles Generadores.-

Def.: Un árbol T, subgrafo de un grafo G que contenga todos los vértices de G se denómina Arbol Generador de G.

A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es asi como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.

En general un grafo G tendrá varios árboles generadores ,como el del ejemplo 1 el cual tiene a lo menos dos arboles generadores T1 yT2.

Ej.