Árboles.

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

Elementos de un árbol.

Raíz: Vértice del que salen 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 brote: Es cuando entran más arcos de los que salen.

Nodo eslabón: Nodo del que salen y entran igual cantidad de arcos.

Nodo eslabón simple: Es el que entra en un arco y sale en otro.

Propiedades de los árboles.

a) El grafo es conexo.

b) El grafo no tiene ciclos.

c) Si 'v' es el número de vértices; V-1 será el número de aristas.

d) Si suprimimos una arista cualquiera, el grafo deja de ser conexo.

e) Si se agrega una arista entre los dos vértices no adyacentes se forma un ciclo.

f) Para cada par de vértices hay una sóla cadena que los conecte.

En cumplimiento  de dos cuales quiera de estas propiedades define a un árbol. 

Isomorfismo.

Las siguientes instrucciones se dan a dos personas que no pueden ver el papel de la otra: Dibuje y etiquete 5 vertices con las siguientes letras: a, b, c, d, e. Conecte a con b, b con c, c con d, d con e y e con a.

Las gráficas producidas se aprecian en las siguientes figuras, sin duda estas figuras definen la misma gráfica aún cuando parezcan diferentes, se dice que estas gráficas son isomorfas.

La gráfica G1 yG2 son isomorfas si existe una función d 1 a 1 y sobre de los vértices de G1 a los vértices de G2, de manera que una arista E es insidente en v y w en G1 si sólo si la arista G (E) es insidente en f(v) y f(w) en G2. El par de funciones de f y g reciben el nombre de isomorfismo de G1 y G2.

Tres ciudades C1, C2 y C3 deberan conectars en forma directa mediante autopistas como cada una de las otras 3 ciudades C4, C5 y C6. Puede diseñarse este sistema de carreteras de manera que la autopista no se crucen. La siguiente figura ilustra un sistema en el que las autopistas se cruzan.

Una gráfica es plana si se puede dibujar en el plan 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 un límite el ciclo (5, 2, 3, 4, 6, 1) y en el límite de la cara c es el ciclo (1, 2, 5,1). La cara exterior d se considera limida  por el ciclo (1, 2, 3, 4, 6, 1) La gráfica de la figura tiene f= 4 caras, e= 8 aristas. v= 6 vertices.

Obserbe que f, e y v satisfacen la ecuación f =  e - v + 2.

En 1752 Euler provó que la ecuación se cumple para cualquier gráfica con hexapiana.

Problemas de los puentes de Königsberg

El primer artículo referente a la teoría de gráficas fue de Leonard Euler en 1736. El artículo presentaba una teoría general que incluía una solución a lo que ahora se llama el proble de los puentes de Königsberg.

Dos islas en el río Pregel en Königsberg estaban conectados entre sí y con las orillas de ríos por puentes, como se aprecia en la siguiente figura. El problema es comenzar en cualquier lugar de A, B, C ó D; cruzar cada puente exactamente una vez; luego regresar al lugar de inició.

La configuración de los puentes se puede modelar como una gráfica, como se ve en la siguiente figura: Los vértices representan los lugares y las aristas representan los puentes. El problema de los puentes de Königsberg ahora se reduce a encontrar un ciclo en la figura que incluya todas las aristas y todos los vértices. En honor a Euler, un ciclo es una gráfica que incluye todas las aristas y vértices de g se llama ciclo de Euler.

A partir del análisis en la sección se ve que no hay un circuito de Euler en la gráfica de la figura porque hay un número impar de aristas, incidentes en cada vértice. 

Tablas lógicas.

Construcción de tablas lógicas para la solución de problemas.

En esta clase de problemas, se maneja otra tipo de variables, la variable lógica, esta tiene dos características fundamentales:

1. La primera expresa una presencia o ausencia de una relación cierta entre dos variables y por tanto sólo puede tomar los valores verdadero y falso.

2. Son mutuamente excluyentes, es decir, que una vez que se da una relación sienta entre los valores de dos variables, no puede ocurrir otra relación verdadera entre los valores de ese mismo par de variables.

Esta estrategia se utiliza para resolver problemas de dos variables cualitativas, sobre las cuales pueden definirse una variable lógica con base a la verdad o falsedad de las relaciones entre las variables cualitativas.

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

