Matemáticas Discretas
De Computacion
El acelerado desarrollo tecnológico alcanzado en los últimos años las áreas de la computación y telecomunicaciones, de los cuales hemos sido testigos de estos sorprendentes avances; campos que han fundamentado su crecimiento en las ciencias puras siendo una de ellas las matemáticas, la misma que ha aportado con una variedad de temas que se encuentran incluidos dentro de las Matemáticas Discretas. Asignatura de Matemáticas Discretas que forma parte del plan de estudios de Ingeniería en Informática y que esta incluida dentro del pensum de estudios del Segundo Ciclo, con temas que proporcionan los conocimientos base, necesarios e indispensables para que los profesionales en formación puedan conocer y adentrarse en estas nuevas tecnologías, con un enfoque práctico, aplicado y computacional, además de un acentuado carácter formativo. Siendo las Matemáticas Discretas, la ciencia que trata sobre el conocimiento y explicación de fenómenos discretos y procesos finitos, que servirán para aplicaciones posteriores dentro de la formación de los futuros ingenieros en informática y al mismo tiempo permitirán conocer como trabajan estas modernas herramientas que son las computadoras y poder aprovechar su potencialidad para poder incursionar en áreas como de Sistemas y desarrollo de Software. Lo que hace que esta asignatura se plantee como respuesta a una variada serie de problemas de la «vida real» (diseño de bloques, flujo de redes, diseño de circuitos, asignaciones horarias o de tareas, ...), lo que le confiere el enfoque aplicado que señalamos arriba, aprendiendo el alumno, además, a buscar modelos matemáticos adecuados para gran número de situaciones diferentes, lo que suele ser muy habitual en el desarrollo profesional. Entre los principales aportes que nos brinda las Matemáticas Discretas a través de diversos métodos es ayudarnos a la creación de sistemas de elevada complejidad y que, sin embargo, alcancen los parámetros de eficiencia y eficacia deseados. El uso de métodos pero si bien formales no nos garantiza, a priori, la corrección del software, pero es una buena práctica que permite alcanzar mejores resultados en la construcción de sistemas complejos, ya que nos permite revelar inconsistencias, ambigüedades, etc. Dentro de este desarrollo nace la necesidad de un ajuste en el perfil de los profesionales que se dedican a la aplicación de la tecnología informática en las empresas y organizaciones; y, es ahí donde tenemos que sustentar los conocimientos necesarios e indispensables de nuestros profesionales que les permitan afrontar los retos del desarrollo. El carácter formativo de la asignatura se debe, no sólo al carácter formativo que tienen las Matemáticas en general sino, en concreto, a que el lenguaje y las herramientas que se usan en la asignatura son los habituales en gran parte de las asignaturas de la carrera como: programación, análisis de sistemas, etc. y en el desarrollo mismo de los profesionales en formación. Actualmente estamos asistiendo a una mejora de los métodos matemáticos para la verificación y especificación de sistemas de hardware y software de elevada complejidad; de hecho, muchos de estos métodos ya son capaces de afrontar ejemplos reales del mundo industrial. Esta mejora en los métodos se debe principalmente al desarrollo de nuevas metodologías y de nuevas y más potentes herramientas (como pueden ser mejores probadores de teoremas). Es difícil predecir, aún así, cual será el alcance, en el futuro, de estas técnicas; pero la situación permite un cierto optimismo que debería ser acompasado de un trabajo en investigación que permita que estas técnicas ayuden en mayor medida al mundo industrial. En el pasado el uso de estas técnicas no fue muy utilizado debido a los problemas que llevan asociados, como la dificultad de los métodos, su baja capacidad para escalar, etc. Actualmente estas técnicas están aumentando su grado de aceptación y mejorando su capacidad de éxito lo que convierte a los métodos formales en una técnica que no debemos dejar de tener en cuenta a la hora de buscar métodos para la creación de sistemas computacionales de calidad. La evolución de estos métodos y los frutos de la investigación que en ellos se está llevando a cabo nos dirán cual será el papel de estos métodos en la informática del futuro. La meta de esta asignatura es enseñar los elementos básicos de Matemáticas que, siendo importantes para la informática, no son cubiertos por los cursos tradicionales de Álgebra y Análisis Matemático, o por cursos más específicos de introducción a la programación y a la informática teórica. El programa trata de manera general materias de teoría de conjuntos, sistemas numéricos, estructuras algebraicas, combinatoria, teoría de grafos, árboles, modelos de redes y lenguajes. Se hace especial énfasis en principios generales tales como la inducción y la recursión. Esperamos que los alumnos adquieran la capacidad de aplicar los conceptos y técnicas aquí aprendidos en el contexto de otras asignaturas del plan de estudios. Uno de los temas que se tratan es la de los tipos de grafos más importantes, entre los que tenemos los árboles. Los árboles se utilizan en muchos campos de aplicación, como por ejemplo: en ciencias de la Computación, los árboles se utilizan para organizar la información de tal forma que sea posible efectuar eficientemente operaciones que involucren a esa información. Por otra parte, es frecuente que resulte muy posible el desglosar los problemas complejos y representarlos mediante una estructura en forma de árbol. Además, los árboles surgen en aplicación de redes que se modelan mediante grafos. Un ejemplo tipo lo encontramos en una red de comunicaciones, en la cual los nodos de la red esté conectada con el mínimo costo posible. Razones que nos han inducido a programar este curso, siguiendo el texto, de Matemáticas Discretas de Richard Johnsonbaugh, cuarta edición, por su enfoque didáctico por la claridad de sus contenidos y por la gran cantidad de ejercicios resueltos y propuestos.
Objetivos Generales
Al concluir el estudio de la asignatura, el estudiante estará en capacidad de:
- Comprender las nociones fundamentales de Matemáticas Discretas para analizar los problemas de diseño y desarrollo de programas basados en computadores.
Objetivos Especificos
- Realizar operaciones con conjuntos.
- Resolver problemas matemáticos relacionados con sistemas numéricos.
- Visualizar la aplicación de la Lógica Matemática relacionada en el contexto de las permutaciones y las combinaciones.
- Determinar los elementos y la representación de los conceptos relacionados con la teoría de grafos.
- Aplicar la teoría de grafos en el diseño de árboles y reconocer sus componentes y afines.
- Aplicar los fundamentos de redes para resolver algunos problemas de flujos.
- Aplicar los fundamentos de las máquinas de estado finito y relacionarlos con autómatas y lenguajes.
Bibliografia
BÁSICA
Se ha elegido como base para el presente curso el siguiente texto:
- JOHNSONBAUGH, Richard (2005): Matemáticas Discretas. Cuarta Edición. Prentice Hall Hispanoamérica México.
El texto Matemáticas Discretas cuarta edición incluye ejemplos, ejercicios, figuras, tablas, secciones relativas a la solución de problemas, notas, repaso y autoevaluacion en cada capitulo. El texto consta de 11 capítulos, de los que se ha elegido los capítulos y contenidos más sobresalientes de acuerdo al perfil de la carrera y de sus objetivos planteados. Las secciones NOTAS contienen sugerencias para lecturas posteriores. Las secciones REPASO DEL CAPITULO contienen por sección o unidad del capitulo listas de referencias para los conceptos claves. AUTOEVALUACION presenta ejercicios por cada sección cuyas respuestas aparecen al final del libro. Además, la mayor parte de los capítulos tienen secciones: Rincón de solución de problemas, sombreada para ser localizad fácilmente, con solo hojear el texto. Contiene 2400 ejercicios, identificados con ∂ los que podrían ser más difíciles, los ejercicios con números en cursiva (cerca de un tercio de ello) tienen una sugerencia o una solución al final del libro. El libro contiene cerca de 430 ejemplos resueltos, que muestran a los estudiantes la manera de cómo abordar problemas en matemáticas discretas y hacer demostraciones. El Rincón de Solución de Problemas tiene la intención de presentar diferentes formas de resolver un problema, presenta técnicas de solución y demostraciones. En resumen presenta el enunciado, analiza algunas formas de resolver el ejercicio, se enuncia las técnicas después de encontrar una respuesta; se presenta la solución formal y algunos comentarios del trabajo realizado.
COMPLEMENTARIA
Para consultar otros textos que disponen de algunos de los contenidos del programa que estudiamos en esta asignatura tenemos:
- LPSCHUTZ, Seymour. (1992): Matemáticas para Computación, Primera edición McGraw - Hill Interamericana de México S.A.
- KOLMA. Bernard y BUSBY Robert. (1984): Estructuras de Matemáticas Discretas para Computación, Prentice - Hall Hispanoamericana S.A. México.
El texto tiene una amplia gama de ejercicios a todos los niveles. Cada capítulo contiene un resumen de conceptos básicos para repaso y lectura complementaria. Las respuestas a los ejercicios de número impar aparecen al final del libro. Las soluciones a los ejercicios vienen en el Manual del Instructor que está disponible en inglés. Dispone de una gran cantidad de ejercicios resueltos y gráficos ilustrativos de cada uno de los temas en estudio.
Existen otras obras, las mismas que le pueden ayudar como material de consulta, y estas son:
- BOGART, Kenneth. P. (1996): Matemáticas Discretas, Editorial Limusa, México, 970 pag.
- GRIMALDI, Ralph P. (1997): Matemáticas Discretas y Combinatorias, Tercera edición, Editorial Addison-Wosley Iberoamericana EEUU, 874 pag.
- LIU, C.L. (1995): Elementos de Matemáticas Discretas, Editorial McGraw - Hill 232 pag.
Desarrollo del Aprendizaje
Capitulo 1 : MATEMÁTICAS PARA COMPUTACIÓN
La presente unidad corresponde a los capítulos 2 y 4 del texto básico. Iniciamos el estudio de conjuntos, concepto fundamental en matemáticas, incluso más que la operación de contar, pues se puede encontrar implícita o explícitamente, en todas las ramas de las matemáticas puras y aplicadas. En su forma explicita, los principios y terminología de los conjuntos se utilizan para construir proposiciones matemáticas más claras y precisas y para explicar conceptos abstractos como el infinito
CONJUNTOS
Sabemos que la palabra conjunto implica la idea de una colección de objetos que se caracterizan en algo común.
En matemática tiene el mismo significado, sólo que a estos objetos se les llama elementos o miembros del conjunto.
No puede darse una definición satisfactoria de un conjunto en términos de conceptos simples, por lo tanto la palabra «CONJUNTO» debe aceptarse lógicamente como un término no definido.
Un conjunto es una colección bien definida de objetos de cualquier clase.
Ejemplo:
A = {2,4,6,8,10}
Se lee: “A es el conjunto formado por los números 2, 4, 6, 8 y 10”.
Hay dos formas de determinar o describir conjuntos:
a) Por extensión ó Forma Tabular
- Se dice que un conjunto es determinado por extensión (o enumeración), cuando se da una lista que comprende a todos los elementos del conjunto y sólo a ellos.
- Ejemplo:
- A = { a, e, i, o, u }
- B = { 0, 2, 4, 6, 8 }
b) Por comprensión ó Forma Constructiva
- Se dice que un conjunto es determinado por comprensión, cuando se da una propiedad que la cumpla en todos los elementos del conjunto y sólo a ellos.
- Ejemplo:
- A = {x/x es una vocal}
- Se lee: “A es igual al conjunto de todas las x tales que x es una vocal”
- Ejercicios: Escribir la forma como se lee los siguientes conjuntos:
- B = {x/x es un número par menor que 10}
- Se lee: .........................................................
- C = {x/x es una letra consonante de la palabra “conjuntos”}
- Se lee: .........................................................
Los conjuntos tienen una amplia clasificación y la correspondiente notación y simbolismo para su representación.
Los conjuntos que mas nos interesan son los conjuntos numéricos, los mismos que son:
N = {0, 1, 2, 3, 4, 5, 6, ................}
Se lee: N es el conjunto formado por los números naturales
E = {..........., -3, -2, -1, 0, 1, 2, 3, ...........}
Se lee: E es el conjunto formado por los números enteros
Otros conjuntos que se pueden escribir en forma tabular y solamente a manera de ilustración ubicaremos algunos elementos son:
Q = {..... , -3/2, -1, -3/4, -1/2, -2/7, 0, 2/7, 1/2, 3/4, 1, 3/2, .....}
Se lee: Q es el conjunto formado por los números racionales
Se lee: R es el conjunto formado por los números reales
El conjunto de los números reales se puede representar mediante diagramas de Venn y diagramas lineales.
Ejemplos:
a) Pertenencia o no pertenencia de elementos
- A = {1, 3, 5, 7, 9}
- donde 5 ∈ A se lee: 5 pertenece al conjunto A
- y 4 ∉ A se lee: 4 no pertenece al conjunto A
b) Conjunto “Vacío”
- B = {n, o, v, e, l, a}
- Determinar el conjunto de las “vocales cerradas” que forman parte del conjunto B, el conjunto de vocales cerradas “C” esta dado por el conjunto VACÍO que se denota por “{ }” o sea C = { }
c) Conjunto finito: Si consta de un cierto número de elementos distintos, es decir si al contar los diferentes elementos del conjunto el proceso de contar puede acabar.
- Conjunto formado por las vocales: V = {a, e, i, o , u}
d) Conjunto infinito: Cuando no se puede contar sus elementos o es el que tiene principio pero no tiene fin.
- Conjunto formado los números naturales: N = {1, 2, 3, 4, 5, 6, .....}
e) Conjuntos iguales: Cuando ambos tienen los mismos elementos, es decir si cada elemento de A pertenece a B.
- Sean los conjuntos:
- A = {1, 2, 3, 4} B = {3, 4, 1, 2} A = B
- C = {1, 2, 3, 3, 4, 1} D = {1, 3, 2, 3, 1, 4,} C = D
- E = {x/x vocal de la palabra “mundo”} F = {u, o} E = F
f) Conjunto universo: Es el conjunto que contiene a todos los elementos del discurso. Es un término relativo, se le denota por la letra U.
- Sean los conjuntos: E = {mujeres} F = {hombres}
- Existe otro conjunto que incluye a los conjuntos E y F, que es:
- U = {seres humanos}
- Gráficamente se representa por un rectángulo tal como se observa a continuación
g) Conjunto potencia
- La familia de todos los subconjuntos incluido el mismo conjunto M y el conjunto vacío de un conjunto M dado, se llama Conjunto Potencia de M y que se denota por P(M), cuyo número de elementos de este nuevo conjunto P(M) esta dado por la expresión 2^n, donde n viene hacer el número de elementos del conjunto M.
- Ejemplos:
- En los siguientes ejercicios hallar el conjunto potencia del conjunto dado:
- 1) Sea el conjunto M={1,2}, hallar su conjunto potencia o sea P(M)
- El conjunto M tiene 2 elementos (), el número de elementos del conjunto potencia P(M) esta dado por 2^2=4 elementos, el resultado es:
- P(M)={{1},{2},{1,2},0}
- 2) Sea el conjunto A={a,b,c}, hallar su conjunto potencia o sea P(A)
- El conjunto A tiene 3 elementos (n=3), el número de elementos del conjunto potencia P(A) esta dado por 2^3=8 elementos, el resultado es:
- P(A)={{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c},0}
NOTA: Con la definición dada de conjunto potencia, podemos ahora determinar cuales son los “subconjuntos propios” de cualquier conjunto dado
- Los subconjuntos propios de cualquier conjunto, es el mismo conjunto potencia pero sin tomar en cuenta al mismo conjunto dado.
Con relación a los dos ejemplos anteriores, los subconjuntos propios de los conjuntos dados son:
a) Los subconjuntos propios del conjunto M={1,2} son:
- {1},{2},0 donde se puede ver que no se considera al subconjunto {1,2}
b) Los subconjuntos propios del conjunto son: A={a,b,c} son:
- {a},{b},{c},{a,b},{a,c},{b,c},0 donde no se considera al subconjunto {a,b,c}
- Ejemplos de operaciones con conjuntos
a) Unión de conjuntos: Se denota A ∪ B = {x/x ∈ A ∨ x ∈ B}
- Se pueden presentar los siguientes casos, en forma gráfica se representan:
- Dados los conjuntos A={0, 1, 2, 3, 4, 5} y B = {0, 2, 4}, efectuar la unión de conjuntos:
- A ∪ B = {0,1,2,3,4,5}
b) Intersección de conjuntos: Se denota por A ∩ B = {x/x ∈ A ∧ x ∈ B}
- Se pueden presentar los siguientes casos, en forma gráfica se representan:
- Dados los conjuntos: A = {0, 1, 2, 3, 4, 5} y B = {3, 5, 7}, efectuar la intersección de conjuntos:
- A ∩ B = {3, 5}
c) Diferencia de conjuntos: Se denota por A - B = {x/x ∈∧ x ∉ B}
- En forma gráfica se representa por:
- Dados los conjuntos: A = {a, b, c, d, e} y B = {a, e}, efectuar la diferencia de conjuntos:
- A - B = {b, c, d}
d) Diferencia simétrica de conjuntos: Se denota por A ∆ B = {x | x ∈ A ∨ x ∈ B ∧ x ∉ A ∩ B}
- La diferencia simétrica de dos conjuntos A y B, denotada por ∆ (que se lee “A diferencia simétrica B”, es el conjunto formado por los elementos que pertenecen a A o a B, pero no pertenecen a su intersección.
- Observe que las regiones sombreadas a la izquierda y a al derecha corresponden respectivamente a los conjuntos A – B y B – A, por esto también:
- A ∆ B = {A – B} ∪ {B – A}
- A ∆ B = {A ∪ B} - {B ∩ A}
- Dados los conjuntos A = {1, 2, 3, 4} y B = {4 ,5}, efectuar la diferencia simétrica de conjuntos:
- A ∆ B = {1, 2, 3, 5}
e) Conjunto complemento: Se denota por que se lee: “conjunto complemento de A”, y esta dado por , donde U representa el conjunto universo.
- Sea el conjunto universo U = {x/x es un número dígito} y el conjunto V = {0, 2, 4, 6, 8}; determinar el conjunto complemento de V o sea = {1, 3, 5, 7, 9}; gráficamente se representa por:
Para profundizar los conocimientos acerca de la Teoría de conjuntos, es necesario revisar los teoremas propuestos en el numeral 2.1 del texto base con los ejemplos que asocia, así como también resolver los ejercicios propuestos de las páginas 85 a la 87.
Actividades de Repaso
Las siguientes preguntas forman parte de la Autoevaluacion del Tema antes visto:
a) Dados los conjuntos A = {1, 2, 3, 4, 5, a, b, c, d} ; B = {e, f, g, h, 5, 6, 7} y C= {a, e, k, p, m, 5,} obtener:
- a. (A ∪ B) ∩ C
- b. ( A ∩ B) ∩ C
- c. (A ∪ B)’
- d. (A ∆ B)
- e. (A - B) ∪ C
b) Hallar todos los subconjuntos de M = {0, {{0}}}
PRODUCTO CARTESIANO
PARES ORDENADOS: intuitivamente un par ordenado (a,b) es un par de objetos en el cual el orden en el que estos se consideran debe ser: primero a y después b . Las letras a y b se llaman la primera y la segunda componentes, respectivamente, de la pareja ordenada.
Dos pares ordenados (a, b) y (c, d) son iguales si solo si
- a = c y b = d
PRODUCTO CARTECIANO: dados dos conjuntos A y B se llama producto cartesiano (o conjunto producto) de A y B, al conjunto de todos los pares ordenados (a, b) de tal forma que la primera componente a pertenece al conjunto A y la segunda componente b es elemento del conjunto B. Este conjunto se denota por A × B y se lee “A producto cartesiano de B”
Simbólicamente
- A × B = {(a, b) | a ∈ A ∧ b ∈ B}
Ejemplos
a) Si A = {a, b, c} ; B = {x, y}
- A × B = = {(a, x), (a, y), (b, x), (b, y), (c, x), (c, y)}
- Nótese que el conjunto tiene seis elementos
b) Si A = {1, 2, 3} ; B = {4, 5, 6}
- A × B = = {(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)}
- B × A = = {(4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3), (6, 1), (6, 2), (6, 2)}
- Nótese que en este ejercicio cada conjunto tiene nueve elementos, y que A × B ≠ B × A
En general, si n(A) = p y n(B) = q entonces, n(A × B) = n(B × A) = pq
Además, el producto cartesiano No es conmutativo, es decir A x B ≠ B x A a menos que A = B o que uno de los conjuntos sea vacío.
Si A y B son conjuntos finitos su producto puede ser representado en el plano cartesiano colocando el conjunto A en el eje horizontal, y B en el eje vertical. A cada par ordenado (a,b) le corresponde un punto del plano.
Por ejemplo, Si A = {a1, a2, a3, a4} y B = {b1, b2, b3} , el conjunto producto consta de 12 elementos o parejas, y en su representación gráfica deben aparecer 12 puntos que forman un red, así:
Otra forma de representar el producto A × B es mediante un diagrama de árbol.
Por ejemplo, si A = {1, 2 ,3} y B = {a, b}, la gráfica arborescente correspondiente a A × B, es:
Relaciones
Este tema se encuentra en el capítulo 3 en los numérales 3.1 y 3.2 paginas 116 y 125 del texto básico, por lo tanto le sugerimos revisar con detenimiento las definiciones, teoremas y ejemplos desarrollados en base a la teoría expuesta, ya que lo que a continuación se desarrolle en la guía coadyuvara a ampliar los términos expuestos en el libro base.
Se define una relación como un conjunto de pares ordenados.
Una relación (binaria) R de un conjunto X a un conjunto Y es un subconjunto del producto cartesiano X × Y. si (x, y) ∈ R escribimos xRy y decimos que x esta relacionado con y.
Una relación que es reflexiva, simétrica y transitiva en un conjunto X se llama relación de equivalencia sobre X.
Ejemplos
a) Sean los conjuntos X = {a, b, c, d} y Y = {1, 2, 3, 4}, definir una relación R de X en Y y determinar el dominio de R y lel rango de R.
- R = {(a, 1), (b, 2), (c, 3), (d, 4)}
- El dominio se define por el conjunto {x ∈ X/(x, y) ∈ R para algún y ∈ Y}
dominio de R es el conjunto {a, b, c, d}
b) La relación R sobre X = {1, 2, 3, 4} esta definida por “(x, y) ∈ R si x ≤ y“ es:
- R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
- el dominio de R es el conjunto {1, 2, 3, 4}
- el rango de R es el conjunto {1, 2, 3, 4}
- se concluye que: el dominio y el rango son iguales porque la relación está definida sobre el mismo conjunto X.
- La digráfica de la relación R es la siguiente:
Ejemplos de las propiedades de las relaciones
a) Reflexiva
- La relación R del ejemplo anterior dada por:
- R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
- se dice que es reflexiva por que cada elemento x ∈ X, (x, x) ∈ R; los pares ordenados (1, 1), (2, 2), (3, 3) y (4, 4) están en R. Si observamos la digráfica de la relación reflexiva, encontramos que tiene un lazo sobre cada vértice.
b) Simétrica
- Tomando la relación R del ejemplo anterior dada por:
- R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
- “no es simétrica”, por cuanto no cumple la definición que dice: “si para cada x, y ∈ X, si (x, y) ∈ R, entonces (y, x) ∈ R”.
c) Transitiva
- Tomando la relación R del ejemplo anterior dada por:
- R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
- “es una relación transitiva R sobre el cojunto X”, por cuanto cumple la definición que dice: “x, y, z ∈ X, si (x, y) y (y, z) ∈ R, entonces (x, z) ∈ R”.
- Específicamente tenemos (1, 2), (2, 3) se tiene (1, 3); (1, 3), (3, 4) se tiene (1, 4); (2, 3), (3, 4) se tiene (2, 4) todos pertenecen a R.
d) Antisimétrica
Tomando la relación R del ejemplo anterior dada por:
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
- “la relación R sobre el cojunto X es antisimétrica”, por cuanto cumple la definición que dice para toda: “x, y X, si (x, y) ∈ R y x ≠ y, entonces (x, y) ∉ R”. Específicamente tenemos (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) pertenecen a R, pero (2, 1), (3, 1), (4, 1), (3, 2), (4, 2), (4, 3) no pertenecen a R.
e) Inversa
- Tomando la relación R del ejemplo anterior dada por:
- R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}
- La relación inversa de R que se denota por R-1, esta dada por:
- R - 1 = {(1, 1), (2, 1), (3, 1), (4, 1), (2, 2), (3, 2), (4, 2), (3, 3), (4, 3), (4, 4)}
- Ejercicio 1
A partir del siguiente dígrafo, resuelva las siguientes instrucciones:
1. Escriba R como un conjunto de pares ordenados
- R ={(3, 5), (4, 4), (5, 5), (3, 5), (3, 4), (4, 5)}
2. Escriba una relación reflexiva sobre G1
- R = {(3,3), (4,4), (5,5)}
3. Escriba una relación simétrica sobre G1
- R = {(3,3), (4,4), (5,5)}
4. Escriba una relación antisimétrica sobre G1
- R = {(3, 5), (3, 4), (4, 5)}
5. Escriba una relación transitiva sobre G1
- R ={(3, 4), (4, 5), (3, 5)}
6. Escriba R-1 como un conjunto de pares ordenados
- R-1 = {(3, 3), (4, 3), (4, 4), (5, 4), (5, 5), (5, 3)}
Ejercicio 2
Considere las siguientes relaciones en W = {1, 2, 3, 4} y determinar si son reflexivas, simétricas, antisimétricas o transitivas.
R1 = {(1, 1), (1, 2)}
R2 = {(1, 1), (2, 3), (4, 1)}
R3 = {(1, 3), (2, 4)}
R4 = {(1, 1), (2, 2), (3, 3)}
R5 = {W x W}
Respuestas: Reflexivas: R5
- Simétricas: R4 y R5
- Antisimétricas: R1, R2, R3, R4
- Transitiva: R1, R2, R3, R4, R5
Matrices de relaciones
Este tema lo encontramos en la página 132, sección 3.3. Se describirá brevemente como formar una matriz de relación y se realizara ejemplos. Una matriz es una manera conveniente de representar una relación R de X a Y. Se etiquetan los renglones con elementos de X (en algún orden arbitrario), y se etiquetan las columnas con elementos de Y (orden arbitrario). Luego el elemento en el renglón x y la columna y se hace igual a 1 si xRy, y 0 de otra manera. Esta matriz se llama matriz de la relación R.
Ejemplos:
Formar la matriz de relación de los siguientes conjuntos:
a)
- R = {(1, b), (1, d), (2, c), (3, c), (3, b), (4, a)}
- Donde X = {1, 2, 3,4} y Y = {a, b, c, d}
- Considerando los ordenes: 1, 2, 3,4 y a, b, c, d tenemos la matriz:
b)
- X = {2, 3, 4} Y = {5, 6, 7, 8}
- Considerando las ordenes: 2, 3, 4 y 5, 6, 7,8; definida por xRy si x divide a y
Para los siguientes ejercicios vamos a determinar:
a) La matriz A_1 de la relación R_1 (con respecto de los órdenes dados)
b) La matriz A_2 de la relación R_2 (con respecto de los órdenes dados)
c) El producto matricial A_1 A_2.
d) Utilice el resultado de la parte c) para determinar la matriz de la relación R_2 o R_1.
e) Utilice el resultado de la parte d) para determinar la relación R_2 o R_1 (como un conjunto de pares ordenados).
Las relaciones dadas son:
R = {(1,x),(1,y),(2,x),(3,x)}
R_2 = {(x,b),(y,b),(y,a),(y,c)}
Órdenes: 1, 2, 3; x, y; a, b, c
Solución:
Las órdenes son los conjuntos que intervienen en las relaciones los mismos que los podemos escribir como:
X = {1, 2, 3} Y = {x, y} Z = {a, b, c}
Por tanto la matriz de una relación, es una representación de una relación cualesquiera R' de X a Y, para nuestro caso serían:
a) La matriz A_1 de la relación R_1, en este caso sería la relación R_1 de X a Y, la misma que esta dada por:
b) La matriz A2 de la relación R2, en este caso sería la relación R2 de Y a Z, la misma que esta dada por:
c) El producto de A1A2 es:
d) Para obtener matriz de la relación , del punto c) tenemos que reemplazar cada término distinto de cero en el producto de matrices A1A2 obtenida en el punto anterior, conforme lo señala el Teorema 2.6.6 de la página 117 del texto básico, la misma que quedaría como a continuación se señala:
e) El conjunto de pares ordenados de la relación esta dado por: si la matriz A1 de la relación R1 que se expresa como la relación R1 de X a Y, intervienen los conjuntos X e Y; mientras la matriz A2 de la relación R2 que se expresa como la relación R2 de Y a Z, intervienen los conjuntos Y e Z. De donde podemos concluir que los conjuntos u órdenes que intervienen en la relación son: el conjunto X de R1 y el conjunto Z de R2; donde el conjunto de pares ordenados es:
- R_2 o R_1 ={(1,a),(1,b),(1,c),(2,b),(3,b)} Respuesta
Ejercicios
Resolver los ejercicios 1 y 2 de la página 117 y ejercicio 16 de la página 118 del texto base.
SISTEMAS NUMERICOS
Este tema lo encontramos en la página 84 del texto base, es conveniente que usted lo revise previamente para sustentar de mejor manera lo que la guía trata de complementar y explicar en forma práctica. Los sistemas de numeración son conjuntos de dígitos o símbolos usados para representar cantidades, así se tiene los sistemas de numeración Decimal, Binario, Octal, Hexadecimal, Romano, etc. Los cuatro primeros se caracterizan por tener una base (numero de dígitos o símbolos diferentes que se utilizan para representar cantidades y estas bases son: 10, 2, 8 y 16). El sistema de numeración binario es el mas importante en los sistemas digitales, mientras el sistema decimal la importancia radica en que se utiliza universalmente para representar cantidades fuera de un sistema digital. Esto significa que habrá situaciones en las cuales los valores decimales tengan que convertirse en valores binarios antes de que se introduzcan en el sistema digital.
Estos son los sistemas de numeración mas utilizados ya que permiten explicar las operaciones y funciones que se cumplen al operar, codificar o programar tareas con el computador. Una computadora utiliza números binarios para calcular respuestas a un problema, luego los convierte a un valor decimal antes de mostrarlos en la pantalla. Además del Sistema Binario y decimal, otros dos sistemas de numeración encuentran amplias aplicaciones en los sistemas digitales. Los sistemas Octal (base 8) y Hexadecimal (base16) se usan con la misma finalidad, la de ofrecer un eficaz medio de representación de números binarios grandes.
Ejemplos en la manipulación de estos sistemas de numeración:
1. Sistema binario
- Convertir un número expresado en base 2 a base 10 y viceversa:
Conversión de Binario a Octal y viceversa
a) Para la conversión de enteros binarios a octales, a los bits del número binario se los agrupa en conjuntos de tres comenzando por la derecha. Luego, cada grupo se convierte a su equivalente octal, utilizando la tabla siguiente:
- Algunas veces el numero binario no tiene grupos de 3 bits completos. En estos casos, agregamos uno o dos ceros a la izquierda del número binario a fin de completar el último grupo. Esto se ilustra a continuación para el número binario 11010110_2.
- 11 010 110 completamos: 011 010 110 remplazamos como indica la tabla:
- 3 2 6
- luego el número buscado es: 326_8
b) Convertir el número octal 1235678 a binario, cada digito octal lo remplazamos por su correspondiente valor de la tabla anterior:
- 1 2 3 5 6 7
- 001 010 011 101 110 111 luego el número buscado es:
- 10100111011101112
Conversión de Binario a Hexadecimal y viceversa
a) Para la conversión de enteros binarios a hexadecimal, a los bits del número binario se los agrupa en conjuntos de cuatro comenzando por la derecha. Luego, cada grupo se convierte a su equivalente hexadecimal, utilizando la tabla siguiente:
- Algunas veces el numero binario no tiene grupos de 4 bits completos. En estos casos, agregamos uno, dos o tres ceros a la izquierda del número binario a fin de completar el último grupo. Esto se ilustra a continuación para el número binario 1001001111_2.
- 10 0100 1111 completamos: 0010 0100 1111
- remplazamos como indica la tabla: 2 4 F
- luego el número buscado es: 24F_16
b) Convertir el número hexadecimal 127A8316 a binario, cada digito hexadecimal lo remplazamos por su correspondiente valor de la tabla anterior:
1 2 7 A 8 3
0001 0010 0111 1010 1000 0011 luego el número buscado es:
100100111101010000011_2
Conversión de un número de cualquier base a base 10
El método consiste en multiplicar los valores equivalentes de los dígitos por su base elevada a su valor posicional y luego sumar estos productos.
Ejemplos:
a) Convertir el número en base 2357_8 a decimal
- posición: 3 2 1 0
- dígitos 2 3 5 7
- = (2 × 8^3) + (3 × 8^2) + (5 × 8^1) + (7 × 80)
- = 1024 + 192 + 40 + 7 = 1263_10
b) Convertir el número hexadecimal 3A1_16 a decimal
- posición: 2 1 0
- dígitos 3 A 1
- = (3 × 16^2)+(10 × 16^1)+(1 × 16^0)
- = 768 + 160 + 1 = 929_10
Conversión de un número en base 10 a cualquier otra base
El método consiste en dividir el número sucesivamente para la nueva base y se escribirán los restos de las divisiones en orden inverso al obtenido.
Ejemplos:
a) Convertir el número decimal 273_10 a base octal u 8
Ejercicios
Resuelva los ejercicios 6, 11, 23 de la página 90 del texto base, los mismos que le permitirán afianzar los conceptos y métodos de conversión.
EJEMPLOS DE OPERACIONES BINARIAS
Adicion
Para esta operación y mejor compresión tómese en cuenta el siguiente cuadro
a)
b)
Obsérvese que en la operación de 1 + 1 = 10 en base binario (102), que es el equivalente del 2 en sistema decimal.
Sustracción
Para la sustracción tómese en cuenta el siguiente cuadro, para mejor comprensión en la resolución de los ejemplos que se muestran.
a)
Es necesario considerar que si el minuendo es negativo la operación se convierte en una adición con el resultado negativo.
Multiplicación
Se presenta la tabla de multiplicación binaria:
a)
Para multiplicar números que tiene parte entera y parte fraccionaria se opera como en el sistema decimal. Para colocar el número binario se cuenta la cantidad de cifras fraccionarias tanto en el multiplicando como en el multiplicador; y en esta cantidad se separa en el producto o resultado.
Ejercicios
Resuelva el ejercicio 18 y 28 de la pagina 90 del texto base.
LAS FORMAS COMPLEMENTARIAS Y EL SIGNO
Las computadoras digitales almacenan los números binarios en registros conformados por dispositivos de almacenamiento denominados FLIP – FLOPS. Cada dispositivo almacena un bit. El signo se introduce con un bit adicional a la izquierda: 0 para los números positivos (+) y 1 para los números negativos ( - ) El sistema mas empleado para representar números binarios con signo es el de complemento a 2, y para considerarlo es necesario tener en cuenta que el complemento a 1 de un numero binario se obtiene cambiando cada bit del numero por su complemento. El complemento a 2 de un numero binario se halla tomado el complemento a 1 y sumándole una unidad al bit menos significativo. Por ejemplo para introducir un signo (+) al número 4310 y convertirlo en +4310 se agrega un bit 0 adelante así: 0101011_2 = + 43_10 Recuerde la conversión de decimal a binario. Para obtener el número negativo -43_10 se halla el complemento a 2 del número positivo, así:
El complemento a 2 se usa para representar números binarios con signo pues permite transformar sustracciones en adiciones. Esto es importante porque la computadora digital podrá hacer ambas operaciones empleando los mismos circuitos.
Al utilizar el complemento a 2 se pueden presentar cuatro casos:
1. Sumar dos números positivos.
2. A un número positivo sumar un número negativo menor o, lo que es lo mismo, efectuar la sustracción entre dos números positivos en donde el minuendo es mayor que el sustraendo.
3. A un número positivo sumar un número negativo mayor, es decir efectuar la diferencia entre dos números positivos en donde el minuendo es menor que el sustraendo.
4. Sumar dos números negativos.
Ejemplos
1. Sumar + 28 con + 13
2. Sumar + 28 con - 13
Considere que el bit de acarreo se desprecia. Por lo tanto la respuesta seria: 0001111
3. Sumar + 13 con - 28
4. Sumar -13 con -15
- El bit de acarreo se desprecia.
Ejercicios:
Realizar la sustracción de los siguientes números binarios con signo utilizando complemento a 2. Dar los resultados como números binarios con signo y como decimales:
a) 010111 - 000110
b) 110001 - 001000
EJEMPLOS DE OPERACIÓNES HEXADECIMALES
* Adicion
Para realizar la operación de adición hexadecimal se debe seguir las mismas reglas que la adición decimal, teniendo en cuenta que el digito de mayor valor es F. El siguiente procedimiento puede ser útil.
1. Sumar los dos dígitos hexadecimales en decimal, insertando el equivalente hexadecimal para números mayores que 9. 2. Si la suma es igual o menor que 15, ésta puede expresarse como digito hexadecimal. 3. Si la suma es mayor o igual que 16, se le resta 16 y se acarrea (lleva) un uno (1) hacia el digito de la siguiente posición.
Otra forma de sumar los números hexadecimales es convirtiéndolos primero a binarios, luego se realiza el proceso de adición binaria, y después se convierte el resultado en hexadecimal, como se lo ha aprendido.
* Sustracción
Para restar números hexadecimales se emplea el mismo método que para restar binarios. Es decir en vez de restar se suma el complemento a 2 del número hexadecimal. El sustraendo hexadecimal se complementa a 2 y luego se suma al minuendo. Si resulta acarreo (llevar uno) se desprecia.
Ahora se efectúa la suma:
Por lo tanto el resultado es: 448F_16. Recuerde que debe eliminar el bit de acarreo.
Ejercicios
Resuelva los ejercicios 32 y 37 de la página 91 del texto base.
PERMUTACIONES Y COMBINACIONES
En computación el ordenamiento lógico y riguroso es una norma que regula la programación, y funcionamiento de todas las actividades que realiza el experto en informática en general.
Nosotros queremos sugerirle algunas estrategias de ordenamiento en las diferentes cadenas y subcadenas que se forman cuando aplicamos la teoría combinatoria.
PERMUTACIONES
En esta sección haremos referencia al estudio y propiedades de los grupos que se pueden formar con un conjunto de n elementos dado, diferenciándose entre sí por el número de elementos que entran en cada grupo y por el orden de colocación de los mismos.
Una de las formas de conocer el número de ordenamientos diferentes que se pueden obtener de un conjunto de n elementos dados, es a través de las permutaciones.
La permutación de n elementos distintos X_1, X_2, .... X_n, esta dado por:
P_n = n! = n(n - 1)(n - 2)(n - 3) ...... 2.1 n! se lee “factorial de n”
Nota: En las permutaciones se debe considerar el orden de los elementos dentro de cada grupo.
Cuando se desea determinar el número de ordenaciones diferentes de “r elementos de entre n elementos distintos”, se conoce como “r-permutaciones de n elementos” y se denota por P(n, r) y esta dado por:
P(n, r) = n(n - 1)(n - 2) ...... (n - r + 1) para r ≤ n
Esta expresión se la puede expresar en términos factoriales:
Ejemplo:
Cuántas y cuales son las permutaciones que pueden realizarse con las letras {A, B, C}
Donde n = 3 P_n = n! = n.(n - 1).(n - 2) ..... 2.1
- P3 = 3! = 3.2.1 = 6
Las ordenaciones diferentes que se obtienen con tres letras diferentes son:
ABC ACB BAC BCA CAB CBA
Ejemplo:
Cuántas y cuáles son las permutaciones que se pueden hacer con las letras A, B, C, D; tomadas de 3 en 3.
Donde: P(n, r) = n(n - 1)(n - 2) ...... (n - r + 1) para r ≤ n
n = 4; r = 3 P(4, 3) = 4.3.2 = 24
Las ordenaciones diferentes que se obtienen con cuatro letras diferentes tomadas de 3 en 3 son:
ABC BAC CAB DAB
ABD BAD CAD DAC
ACB BCA CBA DBA
ACD BCD CBD DBC
ADB BDA CDA DCA
ADC BDC CDB DCB
Ejemplo
De cuántas maneras se pueden ordenar 10 personas tomadas de 4 en 4.
COMBINACIONES
Se llama combinación de n elementos tomados de r en r, al conjunto de todas las colecciones de r elementos dados, considerando distintas, dos colecciones cuando difieran en uno o más elementos.
Es una selección de objetos en la cual no interesa el orden es decir AB = BA.
El número de combinaciones de r elementos de un conjunto de n elementos distintos se denota C(n, r) y esta dado por:
Ejemplos:
Con los números 1, 2, 3, 4, 5 y 6, ¿Cuántas sumas diferentes de 3 sumandos cada una pueden hacerse?.
Razonamiento: Formamos una suma cualquiera con tres de las cifras dadas: (1 + 2 + 3) = 6, con los mismos números formamos otra suma (3 + 2 + 1) = 6, como las dos sumas son iguales, entonces el problema es una combinación, por no influir el orden de colocación de sus elementos.
Ejemplo:
Se tienen 4 pinturas de colores diferentes. ¿Cuantos colores pueden obtenerse mezclando los 4 colores en la misma proporción?.
Razonamiento: Se forma una mezcla con los 4 colores A + B + C + D = Color. Se forma otra mezcla con los 4 colores A + D + C + B = Color, se observa como las dos mezclas dan el mismo color puesto que no influye el orden de colocación de los elementos, entonces es una combinación.
Ejemplo:
¿Cuántas cadenas de 8 bits contienen exactamente cuatro unos?
COEFICIENTES BINOMIALES
El binomio (a + b)n, tiene que ver con las combinaciones, por cuanto los coeficientes del desarrollo de este binomio esta dado por la combinación C(n, r); el número de términos del desarrollo de un binomio elevado a una potencia n entero positiva, es igual a n + 1 términos. El desarrollo de un binomio esta dado por:
Por tanto podemos calcular cualquier término o término general k del desarrollo de (a + b)^n, que esta dado por:
T_{r + 1} = C(n, r)x^{n - r} y^r donde: k = r + 1 y r = k - 1
Ejemplo:
Desarrollar (3x - 2y)^3 utilizando el teorema del binomio
Ejemplo:
Calcular el cuarto término del desarrollo de (2x - 3)5
n = 5
k = 4 k = r + 1 donde r = 4 - 1 = 3
T_{r + 1} = T_4 = C(5, 3)(2x)^{5 - 3}(-3)^3
Capitulo 2: TEORÍA DE GRAFOS
INTRODUCCIÓN
La Teoría de Grafos es parte de Matemáticas Discreta que es una asignatura del plan de estudios de Ingeniería en Informática, que tiene un marcado enfoque práctico, aplicado y computacional, además de un acentuado carácter formativo. El contenido referido a esta temática se plantea como respuesta a una variada serie de problemas de la «vida real» (diseño de bloques, flujo de redes, diseño de circuitos, transporte de viajeros, asignaciones horarias o de tareas, programación, etc.), lo que le confiere el enfoque aplicado que señalamos arriba, aprendiendo el alumno, además, a buscar modelos matemáticos adecuados para gran número de situaciones diferentes, lo que suele ser muy habitual en el desarrollo profesional. El tratamiento que se pretende dar a la asignatura es práctico pues, aparte de la resolución de ejemplos y ejercicios que tiene que desarrollar sobre el papel, se debe dedicar una buena parte de tiempo a realizar prácticas en el computador para resolver algún problema en lo posible concreto (extraído de un caso real).
G1 es un grafo no simple, pues consta de dos lados paralelos e2 y e3 y dos lazos e1 y e4, pues e2 = (V1, V2), e3 = (V1, V2) y e1 es un lazo, pues e1 = (V1, V1)
GRAFOS
Existen varios tipos de grafos:
a) Un GRAFO NO DIRIGIDO G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tal que cada arista e ∈ E se asocia con un par no ordenado de vértices. Entonces se puede decir que si existe una arista e entre un par de vértices v y w, esta puede ser igual a: e = ( v, w) o e = ( w, v)
- Un grafo esta formado de vértices y aristas (lados), por lo tanto G = {V, E}
- Los vértices del grafo G son: V_1, V_2, V_3, V_4 entonces V = {V_1, V_2, V_3, V_4}
- Las aristas del grafo son: e_1, e_2, e_3, e_4 entonces E = {e_1, e_2, e_3, e_4}
- Entonces podemos decir que G = {{V_1, V_2, V_3, V_4}, {e_1, e_2, e_3, e_4}}
- Como el grafo G no tiene lazos ni lados paralelos entonces es un grafo simple.
- Otro ejemplo de grafo no dirigido es el siguiente:
- El grafo no dirigido permite que diferentes aristas se asocien con el mismo par de vértices. Como podemos apreciar todas las aristas que se asocien con el mismo par de vértices se denomina aristas paralelas, para el gráfico serian e1 y e2 pues convergen en los vértices (V1, V2). Denominamos lazo a aquella arista que inciden en un mismo vértice para la grafica sería e3, debido a que incide en el vértice V2; e3 = (V2, V2). Un vértice como V4 que no incide en ninguna arista se llama vértice aislado.
- Un grafo que contiene lazos y aristas paralelas se llama grafo no simple.
b) Un GRAFO DIRIGIDO G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tal que cada arista e ∈ E se asocia con un par ordenado de vértices. Si hay una única arista e asociada con el par ordenado (v, w) de vértices, se escribe e = (v, w), que denota una arista de v a w. En la grafica dirigida sus aristas dirigidas se indican por flechas.
- La arista e_3 se asocia con el par ordenado de vértices (V_4,V_3) debido a que tiene como vértice origen a V_4 y vértice destino a V_3, y se denota por: e_3 = {V_4, V_3}. No se puede decir que: e_3 = {V_3, V_4} porque la dirección de la arista e_3 no es esa.
c) Un GRAFO PONDERADO G es aquel en donde se muestran los pesos de cada una de sus aristas. Peso es el valor asignado a cada arista. En un grafo ponderado la longitud de una ruta es la suma de los pesos de las aristas en la ruta.
- Ejercicio
- Complete el cuadro, con la longitud de las diferentes rutas del grafo G expuesto arriba.
d) GRAFO COMPLETO sobre n vértices, denotada por Kn, es la gráfica simple con n vértices en la que hay una arista entre cada par de vértices distintos.
- G de K_4 y tiene solo una arista entre cada par de vértices.
e) GRAFO DE SIMILITUD se refiere a un grafo que tiende a agrupar objetos semejantes en clases, con base en las propiedades de los objetos. En el textos base pagina 323 se muestra un ejercicio sugiero revisarlo.
SUBGRAFOS
Se puede obtener de un grafo un subgrafo. Por ejemplo
Sea G = (V, E) una gráfica. (V’, E’) es una subgráfica de G si:
a) V’ ⊆ V y E’ ⊆ E
b) Para toda arista e’ ∈ E’, si e’ incide en v’ y w’, entonces v’, w’ ∈ V’
Por lo antes mencionado podemos determinar que G’ es un subgrafo de G.
V = {V_1, V_2, V_3, V_4} E = {e_1, e_2, e_3, e_4, e_5}
V’ = {V_1, V_2, V_3} E‘ = {e_1, e_2, e_5}
V’ ⊆ V E’ ⊆ E
Por lo tanto G’ ⊆ G
GRADO DE UN VERTICE (δ)
El grado de un vértice v, δ(v), es el número de aristas que inciden en v.
δ (V1) = 3
δ (V2) = 5
δ (V3) = 4
δ (V4) = 1
δ (V5) = 5
δ (V6) = 2
δ (V7) = 2
δ (V8) = 0
CAMINOS Y CICLOS
Camino o trayectoria es el recorrido desde un V0 (vértice inicial) a Vn (vértice destino) de longitud n, es una sucesión alternante de n + 1 vértices y n aristas que comienza en el vértice V0 y termina en el Vn . Formalmente significa: comience en el vértice v0; recorra la arista e1 hasta v1; siga por la arista e2 hasta v2, y así sucesivamente.
(v_0', e_1', v_1', e_2', v_2', …. v_{n - 1}, e_n, v_n)
Donde la arista e_i es incidente sobre los vértices v_{i - 1} y v_i para i = 1, … n.
Ejemplo:
Construyamos un camino en G desde el vértice 1 hasta el vértice 2 de longitud 4.
Camino o trayectoria de G: (1, e_1, 2, e_2, 3, e_3, 4, e_4, 2)
Además, el mismo camino se puede representar así: (1, 2, 3, 4, 2)
En caso de que no se repita ningún vértice entonces recibe el nombre de camino simple, por ejemplo: (1, 2, 3,4) y (7, 6, 5,2)
IMPORTANTE
Sean v y w vértices en un grafo G.
- Un camino simple o trayectoria de v a w es una ruta de v a w sin vértices repetidos.
- Un ciclo (o circuito) es un camino de longitud diferente de cero de v a v sin aristas repetidas.
- Un ciclo simple es un ciclo de v a v en el que no hay vértices repetidos, excepto por el inicio y el fin que son iguales a v.
Tomando como referencia la grafica anterior, vamos a determinar si tiene caminos simples, ciclo y ciclo simple.
Una vez aprendido las definiciones anteriores y comprendido el ejemplo, pasamos a estudiar lo que son las gráficas conexas.
Una grafica G es conexa si dados cualesquiera dos vértices v y w en G existe una trayectoria de v a w.
La grafica que se muestra no es conexa por cuanto no existe trayectoria de v_3 a v_5
Ejercicio
Realice el ejercicio 19 de la página 325 del texto base.
CICLO DE EULER Y DE HAMILTON
CICLO DE EULER
Si una grafica G tiene un ciclo de euler, entonces G es conexa y todo vértice tiene grado par (2, 4, 6 …).
Ejemplo:
Verificar si la siguiente gráfica tiene ciclo de Euler.
Observamos que la grafica es conexa, puesto que sus vértices tienen grado par así:
δ(v1) = δ (v2) = δ (v3)= δ (v5) = 4
δ (v4) = 6
δ (v6) = δ (v7) = 2
Por lo tanto si existe ciclo de euler el mismo que es: (v6, v4, v7, v5, v1, v3, v4, v1, v2, v5, v4, v2, v3, v6), si se dan cuenta una característica importante de este camino es que ninguna de sus aristas se repiten.
IMPORTANTE
Si G no tiene aristas entonces tiene un solo vértice por lo tanto contiene un ciclo de euler.
Ejercicio:
Realice el ejercicio 32 de la página 325 del texto base.
CICLO DE HAMILTON
En honor de Hamilton, decimos que un ciclo en una grafica G que contiene cada vértice en G exactamente una vez, excepto por el vértice inicial y final que aparece dos veces, recibe el nombre de ciclo hamiltoniano.
Ejemplo:
Partiendo de la gráfica que se muestra trace un camino de (a) a (a) que contenga todos los vértices sin repetir ninguno.
El camino de Hamilton solicitado sería: (a, f, g, p, q, r, s, t, o, n, m, l, k, j, i, h, b, c, d, e, a). Como pueden observar no se repite vértice alguno, excepto el inicial y final que es el mismo.
Ejercicio:
Realice el ejercicio 2 de la página 336.
REPRESENTACIÓN DE GRÁFICAS
Anteriormente analizamos las gráficas como un dibujo, pero cuando se requiere analizar una grafica mediante una computadora se necesita de una representación mas formal.
Conoceremos dos formas:
a) MATRIZ DE ADYACENCIA
Para formar la matriz, primero elegimos los vértices siguiendo un orden cualquiera. A continuación etiquetamos los renglones y las columnas de una matriz con los vértices ordenados. La entrada en esta matriz es 1 si los vértices del renglón y la columna son adyacentes y 0 en caso contrario.
Llamamos vértices adyacentes a aquellos vértices que están formados por la misma arista. Llamamos aristas adyacentes a aquellas aristas que convergen en un mismo vértice.
De la gráfica que se muestra podemos decir que a y b son vértices adyacentes puesto que comparten la misma arista, así, también a y d. Las aristas adyacentes que convergen en el vértice a son: la que une a d con a y la que une a b con a. Los invito a analizar los demás vértices y aristas de la gráfica.
En la matriz de la grafica expuesta se pueden detectar algunas propiedades de la gráfica simple:
El grado de un vértice
δ(c) = 3 en la fila de c hay tres unos
- δ (c) = 3 en la de b hay tres unos
- δ (c) = 3 en la de e hay tres unos
- La matriz permite representar lazos
- No permite representar lados paralelos
Al elevar al cuadrado la matriz A obtenemos A2 que determina los caminos de longitud (2) que puede trazarse de cada vértice.
Al elevar al cuadrado (A2) obtenemos A4 que determina los caminos de longitud 4 que hay de cada vértice.
Ejemplos
- Los caminos de a - a de longitud 2 son: (2) (a, b, a),(a, d, a)
- Los camino de b - d de longitud 2 son (2): (b, c, d),(b, a, d)
- Los caminos de c - c de longitud 2 son (3): (c, b, c),(c, d, c),(c, e, c)
- Los caminos de d - e de longitud 4 son 6: (d, a, d, c, e), (d, c, d, c, e), (d, a, b, c, e), (d, c, e, c, e), (d, c, e, b,
e), (d, c, b, c, e)
- Los caminos de c - d de longitud 4 son 3: (c, e, b, a, d), (c, b, e, c, d), (c, e, b, c, d)
Le sugerimos que busque y encuentre algunos otros caminos:
- a - b longitud 4 (3)
- d - e longitud 4 (6)
Ejercicio
Realice el ejercicio 1 de la página 348 y 16 de la página 349, del texto base.
b) MATRIZ DE INCIDENCIA
Los elementos de esta matriz están dados por la incidencia entre un vértice y un lado. Cuando existe esta incidencia se adopta 1, caso contrario 0.
Propiedades:
- - Permite representar lazos y lados paralelos
- - La columna con único valor diferente de 0 es un lazo
- - Las columnas que no son lazos deben tener (2) unos
- - La valencia de un vértice es igual a la suma de la fila
ISOMORFISMO DE GRÁFICAS
Las graficas G1 y G2 son isomorfas si existe una función f uno a uno y sobre de los vértices de G1 a los vértices de G2 y una función g uno a uno y sobre de las aristas de G1 a las aristas de G2, de manera que una arista e es incidente en v y w en G1 si y solo si la arista g (e) es incidente en f (v) y f (w) en G2. El par de funciones f y g reciben el nombre de isomorfismo de G1 en G2.
El isomorfismo para las graficas G1 y G2 se define por:
- f(a) = A, f(b) = B, f(c) = C, f(d) = D, f(e) = E
Dos graficas simples G1 y G2 son isomorfas si y solo si para cierto orden de sus vértices las matrices de adyacencia son iguales.
La matriz de adyacencia de la grafica G1 es la que se presenta a continuación.
La matriz de adyacencia de la grafica G2 es la que se presenta a continuación.
De nuevo observamos que las gráficas G1 y G2 son isomorfas.
Ejercicio
Realice el ejercicio 2 y 4 de la página 361, del texto base
GRÁFICAS PLANAS
- Una gráfica es plana si se puede dibujar en el plano sin que sus aristas se crucen.
Ejemplo:
Determine si la grafica es plana. Si lo es, dibújela de nuevo sin que se crucen las aristas.
Luego de analizar detenidamente la grafica observamos que si la podemos trazar sin que se crucen las aristas, quedando asi:
Ahora vamos a aplicar la formula para hacer la verificación correspondiente.
Gráfica plana conexa con f = 7 caras (A, B, C, D, E), e = 10 aristas y v = 5 vértices; f = e – v + 2
Entonces:
f = e – v + 2
7 = 10 – 5 + 2
7 = 7 Por lo tanto la grafica es plana.
Además, es necesario conocer como demostrar que ciertas gráficas no son planas:
- Se dice que una gráfica es plana si se puede dibujar en el plano sin que sus aristas se crucen, si y solo si No contiene una subgráfica homeomorfa a K5 o K3,3 (teorema de Kuratwski).
- Dos graficas G1 y G2 son homeomorfas si G1 y G2 se pueden reducir a graficas isomorfas realizando varias reducciones en serie.
- Existe isomorfismo de graficas cuando las figuras G1 y G2 definen las mismas graficas aunque parezcan diferentes. Entonces se puede decir que para que exista isomorfismo se debe tener el mismo numero de vértices, de aristas, además, de que el grado se 2, luego de realizar una reducción de serie.
- La reducción en serie se da cuando en una grafica G las aristas (v, v1) y (v, v2) están en serie, y al hacer reducción en serie desaparece v y solo queda v1, v2.
Apóyese del ejemplo planteado en la página 361 del texto base, para su mejor comprensión, utilizando el teorema de Kuratowski.
Ejercicio:
Realizar el ejercicio 2 de la página 363 del texto base.
LOCURA INSTANTÁNEA
Es un juego formado por 4 cubos, cada una de cuyas caras está pintada de uno de 4 colores: rojo, blanco, azul, verde (R, B, A, V).
El problema consiste en apilar los cubos, uno sobre otro, de modo que uno vea los 4 colores desde el frente, por detrás, por la izquierda o por la derecha.
Ejemplo:
Determine una solución del juego de locura instantánea, cuya información está dada por el siguiente grafo:
RB BV VA AR
AB AV VB RR
- Cada arista debe tener grado 2.
- Cada cubo debe representarse mediante una arista exactamente una vez en cada gráfica.
- Las dos gráficas no deben tener aristas en común.
- Para obtener una solución primero trazamos una gráfica G que representa todas las caras de todos los cubos.
- Los vértices de G representan los cuatro colores y una arista con etiqueta i conecta dos vértices (colores) si las caras opuestas i tienen dichos colores.
- No es conveniente el método prueba error.
- Mejor busque dos subgráficas que cumplan las condiciones pedidas.
Capitulo 3 ARBOLES
INTRODUCCIÓN
Los árboles forman una de las subclases de gráficas que más se utilizan. La ciencia de la computación hace uso de los árboles ampliamente, especialmente para organizar y relacionar datos en una base de datos. Los árboles surgen en problemas teóricos como el tiempo óptimo para ordenar.
TERMINOLOGÍA Y CARACTERIZACIÓN DE LOS ÁRBOLES
Un árbol T (libre) es una gráfica simple que satisface lo siguiente; si v y w son vértices en T, existe una trayectoria simple única de v a w. Se muestra un ejemplo:
Un árbol con raíz es un árbol en el que un vértice específico se designa como raíz, se presenta un ejemplo:
Como la trayectoria simple de la raíz a cualquier vértice dado es única, cada vértice esta en un nivel determinado de manera única. Así, el nivel de la raíz es el nivel 0, los vértices que están debajo de la raíz están en el nivel 1, y así sucesivamente. Por lo tanto podemos decir que: el nivel de un vértice v es la longitud de la trayectoria simple de la raíz a v.
La altura de un árbol con raíz es el número máximo de nivel que ocurre.
Ejemplo:
Tomando como referencia el gráfico del árbol con raíz determine el nivel del vértice a, b, g y determine también la altura del árbol.
Para el vértice a su nivel es 0
Para el vértice b su nivel es 1
Para el vértice g su nivel es 2
La altura del árbol es de 2.
Ejercicio:
Construya dos árboles libres uno de 7 vértices y el otro de 5 vértices, luego determine cuantas aristas tiene cada árbol.
ÁRBOLES DE EXPANSIÓN
Un árbol T es un árbol de expansión de una gráfica G si T es una subgráfica de G que contiene a todos los vértices de G. Una grafica G tiene un árbol de expansión si y solo si G es conexa.
El árbol de expansión para la grafica G que se presenta, se muestra con línea seguida.
Existen dos métodos para encontrar el árbol de expansión de una grafica G:
1. Por búsqueda a lo ancho: permite procesar todos los vértices en un nivel dado antes de moverse al nivel más alto que lo sigue; primero se selecciona un orden de los vértices, considerando el primer vértice de ese orden como raíz.
2. Por búsqueda en profundidad: o conocido también como de regreso.
Ejemplo
Utilice la búsqueda a profundidad con el orden h, g, f, e, d, c, b, a de los vértices para determinar un árbol de expansión de la grafica G.
Tomado h como vértice raíz tenemos:
Árboles de expansión mínimo
Un árbol de expansión comprende un grafo que posee nodos, arcos cada uno con longitud (peso) no negativa. Para encontrar el árbol de expansión mínima se debe recorrer todos los vértices del árbol en el que la suma de los pesos de sus aristas sea mínima, no se incluyen ciclos en la solución.
Un árbol de expansión mínima de G es un árbol de expansión de G con peso mínimo.
Algoritmo de la ruta más corta en un árbol
Se lo obtiene aplicando el algoritmo de Dijkstra, al recorrer el árbol se lo hace desde un Vo a un Vf por las aristas cuyos pesos sean menores y la suma del recorrido sea menor, no es necesario que se abarque todos los vértices.
Ejemplo:
Determine el árbol de expansión mínimo para la gráfica de la página 405 del texto base ejercicio 4. Utilizando el algoritmo de la ruta más corta.
Luego de haber recorrido las diferentes alternativas de la gráfica propuesta en el texto básico obtenemos como resultado la que se muestra:
Si realizamos la suma de sus pesos es de 35; sumatoria mínima.
Ejercicio:
Realice el mismo ejercicio propuesta anteriormente utilizando el algoritmo de Prim.
ÁRBOLES BINARIOS
Están entre los tipos de árboles binarios especiales con raíz, su característica es que todo vértice tiene cuando mucho dos hijos. Donde cada hijo se designa como un hijo izquierdo o un hijo derecho, además, su posición en el árbol los identifica.
Formalizando se dice que un árbol binario es un árbol con raíz en el que cada vértice tiene ningún hijo, un hijo o dos hijos. Si el vértice tiene un hijo se designa como un hijo izquierdo o como derecho (pero no ambos). Si un vértice tiene dos hijos, un hijo se designa como hijo izquierdo y el otro como hijo derecho.
Un árbol binario completo es un árbol binario en el que cada vértice tiene dos o cero hijos.
Ejemplo
La altura de este árbol es de 2.
Ejercicio
Realice el ejercicio 6 de la página 389 del texto base.
RECORRIDO DE UN ÁRBOL
Existen tres métodos extras que permiten recorrer un árbol, ellos son:
- Recorrido preorden: considera para el recorrido del árbol el siguiente orden (raíz - izquierda - derecha)
- Recorrido entreorden: considera para el recorrido del árbol el siguiente orden (izquierda -raíz - derecha)
- Recorrido postorden: considera para el recorrido del árbol el siguiente orden (izquierda – derecha - raíz)
Respuesta:
PREORDEN: * - + A B - * C D / E F A
ENTREORDEN: A + B – C * D – E / F * A
POSTORDEN: A B + C D * E F / - - A *
Ejercicio
Realice el ejercicio 3 de la página 420 y 8 de la página 421 del texto base.
ISOMORFISMOS DE ÁRBOLES
Dos graficas simples G1 y G2 son isomorfas si y solo si existe una función f uno a uno y sobre del conjunto de vértices de G1 al conjunto de vértices de G2 que preserva la relación de adyacencia en el sentido de que los vértices vi y vj son adyacentes en G1 si y solo si los vértices f(vi) y f(vj) son adyacentes en G2.
Ejemplos
a)
Existe isomorfismo porque:
f(a) = 1, f(b) = 3, f(c) = 2 , f(d) = 4, f(e) = 5
b)
Los árboles con raíz no son isomorfos, pues existe una invariante debido a que el árbol T1 tiene un vértice de grado 2 en el niv
el 1 y T2 no.
Ejercicios
[[Imagen:]]
Realice los ejercicios 4 y 6 de la página 438 del texto base.
Capitulo 4 MODELOS DE REDES
INTRODUCCIÓN
En este capitulo se estudian los modelos de redes, que usan gráficas dirigidas, en esta sección aprenderemos a maximizar el flujo a través de una red. La red podría ser una red de transporte por la que fluyen bienes, una red de tuberías a través de la cual fluye el petróleo, una red de computadoras a través de la cual fluyen los datos, etc. En cada caso el problema consiste en determinar el flujo máximo. La maximización del flujo en una red es un problema que pertenece a la teoría de gráficas como a la investigación de operaciones. Las redes de Petri modelan sistemas en los que el procesamiento puede ocurrir de manera concurrente. El modelo proporciona un marco de referencia para tratar cuestiones como la posible operación de estancamiento en un sistema o el hecho de exceder la capacidad de los componentes de un sistema.
RED DE TRANSPORTE
Considerando la siguiente gráfica dirigida (red de transporte), que representa una tubería de petróleo. El petróleo se descarga en el muelle a y se bombea por toda la red de la refinería z . Los vértices b,c,d y e representan estaciones de bombeo intermedias. Las aristas dirigidas representan subtuberías del sistema y muestran la dirección en que puede fluir el petróleo. Las etiquetas de las aristas indican las capacidades de las subtuberías. El problema es encontrar la manera de maximizar el flujo del muelle a la refinería y calcular el valor de este flujo máximo.
Una red de transporte es una grafica dirigida, simple con pesos que satisface:
a) Un vértice fijo, designado como el origen o fuente, no tiene aristas de entrada.
b) Un vértice, designado como destino o sumidero, no tiene aristas salientes.
c) El peso Cij de la arista dirigida (i, j) llamada capacidad de (i, j) es un numero no negativo.
Si observamos la gráfica, el origen es el vértice a y el destino es el vértices z. La capacidad de la arista (a, b), C_{a, b} es 3 y la capacidad de la arista (b, c), C_{b, c} es 2. Un flujo en una red asigna un flujo a cada arista dirigida que no excede la capacidad de esa arista. Más aun, si se supone que el flujo que entra a un vértice v, que no es el origen y el destino, es igual al flujo que sale de v.
Ejemplo de red de transporte
Tomado con referencia la gráfica:
Sea G una red de transporte. Sea C_{ij} la capacidad de la arista dirigida (i, j) . Un flujo F en G asigna a cada arista dirigida (i, j) un numero no negativo F_{ij} tal que:
a. F_{ij} ≤ C_{ij}
b. Para cada vértice j, que no es la fuente ni el destino.
Conservación de flujo
- F_{ij} recibe el nombre de flujo en la arista (i, j). Para cualquier vértice j,
- Se llama flujo que entra a j y
- Se llama flujo que sale de j.
Conservación de flujo significa para el ejemplo, que el petróleo no se usa ni se suministra en las estaciones de bombeo b, c, d y e.
Ahora, vamos a definir un flujo para la red del ejemplo asignando los valores:
F_{ab} = 2, F_{bc} = 2, F_{cz} = 3; F_{ad} = 3, F_{dc} = 1, F_{de} = 2, F_{ez} = 2
La gráfica quedaría,
Analizando, El flujo que entra al vértice d F_{ad} = 3 y es el mismo que sale del vértice d,
F_{dc} + F_{de} = 1 + 2 = 3
Se debe considerar que una arista e se etiqueta “x, y” si la capacidad de e es x y el flujo en e es y.
Observemos que el flujo que sale del origen (a) Fab + Fad, es igual al flujo que entra al destino (z) Fcz + Fez
F_{ab} + F_{ad} = 2 + 3 = 5
F_{cz} + F_{ez} = 3 + 2 = 5
Ambos valores son iguales a 5; a este valor lo denominamos valor del flujo F.
Sea F un flujo en una red G. el valor
Se llama el valor del flujo F.
Tomando como base la teoría antes mencionada, ahora vamos a realizar los siguientes ejercicios.
* Ejercicio 1
El ejemplo propuesto en la gráfica, nos permite explicar la “conservación del flujo” en una red de transporte.
En cada arista de la red, se encuentra un par o dupla de valores en unos casos completa y en otros incompleta faltando el segundo número de la dupla. El primer número de la dupla nos señala la “capacidad” que tiene la arista de la red denotada por C_{ij} que nos indica la capacidad de la arista dirigida (i, j), mientras el segundo número nos representa el “flujo” que esta transportando la arista de la red denotada por Fij que designa el flujo que transporta la arista dirigida (i, j), todo esto dentro de la red de transporte. Para resolver el problema propuesto, el flujo F en G asigna a cada arista dirigida (i, j) un número no negativo Fij, que cumple las siguientes condiciones:
1) Fij ≤ Cij, que quiere decir que el flujo que circula por cada arista debe ser menor o máximo igual a la capacidad que soporta dicha arista dentro de una red de transporte.
2) Para cada vértice j, que no sea la fuente ni el sumidero, se debe cumplir el siguiente principio: 
, que expresa que el flujo que llega a un vértice debe ser igual al flujo que sale de dicho vértice.
Para determinar los flujos faltantes de algunas de las aristas de aplicaremos las dos condiciones anteriormente expuestas.
Desarrollo:
a) Si analizamos la arista dirigida (a, d), se conoce la capacidad de la misma pero nos falta el flujo Fad, pero se puede observar que del vértice d sale la arista dirigida (d, e) cuyo flujo es conocido y es igual a 2 o sea Fde = 2 y aplicando la segunda condición se tiene que:
donde
- F_{ad} = F_{de}, pero F_{de} = 2 por tanto F_{ad} = 2 que es el flujo faltante
b) Como es conocido el flujo de la arista dirigida (a, b) y que es Fab = 3, se puede determinar el flujo faltante Fbc, aplicando la segunda condición, que para este caso sería:
donde
- F_{ab} = F_{bc}, pero F_{ab} = 3 por tanto F_{bc} = 3 que es el flujo faltante
c) Para conocer los otros flujos faltantes, para el presente caso se deberá considerar al mismo tiempo los flujos que llegan a los vértices y como los flujos que salen de los dos vértices antes mencionados, por la condición dos se tendrá:
- Para el vértice c Para el vértice e
F_{bc} = F_{ce} + F_{cz} F_{ce} + F_{de} = F_{ez}
los flujos conocidos son: los flujos conocidos son:
F_{bc} = 3 F_{de} = 2 y F_{ez} = 3
la ecuación que se forma es: la ecuación que se forma es:
3 = F_{ce} + F_{cz} F_{ce} + 2 = 3 existe una incógnita
despejamos F_{cz} = 3 - F_{ce} = 3 - 1 = 2 F_{ce} = 3 - 2 = 1 dato buscado
d) Para comprobar que los flujos obtenidos son los correctos, se tiene que revisar que la sumatoria de los flujos que salen del vértice “fuente”, deben ser igual a la suma de los flujos que llegan al vértice “destino o sumidero”, o sea:
- F_{ab} + F_{ad} = F_{cz} + F_{ez}
3 + 2 = 2 + 3
5 = 5
Por tanto la red de transporte con los flujos completos que están en negrillas sería:
- Ejercicio 2
- Encuentre los flujos en las aristas que faltan de manera que el resultado sea un flujo en la red dada. Determine los valores de los flujos.
Ejercicio
Realizar el ejercicio 3 de la página 461 del texto base.
ALGORITMO DE FLUJO MÁXIMO
Si G es una red de transporte, un flujo máximo en G es un flujo con valor máximo.
- Diseñar un algoritmo para determinar un valor máximo, consiste en iniciar con cierto flujo inicial e incrementar de manera interactiva el valor del flujo hasta que no pueda mejorarse mas.
- Podemos considerar un flujo inicial aquel en el que el flujo en cada arista es igual a cero.
- Para incrementar el valor de un flujo dado, debemos determinar un camino del origen al destino e incrementar el flujo a lo largo de este camino.
Notación
G denota una red con origen a, destino z y capacidad C
En principio denotaremos aristas no dirigidas
(Camino) P = (V0, V1,……………., Vn) Vo = a, V = z
Si una arista e en P esta dirigida de Vi-1 a Vi decimos que esta orientada en forma propia.
Si podemos determinar un camino P de la forma del origen al destino en donde cada arista P esta orientada en forma propia y el flujo en cada arista es menor que la capacidad de la arista es posible aumentar el valor del flujo.
Uso del algoritmo 8.2.4 para determinar el flujo máximo.
Dada la siguiente red de transporte:
Determinar un flujo máximo en la red, mediante el algoritmo 8.2.4
Desarrollo:
Las líneas 1 y 2 del algoritmo, nos permite inicializar el flujo con 0 para cada una de las aristas de la red.
Las líneas 5 al 9 del algoritmo, permiten etiquetar los vértices como NULOS.
Las líneas 10 y 11 del algoritmo permite etiquetar el vértice a como (-,α) que es un par o dupla de valores, donde el primer elemento identifica el vértice “predecesor o anterior” y el segundo valor es el mínimo entre el incremento (∆) y la diferencia dada por Cvw - Fvw, donde la red resultante es:
En la línea 12 al conjunto U le añadimos el vértice a en este caso (vértice fuente o inicial).
A continuación la línea 13, da inicio al ciclo WHILE, que permite etiquetar los vértices que conectan las aristas que salen de a y al mismo tiempo elimina el vértice a de U, para nuestro caso las aristas (a, b) y (a, d) controlando que los vértices b y d no estén etiquetados. Luego de etiquetar los vértices anteriores, regresamos a la línea 13 y repetimos el ciclo WHILE, pero esta vez tomamos el vértice b y nos dirigimos a etiquetar el vértice c que se conecta con la arista (b, c) y c no esta etiquetado, se elimina el vértice b y se añade el vértice c a U. Regresamos a la línea 13 y repetimos el ciclo WHILE, como el vértice z no está etiquetado, tomamos cualquiera de los vértices que se encuentran en U pero observando que con los vértices que se conecta no se encuentren etiquetados, para nuestro caso tomamos el vértice c y cumplimos los requisitos que nos pide el algoritmo en las líneas que hagamos referencia, para nuestro caso c se conecta con z y z no está etiquetado, dando como resultado lo siguiente:
Regresamos a la línea 13, ciclo WHILE, pero como z está etiquetado, saltamos a la línea 35, donde las líneas que le siguen nos permite determinar el conjunto P con el camino de los vértices comenzando desde z hacia atrás hasta llegar a a, donde el camino está dado por:
P = (a, b, c, z)
En la línea 43 del algoritmo hacemos ∆ = val(z) y asignamos el flujo a todas las aristas del camino identificado, conforme lo señalan las líneas del algoritmo que están a continuación de la línea 43.
La red con estos nuevos datos es la siguiente:
Luego de obtener este primer camino, regresamos al inicio del algoritmo o sea a la línea 3 y volvemos a ejecutar las instrucciones como se lo hizo al inicio, con esto se determina otro camino y los flujos respectivos; pero hay que considerar que ahora algunas de las aristas ya tienen un flujo asignado por el anterior proceso. Este procedimiento continua hasta cuando el conjunto U este vacío, que se controla en la línea 15 y se puede dar por terminado el algoritmo.
Ejercicio
Resolver el ejercicio 6 de la pagina 457.
RED DE ACOPLAMIENTO
Al ser esta una sección muy corta les solicito se remitan al texto base para su correspondiente revisión, en las páginas 478 – 483.
Capitulo 5 AUTÓMATAS, GRAMÁTICAS Y LENGUAJES
CIRCUITOS SECUENCIALES Y MÁQUINAS DE ESTADO FINITO
En esta sección se revisara sobre los circuitos en los que la salida depende no solo de la entrada, sino también del estado del sistema en el momento en que se introduce la entrada, en este sentido estos circuitos tiene memoria y se conocen como circuitos secuenciales. Las operaciones dentro de una computadora se llevan a cabo en intervalos discretos. La salida depende del estado del sistema al igual que de la entrada. Si suponemos que el estado del sistema cambia solo en el tiempo t = 0, 1 … una manera de sencilla de introducir la secuenciación en los circuitos es introducir un retraso unitario de tiempo.
Un retraso unitario de tiempo acepta como entrada un bit xt en el tiempo t y produce xt-1 el bit recibido como entrada en el tiempo t – 1. En el siguiente gráfico se muestra un retraso unitario en el tiempo.
Una máquina de estado finito es un modelo abstracto de una máquina con una memoria interna primitiva.
Una máquina de estado finito M consiste en:
a) Un conjunto finito I de símbolos de entrada
b) Un conjunto finito O de símbolos de salida
c) Un conjunto finito S de estados
d) Una función f del siguiente estado de S x I en S
e) Una función g de salida de S x I en S
f) Un estado inicial δ ∈ S
Se escribe M = {I, O, S, f, g, δ}
Sean I = {a, b} , O = {0, 1} y S = {δ0, δ1}. Defina un par de funciones
f: S × I → S
f: S I → O
Entonces: M = {I, O, S, f, g, δ0} es una maquina de estado finito.
La interpretación de la tabla es la siguiente:
f(δ0, a) = δ_0 g(δ_0, a) = 0
f(δ0, b) = δ_1 g(δ_0, b) = 1
f(δ1, a) = δ_1 g(δ_1, a) = 1
f(δ1, b) = δ_1 g(δ_1, b) = 0
Tomando como referencia la tabla, graficamos el diagrama de transición.
Ejercicio
Realice el ejercicio 1 de la página 510 del texto base.
Ejemplo de máquinas de estado finito sumador en serie
Sean x = x_5, x_4, x_3, x_2, x_1 = 00111 y y = y_5, y_4, y_3, y_2, y_1 = 01101 números binarios x_1 y y_1 son los bits menos significativos. Los ceros restantes en x y y aparecen para las dos cadenas x y y sean de igual longitud y garanticen el espacio suficiente para completar la suma.
Un sumador binario en serie es una maquina de estados finitos que podemos usar para obtener x + y.
El diagrama de la figura anterior demuestra que z = z5, z4, z3, z2, z1 tiene el bit menos significativo en z1.
En la suma z = x + y, tenemos:
x = 0 0 1 1 1
+y = 0 1 1 0 1
z = 1 0 1 0 0
Observamos lo siguiente:
Para la primera suma x_1 = y_1 = 1 y z_1 = 0
Para la tercera suma x3 = y3 = 1 y z3 = 1 por cuanto acarreo de los bits anteriores tanto de x como de y.
En consecuencia, cada salida depende de la suma de dos entradas y de la habilidad para recorrer un acarreo de 0 o de 1.
Este mismo sumador binario podemos modelarlo mediante una maquina de estados finitos.
M = {S,σ ,θ ,γ ,ω} como sigue. El conjunto S = {S0, S1}, donde S1 indica un acarrero de i;
σ = {00, 01, 10, 11}
θ = {0, 1}
Las funciones γ ,ω están dadasen la siguiente tabla.
AUTÓMATAS DE ESTADO FINITO
Un autómata de estado finito es un tipo especial de máquina de estado finito, y son de gran interés por su relación con los lenguajes. Un autómata de estado finito A = (I, O, S, f, g, δ0) es una maquina de estado finito en la que el conjunto de símbolos de salida es {0,1} y donde el estado actual determina la ultima salida. Se denominan estados de aceptación a aquellos estados para los que la última salida fue 1.
Ejemplo:
Dibuje un diagrama de transición de la máquina de estado finito A definida por la tabla, el estado inicial es δ0. Muestre que A es un autómata de estado finito y determine el conjunto de estados de aceptación.
Por lo tanto A es un autómata de estado finito. Los estados de aceptación son δ_1 y δ_2, debido a que si estamos en el estado 0 la última salida fue 0 y si estamos en el estado δ_1 o δ_2, la última salida fue 1.
Ejercicio
Realice el ejercicio 2 de la pagina 559 del texto base.
LENGUAJES Y GRAMÁTICA
En esta sección primero vamos a determinar que se llama Vocabulario a cualquier conjunto finito. Siendo V un vocabulario cualquiera, cada elemento de V es llamado Letra. Concatenar dos o más letras es escribir una junto a la otra. La concatenación de varias letras se llama Palabra (también denominada Cadena o String). Cualquier secuencia continua de letras de una palabra que contenga a la primera letra es un Prefijo, si contiene a la última letra es un Sufijo.
La palabra vacía o sin letras se simboliza con la letra griega Lambda (l).
La reflexión de una palabra W es la que tiene sus letras invertidas. La reflexión es involutiva.
Ejemplo
Lidia = Aidil Juan = Nauj Pedro = Ordep
V* es el conjunto de palabras que pueden formarse con las letras del alfabeto V, es un conjunto infinito siempre y cuando V ≠ ∅.
Llamamos LENGUAJE sobre un vocabulario V a cualquier subconjunto de V*
Ejemplo
Sea N = {0; 1}
L1 = {w ∈ N* / long (w) £ 2} = {0; 1; 00; 01; 10; 11}
L2 = {w ∈ N* / long (w) ≥ 1} = {0; 1; …}
L3 = {w ∈ N* / w termina en 1} = {1; 01; 11; 001; 001; …}
L4 = {w ∈ N* / w = 2} = {00; 01; 10; 11}
L5 = {w ∈ N* / w = 4 y tiene un 1 solamente} = {1000; 0100; 0010; 0001}
Concatenar dos lenguajes es obtener otro lenguaje donde cada palabra es concatenación de una palabra del primer lenguaje con otra del segundo lenguaje.
L1 ° L2 = {w/w = w1•w2 w1 ∈ L1 ∧ w2 ∈ L2 }
Ejemplo
Sea:
L1 = {l, 0, 1, 100}
L2 = {0, 1, 01}
L1 L2 = {0, 1, 01, 00, 001, 10, 11, 101, 1000, 1001, 10001}
L1 L2 ≤ L1 ° L2
Para la concatenación de lenguajes usamos la notación exponencial
L^3 = L^1 L^1 L^1
L^0 = {λ} = Λ
L^1 = L
L^a = L^{a-1} L
Clausura de Kleene
U La
Clausura Positiva
U La
Producción:
X → Y
GRAMÁTICA:
Componentes: (Vt; Vn; S; P)
Vt es un conjunto finito de símbolos no terminales.
Vt ≠ ∅, Vn ≠ ∅, Vt ∩ Vn = ∅
S = Símbolo no terminal, inicial o cabecera del lenguaje.
P = Conjunto de producciones X → Y con X ≠ λ
Sea: Vt = {a, b}
- Vn = {S, A, B}
S → a / A / B
A → λ / Ab
B → b / bbB
Clasificación de Chomsky
Las gramáticas de Tipo 0 o Irrestrictas permiten cualquier tipo de producción.
Las gramáticas del Tipo 1 o Sensibles al Contexto son tales que en cada producción del tipo X → Y la longitud de Y es mayor que la longitud de X0. Las gramáticas de Tipo 2 o Independientes del Contexto son las que admiten en las producciones X como un único símbolo no terminal. En las de Tipo 3 o Regulares X solo puede ser un símbolo no terminal, e y puede ser la palabra vacía, un único símbolo, o bien dos: uno terminal y otro no terminal.
Dos gramáticas son equivalentes cuando generan el mismo lenguaje.
Gramática para enteros
Un entero se define como una cadena que consta de un signo opcional (+ o -) seguido de una cadena de dígitos (0,9). La siguiente gramatica genera todos los enteros
<dígito> ::= 0 1 2 3 4 5 6 7 8 9
<entero> ::= <entero con signo> <entero sin signo>
<entero con signo> ::= + <entero sin signo> - <entero sin signo>
<entero sin signo> ::= <dígito> <dígito> <entero sin signo>
Ejemplo
Derivación del entero – 901
<entero> ⇒ <dígito con signo>
- ⇒ - <entero sin signo>
- ⇒ - <dígito><entero sin signo>
- ⇒ - <dígito><dígito><entero sin signo>
- ⇒ - <dígito><dígito><dígito>
- ⇒ - 9 <dígito><dígito>
- ⇒ - 90 <dígito>
- ⇒ - 901
AUTÓMATAS FINITOS
Componentes: (AE; E; e0; f; F)
AE: Es el lenguaje de entrada, constituido, en el caso de lenguajes, por los elementos del vocabulario.
E: Conjunto de estados necesarios para hacer el reconocimiento.
e0: Estados iniciales.
f: Función que hace corresponder a cada estado con la letra de entrada el estado siguiente.
F: Conjunto de estados finales que se marcan con doble círculo.
Ejemplo de autómata:
