Terminología para entender Teoría de Grafos

Terminología para entender Teoría de Grafos

(Para los chicos de UPN)

Chicos para entender teoría de grafos es  necesario conocer los conceptos básicos en relación al tema. Acá les dejo algunos conceptos (aparte de lo que tenemos en las separatas) muy interesantes, ojalá que les sirva para comprender acerca del  tema tratado.

·        Grafo ponderado.- Es aquel grafo cuyas aristas se les ha asignado un determinado peso o valor (número).

·        Problema del camino de longitud mínima.- El problema de determinar un camino en un grafo ponderado tal que la suma de los pesos de las aristas de dicho grafo sea mínima entre todos los caminos que conectan entre sí los vértices especificados.

·        Problema del viajante.- El problema que pide determinar el circuito de menor longitud total que visita cada vértice del grafo exactamente una  vez.

·        Homeomorfo.- Dos grafos dirigidos son homeomorfos si pueden obtenerse a partir de un mismo grafo por medio de una sucesión de subdivisiones elementales.

·        Bucle o lazo.- Un arista que conecta un vértice consigo mismo (en los pseudografos).

·        Grafo simple.- Es un grafo no dirigido sin bucles ni aristas múltiples.

·        Aristas múltiples.- Aristas distintas conectando a los mismos vértices.

·        Hoja.- Se denomina hoja a un vértice de grado uno.

·        Circuito.-Un camino que comienza y termina en el mismo vértice.

·        Árbol generador.- Llamado también recubridor, es aquel es subgrafo y contiene todos los vértices del grafo.

·        Altura de un árbol.-  Refiere al nivel máximo de los vértices de un árbol.

·        Algoritmo voraz.- Algoritmo que busca una solución óptima realizando la elección óptima en cada paso secuencial del mismo.

·        Algoritmo de Prim.- Procedimiento para construir un árbol generador mínimo en un grafo ponderado mediante la incorporación de las aristas de menor peso que sean incidentes con un vértice que ya esté en el árbol y que no forme un ciclo con las ya seleccionadas.

·        Algoritmo de Kruskal.- Procedimiento para construir un árbol generador mínimo en un grafo ponderado mediante la incorporación de las aristas de menor peso que no estén ya en el árbol en el momento en que se añaden y que no formen un ciclo con las ya seleccionadas