Algoritmos

La resolución de un problema por medio de una computadora requiere de un conjunto de instrucciones precisas. Este conjunto de instrucciones se conoce como algoritmo. Un algoritmo obedece a una serie a una serie de instrucciones precisas, enunciadas de forma que una máquina podría manejarlas fácilmente para resolver un problema. Ejemplo de algoritmo que sirve para determinar el valor máximo.

El algoritmo busca en una sucesión dada s(1), s(2),…s(n) el valor máximo y lo proporciona con el nombre de LARGE.

1.[inicialización] sea I:=1 y LARGE:=s(1) (I indica el elemento de la sucesión que se estudia en ese momento)
2.[¿se encontró el máximo?] si s(1)>LARGE, entonces (si se haya un valor entonces hay que actualizar
3.[¿terminó?] si I=N entonces ha terminado (el máximo es el número correspondiente a LARGE)
4.[continua la búsqueda] I:= I+1 pasar a la instrucción 2

Este algoritmo consiste en una sucesión finita de instrucciones (cuatro) que resuelven el problema cada una de las cuatro instrucciones indica precisamente qué acción realizar.

Cada instrucción contiene una descripción breve de su propósito encerrada entre corchetes [ ]. Se colocarán entre ( ) y donde se considere necesario, algunos comentarios que ayudarán a comprender parte de la instrucción.

El operador de asignación se denota “:=” y así A:=B significa que la variable A se le asigna el valor de B el signo “=” se usa solamente en proposiciones condicionales.

Un algoritmo es un conjunto limitado (o finito) de instrucciones que tienen las siguientes características:
1. Precisión. Las instrucciones se enuncian de manera precisa
2. Univocidad. Los resultados intermedios correspondientes a cada paso de ejecución están definidos unívocamente y solo dependen de los datos de entrada y los resultados de los pasos anteriores
3. Finitud. El algoritmo termina después de una serie finita de instrucciones
4. Datos de entrada (input). El algoritmo recibe datos que ingresan
5. Datos de salida (output). El algoritmo producen datos que egresan
6. Generalidad. El algoritmo se aplica a una serie de datos de entrada. Las instrucciones de un algoritmo tienen un enunciado lo suficientemente preciso para convertirse en:

Teoría de los grafos

Definición un grafo (o bien un grafo no dirigido) G consiste en un conjunto V de vértices (o nodos) y un conjunto E de lados (o ramas) tales que cada lado e ? E está asociado a un par no ordenado de vértices. Si un lado e está asociado a un único par de vértices v y w, se escribe e=(v,w) o tambien e=(w,v).

En este contexot (v,w) denota un lado de un grafo no dirigido y no un par ordenado de números.
Un grafo dirigido G consiste en un conjunto v de vértices y un conjunto de E lados tales que cada lado e ? E está asociado a un par ordenado de vértices. Si un lado e está asociado a un par ordenado único de vértices v y w, se escribe e=(v,w). Se dice qe un lado e=(v,w) de un grafo dirigido (dirigido o no dirigido) es incidente en v y w . se dice que los vértices v y w son incidentes en e y también que son vértices adyacentes. Si G es un grafo y un conjunto de lados E se escribe G=(V,E). Si no se hace otra especificación los conjuntos E y V se suponen finitos.

En la figura anterior el grafo G consiste en el conjunto {S,T,U,V,W,X,Y,Z} de vértices y el conjunto {e1,e2,…en} de lados. El lado e1 está asociado con el par ordenado no ordenado de vértices {s,x}. El lado e, se denota por (T,U) o bien (U,T). El lado e4 es incidente en Y,Z y los vértices Y y Z son adyacentes

Los lados paralelos son lados distintos asociados a los mismos vértices Lazo es un lado asociado al mismo vértice. Grafo simple es un grafo que no tiene lazos ni lados paralelos.

Problema de los puentes de Könisberg

El problema consiste en partir desde cualquier lugar A,B,C,D; seguir caminando y pasar por cada uno de los puentes exactamente una vez, luego volver al punto de partida. Tal ruta se llama circuito o recorrido de Euler. Valencia o grado de un vértice es el número de los lados incidentes en V.

Teorema: si el grado tiene un vértice de grado impar entonces no existe un circuito de Euler.

Si se puede partir de cualquier lado exactamente una vez y volver al punto de partida, todos los vértices deben tener grado par.

En cada circuito de Euler se pasa por cada lado exactamente una vez. En un circuito de Hamilton o Hamiltoniano se pasa por cada vértice exactamente una vez.
Un grafo regular es aquel en el que cada vértice tiene la misma valencia o grado. Un grafo completo es aquel cuyos vértices se encuentran unidos, ejemplo:

Teoría de grafos

A diferencia de las situación relacionada con los circuitos de Euler, no hay condiciones necesarias y suficientes para la existencia de los circuitos de hamilton en un gráfico se puedan verificar con facilidad. El grafo que tiene n vértices y cada vértice es adyacente a todos los demás (sin lazos ni lados paralelos) se denomina grafo completo de n vértices y de denota grafo completo d n vértices y se denota por Kn.
Encuentra:
a) el conjunto de V vértices
b) el conjunto de de E lados
c) la valencia de cada vértice
d) si existe un circuito de Euler, determinalo

