Arboles

Grafo conexo que no contiene ningún ciclo, existiendo siempre entre dos vértices una cadena.

Igualmente se denominan así a un procedimiento frecuentemente 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

• El grafo es conexo
• El grafo no tiene ciclos
• Si v es el número de vértices; v-1 será el número de aristas
• Si se agrega una lista entre 2 vértices no adyacentes se forma un ciclo.
• Si suprimimos una arista cualquiera, el grafo deja de ser conexo
• 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éticamente.

Gráficas 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 gráficas 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 gráfica 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 gráfica de la figura es igual a 4 caras, e igual a 8 aristas y 6 vértices, observe que F, E y V satisfacen la siguiente ecuación.

F=E-V+2

Diagrama 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

1.     Todo diagrama debe tener un inicio y un fin
2.     Del inicio solo puede salir un proceso
3.     El fin solo puede terminar un proceso
4.     Todas las figuras deben estar unidas

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 características 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 falso.

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 cualitativas.

Establecimiento de la existencia o no de una relación entre variables

A través 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, así como la inclusión o exclusión de posibilidades “se trata de logra la concientización 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

•        Leer el problema
•        Identificar las variables y la pregunta del problema
•        Elaborar la tabla
•        Leer el problema paso a paso, anotar o proteger la información
•        Inferir otras relaciones a partir de la información mutuamente excluyente
•        Releer el problema para relacionar datos postergados
•        Verificar la congruencia del razonamiento que se sigue

Teoría 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.

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.

 Dirección

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 vértice 

• El grado de un vértice es el número de aristas que se encuentran en ese vértice.
• Un circuito es una trayectoria que inicia y termina en el mismo vértice.
• 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.

Recursividad

Los bucles son unos de los pilares fundamentales de la programación, sin embargo, esto es posible construir programas sin utilizarlos. Algunos lenguajes no tienen alguna construcción explicita de bucles a diferencia del for, while, etc; si no que utilizan una técnica de programación conocida como recursividad.

Esta resulta ser una técnica muy poderosa para la solución de determinados problemas.

La recursividad significa aplicar una función como parte de la definición de esa misma función, la clave  de funcionamiento es que obligatoria mente debe de existir una condición terminal con el objeto de que la función se divulgue hacia una resolución no recursiva en algún punto, de lo contrario la función entra en un bucle infinito y nunca finaliza.

La matemática factorial se define como el producto de todos los números hasta el argumento inducido. El factorial de 1 es 1, si suponemos un poco nos daremos cuenta que tenemos otra manera de expresar esta función. El factorial de n es igual a n veces el factorial de n-1, por lo tanto…

1!=1

2!= 1*2=2

3!= 1*2*3=6

N!= 1*2*3*….(N-2)*(N-1)*N….

Ordenadas y No ordenadas

Comenzaremos con un recorrido por la combinatoria elemental contando diversas maneras se puede seleccionar un cierto número de elementos de un conjunto, para contar este número es preciso fijar los criterios de una selección a otra, aquí tendremos en cuenta 2 tipos de criterio, ele orden de los elementos y el número de veces que puede aparecer cada uno.

Si identifico 2 selecciones: Cuando tienen elementos diferentes o bien, cuando los elementos aparecen en un orden diferente hablaremos de permutaciones .En cambio si no distinguimos 2 selecciones que solo difieren en la ordenación de sus elementos, entonces hablaremos de combinaciones. Por otra parte, si cada elemento puede aparecer muchas veces, hablaremos de selecciones sin repetición, mientras que si no hay restricciones hablaremos de selecciones sin repetición.

Podemos formar 16 permutaciones con repetición de 2 elementos

• Puede repetirse 2 de los elementos pero solo una vez sin importar el orden

12 Permutaciones, sin repetición  de 2 elementos

• No pueden repetirse los elementos y no importa el orden de los elementos

• 10 Combinaciones, con repetición de 2 elementos

6 Combinaciones, sin repetición de 2 elementos

• No se repiten los elementos