sábado, 28 de noviembre de 2015

ARBOLES

Grafo conexo que no contiene ningún ciclo, existiendo siempre entre dos vértices una cadena.
Igualmente se denominan así a un procedimiento frecuente mente utilizado para tratar problemas de enumeración y probabilidad.

Elementos de un árbol
·         Raíz: Vértice del que sale uno o más arcos pero no entran.
·         Brote: Vértice en el que termina uno o más arcos, pero del que no sale ninguno.
·         Nodo raíz: Es cuando salen más arcos de los que entran.
·         Nodo eslabón simple: Es el que entra en arcos y salen de otro.

Arboles binarios
/Propiedades
a)      El grafo es conexo
a)      El grafo no tiene ciclos
b)      Si v es el número de vértices; v-1 será el número de aristas
c)       Si se agrega una lista entre 2 vértices no adyacentes se forma un ciclo.
d)      Si suprimimos una arista cualquiera, el grafo deja de ser conexo
e)      Para  cada par de vértices hay una sola cadena que los conecta.


El cumplimiento de 2 cualesquiera de estas propiedades define un árbol. Con frecuencia se usa un árbol raíz para especificar relaciones jerárquicas. Cuando se usa un árbol de esta manera si un vértice A esta en un nivel uno menos que el nivel de vértice B y A y B son adyacentes, entonces A esta “justo arriba” de B o B es subordinado. Un ejemplo de este tipo de árbol que es el organigrama administrativo de la organización de una Universidad hipotética mente.

GRAFICAS PLANAS


Tres ciudades C1, C2, C3 deberán conectarse en forma directa mediante autopistas con cada una de otras 3 ciudades C4, C5, C6. 

¿Puede diseñarse un sistema de manera que las autopistas no se crucen, la figura anterior ilustra un sistema d las autopistas?
Una gráfica es plana si se puede dibujar en el plano sin que sus aristas se crucen. Al diseñar circuitos impresos es deseable tener el menor número de cruces posibles; así, el diseñador de circuitos impresos se enfrenta con el problema de graficas planas. Si una gráfica plana conexa se  dibuja en el plano, este se divide en regiones contiguas llamadas caras. Una cara se caracteriza por el ciclo que forma su frontera. Por ejemplo en la siguiente grafica la cara A tiene como límite el ciclo (5, 2, 3, 4,5) el límite de la cara C es el ciclo (1, 2, 5,1). La cara exterior se considera limitada por ciclo (1, 2, 3, 4, 6,1). La grafica de la figura es igual a 4 caras, e igual a 8 aristas y 6 vértices, obsérvese que F, E y V satisfacen la siguiente ecuación.

Diagramas de flujo



El diagrama de flujo es la forma más tradicional para representar gráficamente los detalles algorítmicos de un proceso. El diagrama de flujo utiliza una serie de símbolos gráficos con un significado especial.
Bases para desarrollar diagramas de flujo
·         Todo diagrama debe tener un inicio y un fin
·         Del inicio solo puede salir un proceso
·         El fin solo puede terminar un proceso
·         Todas las figuras deben estar unidas

viernes, 27 de noviembre de 2015

CONSTRUCCIÓN DE TABLAS LÓGICAS PARA LA SOLUCIÓN DE PROBLEMAS


En esta clase de problemas se maneja la variable lógica, esta tiene 2 caracteristicas fundamentales.
La primera expresa una presencia o ausencia de una relación cierta entre 2 variables y por tanto solo pueden tomar los valores de verdadero y fals.
La segunda, que son mutuamente excluyentes, es decir que una vez que se da una relación cierta entre las dos variables, no pueden ocurrir otra relación verdadera entre los valores de ese mismo para de variables.
Esta estrategia se utiliza para resolver problemas de 2 variables cualitativos, sobre las cuales pueden definirse una variable lógica con base a la veracidad de falsedad de las relaciones entre las variables cualitativos.
Establecimiento de la existencia o no de una relación entre variables
A travez de varios procesos de pensamiento se establece la relación o no entre las variables, p/e: se emplea la deducción, inducción, comparación, las inferencias, asi como la inclusión o exclusión de posibilidades “se trata de logra la consientisacion de las estrategia mediante el análisis y verbalismo de los procedimientos utilizados para llevar acabo los procedimientos.
Pasos para la estrategia para resolver problemas de tablas lógicas
1.       Leer el problema
2.       Identificar las variables y la pregunta del problema
3.       Elaborar la tabla
4.       Leer el problema paso a paso, anotar o proteger la información
5.       Inferir otras relaciones apartir de la información mutuamente excluyente
6.       Releer el problema para relacionar datos postergados

7.       Verificar la congruencia del razonamiento que se sigue
RELACIONES MUTUAMENTE EXCLUYENTES

Una característica importante de las tablas lógicas es la relación mutuamente excluyente, esta se observa cuando determinamos la relación entre 2 variables que es correcta y verdadera. esta relación excluye de las otras variables la posibilidad que se establezca una relación con ellas y también sea verdadera, p/e: "Si decimos que Pablo trabaja como vendedor de libros y que a Lucia le gusta la lectura y queremos determinar que compro lucia a Pablo en 3 variables ¿Que son, libros, pan o ropa?, encontraremos la relación entre lectura y libros, entonces se excluye otra posibilidad de que haya otra variable y que también sea cierta".

INFORMACIÓN INCOMPLETA

Cuando nos referimos a una información incompleta en un problema, nos referimos a que dentro del texto no se encuentran todos los elementos o variables para resolver el problema, esto no implica que el problema no tenga solución simplemente que hay que emplear la mente lógica para deducir que elementos o variables que hacen falta y extraerlos a partir de la información que si tengo.
Es muy fácil expresar "A este problema le hacen falta datos" o "pide esto y no tiene la información" y en ocasiones los alumnos dan por hecho que el problema esta mal redactado o incompleto pero no es así. Solo se tiene que ser mas observador y poner en practica nuestro pensamiento deductivo-inductivo, así como actuar de manera sistematica para descubrir los datos faltantes.

GRAFO


Es una estructura que posee elementos de una sola estructura, relacionados por vínculos de una misma base, a estos elementos les llamaremos puntos y líneas.
El diagrama representativo de un grafo es una figura constituida por puntos unidos entre sí, por segmentos o flechas. Los diagrama de flujo y los árboles son casos particulares de grafos.


DIRECCION: En ciertos gráficos se inserta la dirección de las líneas con una flecha, originándose hacia los grafos no orientados.
Los gráficos en los que las líneas no tienen dirección se le denominan gráficos no orientados.
ARISTA: línea que conecta dos puntos en un grafo no orientado

ARCO: línea con dirección que conecta con 2 puntos en un grafo orientado.


GRADO DE UN VERTICE


a)      El grado de un vértice es el número de aristas que se encuentran en ese vértice
b)      Un circuito es una trayectoria que inicia y termina en el mismo vértice

c)       Una gráfica es conexa si cualquiera de sus vértices se pueden unir con una trayectoria, si una gráfica no es conexa se le denominara DISCONEXA, a los pedazos de una gráfica se le denominara componentes


TEORIA DE GRAFOS


Circuitos de Euler y circuitos de Hamilton sean un G un grafo sin vértice aislados un circuito que contiene todas las aristas de G recibe el nombre de circuito euleniano.

Un circuito euleriano es una trayectoria que empieza y termina en el mismo vértice y recorre cada arista exactamente una vez.

TEOREMA: Son grafos
G contiene un circuito euleriano si y solo si
·         G es conexo
·         Cada vértice de G es de grado par