Arboles y S.O. de una computadora

ARBOLES

Grafo conexo que no contiene 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 salen 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 arboles

A)   El grafo es conexo

B)   El grafo no tiene ciclos

C)   Si V es número de vértices; V -1 será número de aristas

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

E)   Si suprimimos una arista cualquiera el grafo deja de ser conexo

F)   Para cada par de vértices hay una sola cadena que los conecte

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

La figura muestra resultados  de las semifinales y finales de la competencia de tenis clásico en Wimbledom, que incluyo cuatro de los mejore jugadores de la historia de tenis.
En Wimbledom, cuando un jugador pierde sale del torneo.
Los ganadores siguen jugando hasta que queda una persona: EL campeón

SISTEMAS OPERATIVOS DE UNA COMPUTADORA


Los sistemas operativos de las computadoras modernas organizan las carpetas y los archivos usando una estructura de árbol .Una parte contiene otras carpetas de archivos .La figura muestra el explorador de Windows  con el despliegue de carpetas a  la izquierda a los archivos a la derecha a una computadora en particular .La figura ilustra la misma estructura de un árbol con raíz , la raíz desktop .Abajo de desktop esta maketo  mi computer esta tres medios floppy (A:), micro ( C:) y otras que no se muestran . Abajo de ´plug insertada, están los archivos AFF: 1132 .apl.aform.js y otros, que aparecen a la derecha de la figura .

Gráficas planas

GRAFICAS PLANAS

Tres ciudades C1,C2 y C3 deberían conectarse en forma directa mediante autopistas cada una de estas tres ciudades C1 y C6. Pueden diseñarse este sistema de carreteras de qué manera que las autopistas no se cruzan.

Una gráfica es una 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 encuentra con el problema de graficas planas.
Si una gráfica Plana conexa  se dibuja, esto se divide en regiones contiguas llamadas cara. Una cara se caracteriza por el ciclo que forma su frontera .Por Ejemplo, en la siguiente grafica la Cara A la Cara C es el ciclo  .La  cara D se considera limitada por el ciclo, La grafica por la que F EV satisface la ecuación F =E-V+2

Isomorfismo

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 sig. letras: A, B, C, D y E; conecte A con B, B con C, C con D, D con E, A con E.

B

                                                 A                                              C

                                                 E                                           D

Las graficas se aprecian en las sig figuras, sin duda estas figuras definen la misma grafica aun cuando parescan diferentes; se dice que estas graficas son isomorfas.

La grafica G1 y G2 son isomorfas si existe una función F uno a uno y sobre de los vértices G1 a los vértices G2 y aristas de G2, de manera que una arista E es incidente en V y donde G2.

Si y solo si donde la arista G(B) es incidente 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.

                                  A                                                                A

                                                               

                X1                             X2                 C                                                D

         E                                                    B

X5                                         X3

                 D            X4               E                          E                                 B

                                      

Problema de los puentes de Königsberg

PROBLEMA DE LOS PUENTES DE KÖNIGSBERG


El 1er artículo referente a las teorías de graficas fue de Leonhard Euler  en 1936; el artículo recitaba una teoría general que incluía una solución a lo que ahora se llama el problema de los puentes de Königsberg.
Dos islas en el rio Pregel en Königsberg (ahora Kaliningrado, Rusia) estaban conectadas entre sí y con las orillas de rio por puentes, como se aprecia en la sig. Figura. El problema es comenzar en cualquier lugar de A, B, C o D; cruzar cada puente exactamente una vez; luego regresar al lugar de inicio.
La configuración de los puentes se puede moderar como una gráfica, como se ve en la sig. 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 gráfica de la figura que incluya todas las aristas y todos los vértices. En honor a Euler, en un ciclo una gráfica que incluye todas las aristas G se llama ciclo Euler

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

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

En esta clase de problemas se maneja otro 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  solo pueden tomar los valores de verdadero y falso.

2.    La segunda, que son mutuamente excluyentes, es decir, que una vez que se evade una relación   cierta entre dos 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 los 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  y 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, por ejemplo, se crea la deducción, la intuición, la comparación, las inferencias, así como la exclusión de posibilidades, “se trata del lugar concientización de las estrategias mediante el análisis  y la verbalización de los procedimientos utilizados para llevar acabo"

Pasos de 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 y postergar la información

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

6.    Releer el problema para relacionar los datos postergados

7.    Verificar la congruencia del razonamiento que se siguió

Relaciones mutuamente congruentes

Una característica importante  de las tablas lógicas es la relación mutuamente siguiente, estas se observa cuando  determinamos la relació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 que sea verdadero.

Por ejemplo. Si decimos que Pablo trabaja como vendedor de libros y a  que Lucia le gusta la lectura queremos determinar que compro Lucia  a Pablo en tres variables, que son libros, pan o ropa. Encontramos la relación entre lectura y libros, entonces excluye toda posibilidad de que hay otra variable y que también sea cierto. 

Información incompleta

Cuando hablamos de información incompleta en un problema,  nos referimos 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 ampliar la mente lógica  para deducir que elementos o variables me hacen falta y extraerlos a partir de la información que nos hace falta.

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

Diagrama de flujo

PARTES DEL DIAGRAMA DE FLUJO

Circuito de Euler y Circuito de amilton

CIRCUITO DE EULER Y CIRCUITO DE HAMILTON

Sea G un Grafo  sin vértices aislados  un circuito que tienen todas las aristas  de G recibe el nombre de circuito euleriano  un circuito euleriano es una trayectoria que empieza y termina en el mismo vértice y recorre cada arista exactamente una vez
Ej.


Teorema
Si G es un Grafo  g contiene un circuito Euleriano si y solo si

-       G es conexo

-       Cada vértice de G es de grado por

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

Aristas  E-D: Grado      E=1 una entrada  y/o salida

    D=3 entrada  y/o salida

-        Trayectoria  de Euler debe comenzar  en una vértice de grado  impar y terminar en otro

TEOREMA DE EULER

Si una gráfica tiene más de dos vértices de grado sin par, entonces no puede tener una trayectoria de Euler.

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

a)    El grado de un vértice es el número de aristas que se encuentra 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 cualquiera  de sus vértices  se puede unir por una trayectoria .Si una gráfica no es conexa se le denomina es discoteca, a los pedazos de una gráfica se les llamara componentes.