Bueno, vamos a dar inicio (acompañados de algo de b
uena musica) a este material de investigacion respecto a los algoritmos, primeramente, definamos el termino, Algoritmo; En matemáticas, ciencias de la computación y disciplinas relacionadas, un algoritmo (del griego y latín, dixit algorithmus y éste a su vez del matemático persa Al Juarismi ) es un conjunto preescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generen dudas a quien deba realizar dicha actividad. Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la algoritmia.
En la vida cotidiana, se emplean algoritmos frecuentemente para resolver problemas. Algunos ejemplos son los manuales de usuario, que muestran algoritmos para usar un aparato, o las instrucciones que recibe un trabajador por parte de su patrón. Algunos ejemplos en matemática son el algoritmo de la división para calcular el cociente de dos números, el algoritmo de Euclides para obtener el máximo común divisor de dos enteros positivos, o el método de Gauss para resolver un sistema lineal de ecuaciones.
Teoria de grafos en general
La teoría de grafos ayudará a resolver problemas que se puedan representar mediante una red o grafo: camino mínimo, inventarios, etc.
La Teoría de Grafos proporciona algoritmos eficientes para resolver problemas en distintos campos de la ciencia.
La eficiencia puede medirse en función de:
i) La capacidad de almacenamiento requerida.
ii) El tiempo de ejecución: complejidad.
La complejidad depende del número de operaciones elementales f(n) y de la dimensión del problema n.
Damos, a continuación una serie de definiciones.
Definición 1.1. Un grafo G es un triple conjunto (V (G); A(G); I(G)) donde:
V (G) es un conjunto cuyos elementos son llamados vértices.
A(G) es otro conjunto cuyos elementos son llamados aristas o arcos.
I(G) es una relación (la relación de incidencia), que le asocia a cada arista a∈A(G) dos vértices, llamados los extremos de a.
Los arboles de grafos de esta manera son un grafo en el que existe un único nodo desde el que se puede acceder a todos los demás y cada nodo tiene un único predecesor, excepto el primero, que no tiene ninguno. También podemos definir un árbol como:
- Un grafo conexo y sin ciclos.
- Un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices.
Un árbol consta de un nodo raíz del que vamos a partir, de manera que con los restantes nodos se puedan formar conjuntos disjuntos de nodos de forma que cada subconjunto sea a su vez un árbol. En un árbol todo par de vértices se encuentra unido mediante una cadena y sólo una. Los árboles son estructuras de tipo jerárquico.
El algoritmo de Solin
Una vez definidos estos conceptos, ya podemos definir lo que representará nuestro algoritmo de Solin, Este algoritmo obtiene el árbol minimal de un grafo mediante la representación matricial, matriz de coste, del grafo. Consta de los pasos siguientes:
1) Marcamos el elemento de valor mínimo. En el caso de que existan varios, tomamos uno cualquiera. Se elimina la columna que posea el valor marcado y marcamos la fila correspondiente a la columna eliminada.
2) Del conjunto de elementos de las filas marcadas y que no hayan sido eliminados, tomamos aquel de valor mínimo y lo marcamos. Se elimina la columna que posea este valor marcado.
3) Reiteramos el proceso desde el punto 2) hasta que no podamos seleccionar más valores.
Ejercicio de prueba: Determinaremos con el siguiente grafo, el árbol minimal que podamos hallar usando el algoritmo indicado de Solin
La matriz asociada al grafo es:
Siguiendo los pasos del algoritmo llegamos a la matriz final:
En la matriz anterior, la matriz columna recoge el orden de los pasos que se han seguido para obtener la matriz definitiva:
La matriz anterior reprensentada gráficamente es:
Asi tenemos el resultado de nuestro arbol utilizando el metodo algoritmico, el mismo puede tener diversas aplicaciones en una investigación operativa mas avanzada, ademas del método presente, podemos denotar el método de kruskal. que de igual manera, buscara hacer del grafo un arbol minimal.
uena musica) a este material de investigacion respecto a los algoritmos, primeramente, definamos el termino, Algoritmo; En matemáticas, ciencias de la computación y disciplinas relacionadas, un algoritmo (del griego y latín, dixit algorithmus y éste a su vez del matemático persa Al Juarismi ) es un conjunto preescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generen dudas a quien deba realizar dicha actividad. Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la algoritmia.En la vida cotidiana, se emplean algoritmos frecuentemente para resolver problemas. Algunos ejemplos son los manuales de usuario, que muestran algoritmos para usar un aparato, o las instrucciones que recibe un trabajador por parte de su patrón. Algunos ejemplos en matemática son el algoritmo de la división para calcular el cociente de dos números, el algoritmo de Euclides para obtener el máximo común divisor de dos enteros positivos, o el método de Gauss para resolver un sistema lineal de ecuaciones.
Teoria de grafos en general
La teoría de grafos ayudará a resolver problemas que se puedan representar mediante una red o grafo: camino mínimo, inventarios, etc.
La Teoría de Grafos proporciona algoritmos eficientes para resolver problemas en distintos campos de la ciencia.
La eficiencia puede medirse en función de:
i) La capacidad de almacenamiento requerida.
ii) El tiempo de ejecución: complejidad.
La complejidad depende del número de operaciones elementales f(n) y de la dimensión del problema n.
Damos, a continuación una serie de definiciones.
Definición 1.1. Un grafo G es un triple conjunto (V (G); A(G); I(G)) donde:
V (G) es un conjunto cuyos elementos son llamados vértices.
A(G) es otro conjunto cuyos elementos son llamados aristas o arcos.
I(G) es una relación (la relación de incidencia), que le asocia a cada arista a∈A(G) dos vértices, llamados los extremos de a.
Los arboles de grafos de esta manera son un grafo en el que existe un único nodo desde el que se puede acceder a todos los demás y cada nodo tiene un único predecesor, excepto el primero, que no tiene ninguno. También podemos definir un árbol como:
- Un grafo conexo y sin ciclos.
- Un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices.
Un árbol consta de un nodo raíz del que vamos a partir, de manera que con los restantes nodos se puedan formar conjuntos disjuntos de nodos de forma que cada subconjunto sea a su vez un árbol. En un árbol todo par de vértices se encuentra unido mediante una cadena y sólo una. Los árboles son estructuras de tipo jerárquico.
El algoritmo de Solin
Una vez definidos estos conceptos, ya podemos definir lo que representará nuestro algoritmo de Solin, Este algoritmo obtiene el árbol minimal de un grafo mediante la representación matricial, matriz de coste, del grafo. Consta de los pasos siguientes:
1) Marcamos el elemento de valor mínimo. En el caso de que existan varios, tomamos uno cualquiera. Se elimina la columna que posea el valor marcado y marcamos la fila correspondiente a la columna eliminada.
2) Del conjunto de elementos de las filas marcadas y que no hayan sido eliminados, tomamos aquel de valor mínimo y lo marcamos. Se elimina la columna que posea este valor marcado.
3) Reiteramos el proceso desde el punto 2) hasta que no podamos seleccionar más valores.
Ejercicio de prueba: Determinaremos con el siguiente grafo, el árbol minimal que podamos hallar usando el algoritmo indicado de Solin
La matriz asociada al grafo es:
Siguiendo los pasos del algoritmo llegamos a la matriz final:
En la matriz anterior, la matriz columna recoge el orden de los pasos que se han seguido para obtener la matriz definitiva:
La matriz anterior reprensentada gráficamente es:
Asi tenemos el resultado de nuestro arbol utilizando el metodo algoritmico, el mismo puede tener diversas aplicaciones en una investigación operativa mas avanzada, ademas del método presente, podemos denotar el método de kruskal. que de igual manera, buscara hacer del grafo un arbol minimal.
No hay comentarios:
Publicar un comentario