ARBOLES, PROPIEDADES, SISTEMAS

ARBOLES

ÁRBOLES

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

Ejemplo:

¿Cuáles de los grafos de la figura 6.2  son árboles?

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 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 cualesquiera de estas propiedades define a un árbol.

SISTEMAS OPERATIVOS DE COMPUTADORA

Los sitemas operativos de las computadoras modernas organizan las carpetas y los archivos usando una estrictira de árbol. Una carpeta contiene otras carpetas y archivos. La figura muestra el explorador de Windows con él despliegue de carpeta a la izquierda y los archivos a la derecha en una computadora en particular. La figura ilustra la misma estructura como un árbol con raíz. La raíz se llama Desktop (escritorio). Abajo de Desktop están My Computer, Internet Explorer, y otros (My computer es lo único desplegado en la figura 9.1.7). Abajo de My Computer están 3 un medio Floppy (A:), Micron (C:) y otros que no se muestran. Abajo de plug-ins, que están resaltados están los archivos Afill32.api, aform.js y otros, que aparecen a la derecha de la figura 9.1.7.

GRÁFICAS PLANAS

GRÁFICAS PLANAS

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 dircuitos impresos se enfrenta con el problema de gráficas planas.

Si una gráfica plana convexa 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 (cinco, dos, tres, cuatro, cinco) y el límite de la cara C es el ciclo (uno, dos, cinco, uno). La cara exterior D se considerada limitada por el ciclo (uno, dos, tres, cuatro, seis, uno). La gráfica de la figura tiene f=4 caras, e=8 aristas y v=6 vértices. Obsérvece que f,e y v satisfacen la ecuación f=e-v+2.

En 1972, Euler probó que la ecuación se cumple para cualquier gráfica conexa plana.

f=e-v+2

f=8-6+2

4=2+2

4=4

ISOMORFISMO DE GRAFOS

 ISOMORFISMO DE GRAFOS

Definición:

Dos grafos G1 y G2 son isomorfos si existe una función biyectiva f entre los vértices de G1 y G2, y una función biyectiva g entre lados de G1 y G2 tales que un lado e es incidente a v y w en G1 si solo si el lado g(e) es incidente a los vértices f (v) y f (w) en G2. Al par de funciones f y g se le denomina isomorfismo.

Ejemplo:

Sean los siguientes grafos G1 y G2

Un isomorfismo para los grafos anteriores G1 y G2 esta definido por:

f (a) = A

f (b) = B

f (c) = C

f (d) = D

f (e) = E

y g(Xi) = Yi, i = 1, ... , 5

CONSTRUCCIÓN DE TABLAS

 CONSTRUCCIÓN DE TABLAS

Lógica para la solución de problemas.

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

1. Expresa una presencia o ausencia de una relación cierta entre dos variables y por tanto solo pueden tomar los valores verdadero y falso

2. La segunda, son mutuamente excluyentes, es decir, que una vez que se da una relación cierta entre los valores de dos variables, no puede ocurrir otra relación verdadera entre los valoresde 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 varios procesos de pensamiento se establece la relación o no entre las variables, como por ejemplo, se emplea la deducción, la inducción, la comparación, las diferencias así como la intuición o exclusión de posibilidades, se trata de lograr concientización mediante el análisis y la verbalización de los procedimientos utilizados para llevar a cabo.

 

TEOREMA DE EULER

TEOREMA DE EULER

A) si una gráfica tiene más de dos vértices de grado impar, entonces no puede tener una trayectoria de euler.

B) si una gráfica convexa 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 de grado por si termina en el otro.

A) el grado de un vértice es el número de aristas que se encuentra en ese vértice.

B) un circuito es una trayectoria que inicia y termina en el mismo vértice.

C) una gráfica es convexa si cualquiera de sus vértices se puede unir por una trayectoria. Si una gráfica no es convexa se le denominará como disconexa, a los pedazos de una gráfica se les llamará componentes.

Postulados

CIRCUITOS DE EULER Y DE HAMILTON

CIRCUITOS DE EULER Y DE HAMILTON

CIRCUITO DE EULER

Sea G un grafo sin vértices aislados, un circuito que tiene 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.

Teorema: Si G es un grafo, G contiene un circuito euleriano si y solo si:

-G es un conexo

-Cada vértice de G es de grado par

Entonces si G (un grafo) tiene un 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 vértice de grado impar y terminar en otro.

Hamilton (1805-1865) inventó (y patentó) un juego en el que se trataba de hacer un recorrido por 20 ciudades (vértices) del mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30 aristas, formando el grafo de un icosaedro.

Un circuito hamiltoniano, o de Hamilton, es un grafo G es un camino que comienza y termina en un mismo vértice, pasando exactamente una vez por cada vértice.

CICLO DE HAMILTO

Hamilton (1805-1865) inventó (y patentó) un juego en el que se trataba de hacer un recorrido por 20 ciudades (vértices) del mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30 aristas, formando el grafo de un icosaedro.

Un circuito hamiltoniano, o de Hamilton, es un grafo G es un camino que comienza y termina en un mismo vértice, pasando exactamente una vez por cada vértice.

GRAFOS

GRAFOS

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 diagramas de flujo 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 hacia los grafos no orientados.

Los gráficos en los que las líneas no tienen dirección se denominan grafos no orientados.

Arista: línea que conecta dos puntos en un grafo no orientado.

Arco: Línea con dirección que conecta dos puntos en un grafo orientado.

                

Aristas

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.
Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.
Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
Cruce: Son dos aristas que cruzan en un punto.

Vértices

Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.
Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
Vértice Aislado: Es un vértice de grado cero.

Vértice Terminal: Es un vértice de grado 1.