analisis de algoritmo

Programación IV. Guía 7

1

Facultad:
Ingeniería
Escuela:
Computación
Asignatura: Programación IV

Tema: Grafos en C#.
Objetivos Específicos
•

Definir el concepto de Grafo.

•

Apartir de una clase agregar la sintaxis necesaria para construir una función de grafos en C#

Materiales y Equipo
•

Guía Número 7.

•

Computadora con programa Microsoft Visual C#.Introducción Teórica
Grafos.
Un grafo G = (V, E) está formado por un conjunto de elementos llamados vértices “V” y un
conjunto de aristas “E” que conectan a los distintos vértices. En ocasiones losvértices son
llamados nodos y las aristas arcos.
Las aristas se definen como el par de vértices que conectan y pueden tener asociado un valor
el cual representa el peso o dificultad para desplazarse de unvértice a otro.
Ejemplo gráfico de un grafo:

Figura 1.

Donde:
Vértices = {A, B, C, D, E}
Aristas = {(A, B), (A, D), (B, C), (B, D), (B, E), (C, E), (D, E), (E, D)}

2

Programación IV.Guía 7

Tipos de grafos.
Existen dos tipos de grafos: los no dirigidos y los dirigidos.
Grafos No Dirigidos.
Son aquellos en los cuales las aristas no están orientadas (no son flechas). Cada ladose
representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta que
ambos vértices son origen y destino a la vez: (Vi, Vj) = (Vj, Vi).
Grafos Dirigidos.
Son aquellos en loscuales las aristas están orientadas (son flechas). Cada arista se representa
entre paréntesis, separando sus vértices por comas y teniendo en cuenta (Vi, Vj) ≠ (Vj, Vi).
Los grafos puedenrepresentarse de varias formas en una computadora:

 Listas adyacentes.
Cada vértice tiene una lista de vértices los cuales son adyacentes a él.
Representación del ejemplo (grafo de Figura 1):
(A) => B=> D
(B) => C => D => E
(C) => E
(D) => E
(E) => D

 Listas de pares ordenados (incidentes).
Las aristas se representan como un arreglo de pares ordenados.

 Matriz de adyacencia.
El...