Metodo de Grafos

METODO DE GRAFOS
El mtodo de Grafos juega un papel importante en la fundamentacin

matemtica de las Ciencias de la Computacin. Los grafos constituyen una
herramienta bsica para modelar fenmenos discretos y son fundamentales
para la comprensin de las estructuras de datos y el anlisis de algoritmos. En
matemticas y ciencias de la computacin, la teora de grafos estudia las
propiedades de los grafos, que son colecciones de objetos llamados vrtices (o
nodos) conectados por lneas llamadas aristas (o arcos) que pueden tener
orientacin (direccin asignada). Tpicamente, un grafo est diseado por una
serie de puntos (los vrtices) conectados por lneas (las aristas).
El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de

Knigsberg es considerado como uno de los primeros resultados de la teora de
grafos. Tambin se considera uno de los primeros resultados topolgicos en
geometra (que no depende de ninguna medida). Este ejemplo ilustra la
profunda relacin entre la teora de grafos y la topologa. En 1845 Gustav
Kirchhoff public sus leyes de los circuitos para calcular el voltaje y la corriente
en los circuitos elctricos. En 1852 Francis Guthrie plante el problema de los
cuatro colores que plantea si es posible, utilizando solamente cuatro colores,
colorear cualquier mapa de pases de tal forma que dos pases vecinos nunca
tengan el mismo color. Este problema, que no fue resuelto hasta un siglo
despus por Kenneth Appel y Wolfgang Haken, puede ser considerado como el
nacimiento de la teora de grafos. Al tratar de resolverlo, los matemticos
definieron trminos y conceptos tericos fundamentales de los grafos.
GRAFO
Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados
vrtices, y A es un conjunto de pares de vrtices, llamadas aristas.
En teora de grafos, slo queda lo esencial del dibujo: la forma de las aristas no
son relevantes, slo importa a qu vrtices estn unidas. La posicin de los
vrtices tampoco importa, y se puede variar para obtener un grafo ms claro.
Generalmente, se considera que colocar los vrtices en forma de polgono

regular da grafos muy legibles. Prcticamente cualquier red puede ser
modelada con un grafo: una red de carreteras que conecta ciudades, una red
elctrica o un alcantarillado.
ARISTAS DIRIGIDAS Y NO DIRIGIDAS
En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si

se quiere representar la red de las calles de una ciudad con sus inevitables
direcciones nicas. El conjunto de aristas ser ahora un subconjunto de todos
los posibles pares ordenados de vrtices, con (a, b) (b, a). Los grafos que
contienen aristas dirigidas se denominan grafos orientados, como el siguiente:
Las aristas no orientadas se consideran bidireccionales para efectos prcticos
(equivale a decir que existen dos aristas orientadas entre los nodos, cada una
en un sentido). Se considera la caracterstica de "grado" (positivo o negativo)
de un vrtice, como la cantidad de aristas que llegan o salen de l; para el caso
de grafos no orientados, el grado de un vrtice es simplemente la cantidad de
aristas que tocan este vrtice. Por ejemplo, el grado positivo (salidas) de d es
3, mientras que el grado negativo (llegadas) de b es 1.
Grafos isomorfos Dos grafos tendrn la misma forma matemtica cuando la
nica diferencia entre ambos, en cuanto a su estructura, sea la representacin
grfica de sus vrtices y aristas. Cuando las conexiones entre vrtices tengan
las mismas aristas, se dice que son homorfos.
Subgrafo Un grafo G1 es subgrafo de otro G si todos los vrtices de G1 estn

en G pero no necesariamente todos los vrtices de G estn en G1.
DIAGRAMA DE GANTT
El diagrama de Gantt es una til herramienta grfica cuyo objetivo es exponer el tiempo de
dedicacin previsto para diferentes tareas o actividades a lo largo de un tiempo total
determinado. A pesar de esto, el Diagrama de Gantt no indica las relaciones existentes entre
actividades.
MARCO TEORICO
Dada la posicin de cada tarea a lo largo del tiempo hace que se puedan identificar dichas
relaciones e interdependencias. Fue Henry Laurence Gantt quien, entre 1910 y 1915,
desarroll y populariz este tipo de diagrama en Occidente.1 2
Por esta razn, para la planificacin del desarrollo de proyectos complejos (superiores a 25
actividades) se requiere adems el uso de tcnicas basadas en redes de precedencia
comoCPM o los grafos PERT. Estas redes relacionan las actividades de manera que se puede
visualizar el camino crtico del proyecto y permiten reflejar una escala de tiempos para facilitar
la asignacin de recursos y la determinacin del presupuesto. El diagrama de Gantt, sin
embargo, resulta til para la relacin entre tiempo y carga de trabajo.
En gestin de proyectos, el diagrama de Gantt muestra el origen y el final de las
diferentesunidades mnimas de trabajo y los grupos de tareas (llamados summary
elements en la imagen) o las dependencias entre unidades mnimas de trabajo (no mostradas
en la imagen).
Desde su introduccin los diagramas de Gantt se han convertido en una herramienta bsica
en la gestin de proyectos de todo tipo, con la finalidad de representar las diferentes fases,
tareas y actividades programadas como parte de un proyecto o para mostrar una lnea de
tiempo en las diferentes actividades haciendo el mtodo ms eficiente.
Bsicamente el diagrama est compuesto por un eje vertical donde se establecen las
actividades que constituyen el trabajo que se va a ejecutar, y un eje horizontal que muestra en
un calendario la duracin de cada una de ellas.
CREANDO DIAGRAMAS DE GANTT
Se puede elaborar un diagrama de Gantt con una hoja de clculo de una manera muy sencilla,
marcando determinadas celdas para formar la representacin de cada tarea. Existen macros
que automatizan esta elaboracin en MS Excel y Libre/OpenOffice Calc. Sin embargo, existen
herramientas de gestin de proyectos dedicadas a la planificacin y seguimiento de tareas,
que utilizan el diagrama de Gantt como pantalla principal. Se introducen las tareas y sus
procesos no son capaces de producir una representacin de dichas tareas en el tiempo en el
formato del grfico de Gantt. Tambin existen herramientas de licencia libre capaces de llevar
a cabo dicho tipo de operacin. Se deben valorar, por ltimo, el uso de herramientas que usan
una pgina web y el navegador para realizar el seguimiento de proyectos.

Metodo de Grafos

Cargado por

Copyright:

Formatos disponibles

Metodo de Grafos

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Metodo de Grafos

Cargado por

Copyright:

Formatos disponibles

METODO DE GRAFOS

El mtodo de Grafos juega un papel importante en la fundamentacin

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de

Generalmente, se considera que colocar los vrtices en forma de polgono

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si

Subgrafo Un grafo G1 es subgrafo de otro G si todos los vrtices de G1 estn

También podría gustarte