V={v1,v2,v3,v4,v5,v6,v7,v8,v9} E={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}
V1=2 V2=2 V3=3 V4=6 V5=5 V6=3 V7=6 V8=4 V9=3

Los circuitos de hamilton son llamados así en honor a Sir William Rowan Hamilton quien patentó un juego con la forma de un dodecaedro. Cada esquina del dodecaedro representa una ciudad. Trata de viajar a todas las ciudades pasando solo una vez por cada una y volver al punto de partida. El grafo se representa así:

Circuito de Hamilton.

Problema del vendedor viajero.
Dado un conjunto de ciudades y la distancia entre cada par de ellas, obtener la ruta más corta que pase por cada ciudad exactamente una vez y termine en el punto de partida.

ac, cd,de, eb,ba dc,cb,be,ea,ad

Sistema

Consiste en lograr la conexión entre todos los vértices del grafo eliminando los caminos o lados que no sean necesarios, el objetivo es unir los vértices en forma directa o indirecta.


	Algoritmos
	La resolución de un problema por medio de una computadora requiere de un conjunto de instrucciones precisas. Este conjunto de instrucciones se conoce como algoritmo. Un algoritmo obedece a una serie a una serie de instrucciones precisas, enunciadas de forma que una máquina podría manejarlas fácilmente para resolver un problema. Ejemplo de algoritmo que sirve para determinar el valor máximo. El algoritmo busca en una sucesión dada s(1), s(2),…s(n) el valor máximo y lo proporciona con el nombre de LARGE. 1.[inicialización] sea I:=1 y LARGE:=s(1) (I indica el elemento de la sucesión que se estudia en ese momento) 2.[¿se encontró el máximo?] si s(1)>LARGE, entonces (si se haya un valor entonces hay que actualizar 3.[¿terminó?] si I=N entonces ha terminado (el máximo es el número correspondiente a LARGE) 4.[continua la búsqueda] I:= I+1 pasar a la instrucción 2 Este algoritmo consiste en una sucesión finita de instrucciones (cuatro) que resuelven el problema cada una de las cuatro instrucciones indica precisamente qué acción realizar. Cada instrucción contiene una descripción breve de su propósito encerrada entre corchetes [ ]. Se colocarán entre ( ) y donde se considere necesario, algunos comentarios que ayudarán a comprender parte de la instrucción. El operador de asignación se denota “:=” y así A:=B significa que la variable A se le asigna el valor de B el signo “=” se usa solamente en proposiciones condicionales. Un algoritmo es un conjunto limitado (o finito) de instrucciones que tienen las siguientes características: 1. Precisión. Las instrucciones se enuncian de manera precisa 2. Univocidad. Los resultados intermedios correspondientes a cada paso de ejecución están definidos unívocamente y solo dependen de los datos de entrada y los resultados de los pasos anteriores 3. Finitud. El algoritmo termina después de una serie finita de instrucciones 4. Datos de entrada (input). El algoritmo recibe datos que ingresan 5. Datos de salida (output). El algoritmo producen datos que egresan 6. Generalidad. El algoritmo se aplica a una serie de datos de entrada. Las instrucciones de un algoritmo tienen un enunciado lo suficientemente preciso para convertirse en: Teoría de los grafos Definición un grafo (o bien un grafo no dirigido) G consiste en un conjunto V de vértices (o nodos) y un conjunto E de lados (o ramas) tales que cada lado e ? E está asociado a un par no ordenado de vértices. Si un lado e está asociado a un único par de vértices v y w, se escribe e=(v,w) o tambien e=(w,v). En este contexot (v,w) denota un lado de un grafo no dirigido y no un par ordenado de números. Un grafo dirigido G consiste en un conjunto v de vértices y un conjunto de E lados tales que cada lado e ? E está asociado a un par ordenado de vértices. Si un lado e está asociado a un par ordenado único de vértices v y w, se escribe e=(v,w). Se dice qe un lado e=(v,w) de un grafo dirigido (dirigido o no dirigido) es incidente en v y w . se dice que los vértices v y w son incidentes en e y también que son vértices adyacentes. Si G es un grafo y un conjunto de lados E se escribe G=(V,E). Si no se hace otra especificación los conjuntos E y V se suponen finitos. En la figura anterior el grafo G consiste en el conjunto {S,T,U,V,W,X,Y,Z} de vértices y el conjunto {e1,e2,…en} de lados. El lado e1 está asociado con el par ordenado no ordenado de vértices {s,x}. El lado e, se denota por (T,U) o bien (U,T). El lado e4 es incidente en Y,Z y los vértices Y y Z son adyacentes Los lados paralelos son lados distintos asociados a los mismos vértices Lazo es un lado asociado al mismo vértice. Grafo simple es un grafo que no tiene lazos ni lados paralelos. Problema de los puentes de Könisberg El problema consiste en partir desde cualquier lugar A,B,C,D; seguir caminando y pasar por cada uno de los puentes exactamente una vez, luego volver al punto de partida. Tal ruta se llama circuito o recorrido de Euler. Valencia o grado de un vértice es el número de los lados incidentes en V. Teorema: si el grado tiene un vértice de grado impar entonces no existe un circuito de Euler. Si se puede partir de cualquier lado exactamente una vez y volver al punto de partida, todos los vértices deben tener grado par. En cada circuito de Euler se pasa por cada lado exactamente una vez. En un circuito de Hamilton o Hamiltoniano se pasa por cada vértice exactamente una vez. Un grafo regular es aquel en el que cada vértice tiene la misma valencia o grado. Un grafo completo es aquel cuyos vértices se encuentran unidos, ejemplo: Teoría de grafos A diferencia de las situación relacionada con los circuitos de Euler, no hay condiciones necesarias y suficientes para la existencia de los circuitos de hamilton en un gráfico se puedan verificar con facilidad. El grafo que tiene n vértices y cada vértice es adyacente a todos los demás (sin lazos ni lados paralelos) se denomina grafo completo de n vértices y de denota grafo completo d n vértices y se denota por Kn. Encuentra: a) el conjunto de V vértices b) el conjunto de de E lados c) la valencia de cada vértice d) si existe un circuito de Euler, determinalo V={v1,v2,v3,v4,v5,v6,v7,v8,v9} E={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16} V1=2 V2=2 V3=3 V4=6 V5=5 V6=3 V7=6 V8=4 V9=3 Los circuitos de hamilton son llamados así en honor a Sir William Rowan Hamilton quien patentó un juego con la forma de un dodecaedro. Cada esquina del dodecaedro representa una ciudad. Trata de viajar a todas las ciudades pasando solo una vez por cada una y volver al punto de partida. El grafo se representa así: Circuito de Hamilton. Problema del vendedor viajero. Dado un conjunto de ciudades y la distancia entre cada par de ellas, obtener la ruta más corta que pase por cada ciudad exactamente una vez y termine en el punto de partida. ac, cd,de, eb,ba dc,cb,be,ea,ad Sistema Consiste en lograr la conexión entre todos los vértices del grafo eliminando los caminos o lados que no sean necesarios, el objetivo es unir los vértices en forma directa o indirecta.