Grafos Art

Universidad ECCI Rubén Darío Velandia, Estructura de programación Multígrafos

Estructuras de Datos Dinámicos
Grafos
Multígrafos
Velandia Triviño Rubén Darío
rastben@hotmail.com
Universidad ECCI

Abstract: In this article the definition of graphs is
presented as a structure of dynamic programming ,
which arises from the need to relate nodes , with the
sole purpose of optimizing the algorithmsused in
programming. Multigraph focusing on a structured
graph subclass using multiple loops and edges or
links between nodes . Concluding and highlighting
the effectiveness of the use of this theory for his great
might of abstraction and simple representation not
only in the design phase and postulation if not also in
solving a problem.
Keyword --Graphs , Nodes, Edges

Resumen: En este artículo sepresenta la
definición de grafos como una estructura de
programación dinámica, que surge con la necesidad
de relacionar nodos, con el único fin de optimizar los
algoritmos
empleados
en
programación.
Enfocándonos en el multígrafo como una subclase de
grafo estructurado que utiliza bucles y múltiples
aristas o enlaces entre nodos. Concluyendo y
resaltando la eficacia de la utilización de esta teoríapor su gran poderío de abstracción y sencilla
representación no solo en la fase de diseño y
postulación si no también en la solución de un
problema.

En programación
un grafo se define como
una estructura gráfica que expresa algorítmicamente
la unión de diversos puntos (Nodos) a través de lazos
que reciben el nombre de aristas. Los grafos se
utilizan en diversas disciplinas pues simbolizanmúltiples elementos de la realidad cotidiana que
requieren interacción entre sí.
II. GRAFO
Etimológicamente la palabra grafo deriva del griego
graphein, que transcribe grabar o escribir.
Partiendo de esto el grafo (G) es una dupla
ordenada de N y A, donde N es el conjunto finito de
vértices o nodos del grafo y A son elementos
compuestos por subconjuntos de N de carnalidad (2)
definiéndose como Aristas.Dichos vértices de X se denomina X1, X2....Xn, y
siempre deben ser representados como puntos, así la
notación G = N (N, A) nos permite identificar per se
un grafo.

Palabras clave -- Grafos, Nodos, Aristas
I. INTRODUCCION
La teoría de los grafos surge gracias Leonhard Euler
y su teoría "Solutio problematis ad geometriam situs
pertinentis" en la cual se intentaba establecer un
recorrido queatravesara los siete puentes del Rio
Pregel sin tener que pasar nuevamente por alguno
de ellos. Teoría que a su vez dio origen al ciclo
euleriano. Posterior a eso Gustav Kirchhoff, Francis
Guthrie,
Kenneth Appel y Wolfgang Haken
complementaron y fortalecieron la teoría de los
grafos constituyendo la definicon que actualmente se
utiliza.

Figura I. Representación de un grafo

En cuanto a los nodos odirección es importante
resaltar que este puede tener varios o ningún arista
relacionado, mas sin embargo toda arista por regla

Universidad ECCI Rubén Darío Velandia, Estructura de programación Multígrafos

debe unir exactamente a dos nodos. Es decir los
grafos representan conjuntos de objetos que no
tienen restricción de relación entre ellos.

llamados aristas o líneas, las cuales pueden ser
dirigidaso no conformando un multidigrafo mixto
G:=(V,E,A)

III. CLASIFICACION GRAFOS
Es así que teniendo en cuenta lo anterior
encontramos diversos subtipos de grafos que se
adaptan a las necesidades y requerimientos de
dirección como lo es el Grafo simple.
El Grafo simple es aquel recibe una sola arista
uniendo dos vértices, es decir que una arista que une
dos nodos. Esto es equivalente a decir que unaarista
cualquiera es la única que une dos vértices
específicos. Es la definición estándar de un grafo.
Por otro lado encontramos el grafo orientado o
dirigido en el cual las aristas poseen una dirección
específica representada por una flecha. En estos
casos U es una familia de
Pares ordenados resultantes del producto cartesiano
de X.
U ⊆ XxX = { ui = (xk, xj): 1 ≤ i ≤ |U|, 1 ≤ j, k ≤ |X|,
xk,...