CHAVO

Programación IV. Guía 10

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 10.
• Computadora con programa Microsoft Visual C#.

IntroducciónTeó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 los vértices sonllamados 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:

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 10
Tipos degrafos.
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 lado se
representa entreparé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 los cuales las aristas estánorientadas (flechas). Cada arista se representa
entre paréntesis, separando sus vértices por comas y teniendo en cuenta (Vi, Vj) ≠ (Vj, Vi).
Los grafos pueden representarse de varias formas en unacomputadora:

 Listas adyacentes.
Cada vértice tiene una lista de vértices los cuales son adyacentes a él.
Representación del ejemplo:
(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 grafo se representa por una matriz de tamaño VxV,...