A través de variados procesos de pensamiento se establece la relación o no entre las variables, cómo por ejemplo, se emplea la deducción, la inducción, la comparación, las inferencias así como la intuición o la exclusión de posibilidades, se trata de lograr concientización de las estrategias mediante el analisis y verbalización de los procesos utilizados para llevar a cabo la representación.

Pasos de la estrategia para resolver problemas de tablas lógicas.

1. Leer el problema. 

2. Identificar variables y la pregunta del problema.

3. Elaborar la tabla. 

4. Leer el problema paso a paso, anotar y postergar la información.

5. Inferir otras relaciones a partir de la relación que se tiene de los datos y de la relación mutuamente excluyente.

6. Reeler el problema para relacionar los datos portegados.

7. Verificar la congruencia del razonamiento que se siguió.

Relaciones mutuamente excluyentes.

Una característica importante de las tablas lógicas en la relación mutuamente excluyente esta se observa cuando determinamos la operación entre dos 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 que también se verdaderas.

Por ejemplo:

Si decimos que Pablo trabaja como vendedor de libros y que a Lucía le gusta la lectura y queremos determinar que compró Lucia a Pablo en tres variables, que son libros, pan o ropa encontramos la relación entre lectura y libros, entonces se excluye toda posibilidad de que haya otra variable y que también sea cierta. 

Información incompleta.

Cuando hablamos de información incompleta en un problema nos referimos a que dentro del texto no se encuentran todos los datos, elementos o variables para poder 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 me hacen falta y extraerlos a partir de la información que si tengo.

Es muy fácil expresar "a este problema le falta datos" o "No se puede resolver" o pide esto y no tiene la información y en ocasiones los alumnos dan por hecho que el problema esta mal redactado o que esta incompleto, pero no es así. Sólo hay que ser más observador y poner en práctica nuestro pensamiento inductivo deductivo, así como actuar de manera sistemática para descubrir los datos faltantes. 

Ejemplo: 

Luis, Pedro y Juan tienen Jugos diferentes en el receso, los jugos son de piña, melón y mora, Luis no tomo jugo de piña, tampoco de Mora, Pedro no tomo jugo de Mora. ¿De qué sabor tomó Juan su jugo? 

Circuito de Euler y circuitos de Hamilton.

Sea G un grafo sin vértices aislados. Un circuito que tiene todas las aristas de G recibe el nombre de Circuito de Euler. Un circuito euleriano es una trayectoria que empieza y termina en el mismo vertice y recorre cada arista exactamente una vez.

Teorema.

Si G es un grafo contiene un circuito euteriano si y sólo si:

• G es un conexo.
• Cada vértice de G es de grado par.

Entonces si G (un grafo) tiene un grado de vértice de grado 1 no puede tener circuitos (x - x  no se repite arista). Tampoco tiene grado impar porque no se puede salir y entrar en n par de veces 

Trayectoria de Euler.

 Debe comenzar en un vertice de grado impar y termina en otro.

Teorema de Euler.

a) Si una gráfica tiene más de dos vértices de grado impar, entonces no puede tener una trayectoria d Euler.

b)  Si una gráfica conexa tiene exactamente dos vértices de grado par, entonces tiene por lo menos una trayectoria de Euler. Cualquier circuito de Euler debe iniciar en uno de los vértices y terminar en el otro.

Grado de un vértice.

a) El grado de un vértice  es el número de aristas que se encuentran en ese mismo 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 por una trayectoria. Si una gráfica no es conexa se le denominará como disconexa, a los pedazos de unas gráficas se les llamará componentes. 

 

Grafos.

Es una estructura que posee elementos de una sola estructura relacionados por vínculos de una misma base, a estos elementos llamaremos puntos y lineas.

El diagrama representativo de un grafo es una figura constituida por puntos unidos entre sí, por segmentos o flechas. Los diagramas de flujos y los árboles son casos particulares de grafos.

Dirección.

En ciertos gráficos se indica la dirección de las líneas con una flecha originándose hacía los grafos no orientados.

Los gráficos en los que las lineas no tienen dirección se denominan grafos norentados.

Arista.

Linea que conecta dos puntos en un grafo norentado.

Arco.

Linea con dirección que conecta dos puntos en un grafo orientado.

Binomio

Se utiliza la formula: a² + 2 ab + b², por ejemplo:

(x + 4)² = x² + 8x + 16

(3ab - 5x²)² = 9a²b² - 30 abx² + 25x^4.