Download Silabus Matematica Discreta Archivo - Virtual Udabol

FACULTAD DE INGENIERIA
RED NACIONAL UNIVERSITARIA
SYLLABUS
Facultad de Ingeniería
Ingeniería de Sistemas
TERCER SEMESTRE
Gestión Académica I/2017
1
FACULTAD DE INGENIERIA
UDABOL
UNIVERSIDAD DE AQUINO BOLIVIA
Acreditada como PLENA mediante R. M. 288/01
VISION DE LA UNIVERSIDAD
Ser la Universidad líder en calidad educativa.
MISION DE LA UNIVERSIDAD
Desarrollar la Educación Superior Universitaria con calidad y competitividad al servicio de
la sociedad.
2
FACULTAD DE INGENIERIA
SYLLABUS GENÉRICO
Asignatura:
Código:
Requisito:
Carga Horaria:
Créditos:
MATEMATICA DISCRETA
MAT 201 A
MAT 111 A
60
6
I. OBJETIVOS GENERALES DE LA ASIGNATURA.
Desarrollar los conceptos fundamentales de la matemática discreta, estableciendo su importancia en las ciencias de la
computación, a través de ejemplos de aplicación practica.
La enseñanza de los contenidos fundamentales de la Matemática Discreta y el uso de su terminología son imprescindibles en
todos los cursos de nivel universitario, ya que van asociadas al progreso de las ciencias y la unidad conceptual, desde el
punto de vista instructivo la asignatura introduce la terminología y conocimientos que trata con diferentes tipos de objetos, los
cuales pueden a su vez, combinarse de maneras diferentes.
II.
PROGRAMA ANALÍTICO DE LA ASIGNATURA.
TEMA 1. TEORIA DE CONJUTOS
Conjuntos
Conjunto universal
Conjunto vacio
Subconjuintos
Operaciones con conjuntos
Complemento de conjuntos
Intersección de conjuntos
Unión de conjuntos
Leyes de Morgan
Diferencia de conjuntos
TEMA 2. RECUENTO
Conjunto producto
Variaciones - Combinaciones
R - eto Ordenado
R - eto No Ordenado
Métodos secuencial de Recuento de os r- etos Ordenados que Poseen Una propiedad Dada
Número de r - etos Ordenados Con Repetición (Variaciones Con Repetición)
Número de r - etos Ordenados Sin Repetición (Variaciones Sin Repetición)
Número de r - etos No Ordenados Con Repetición (Combinaciones Con Repetición)
Número de r - etos No Ordenados Sin Repetición (Combinaciones Sin Repetición)
Extensión de los Métodos de Recuento
Fórmula de inclusión y de Exclusión
Representación de la Fórmulas que Poseen Propiedades
Caso de Subconjuntos No Específicos
Método General de Cribado en la Teoría de los números Enteros
3
FACULTAD DE INGENIERIA
Función de Euler
Función de Moebius
Criba de Erastostenes
TEMA 3. TEORIA DE GRAFOS
Introducción
Definición de Grafo. Tipos de Representación de Grafo
Notación de Berge
Definición de Grafo 2. Orden de un Grafo
Vértice. Arco. Extremidades. Bucles Arcos Adyacentes. Vertices Adyacentes
Arco Incidente a un Subconjunto de Vértices
Semi-grado de un Subconjunto
Grafo parcial de un Grafo. Subgrafo de un Grafo
Grafo Simétrico. Grafo Antisimétrico. Grafo Completo. Grafo Lleno. Grafo Lleno Asociado
Grafo Complementario de un Grafo.
Noción de Camino. Camino Simple. Camino Elemental
Circuito. Circuito Elemental. Circuito Simple
Longitud de un Camino
Camino Hamiltoniano. Circuito Hamiltoniano
Grafo Fertemente Conexo
Cierre Transitivo
Descomposisción de un Grafo en Subgrafos Fuertemente Conexos Másimos
Método Para Descomponer un Grafo en Subgrafos Fuertemente Conexos Máximos
Existencia y Recuento de Caminos
Función Ordinal de un Grafo sin Circuito. Función de Grundy
Estabilidad interna. Nucleo de un Grafo
Conceptos No Orientados
Número Cromatica
Tribu. Tribu Máxima
Grafo p-Coloreado. Grafo p-Aplicado
Multigarafo no Orientado o p-Grafo no Orientado. p-Grafos Planos
TEMA 4. ARBOLES
Arborescencia
Arbol. Arboles Generados Mínimos
Algoritmos de Búsqueda en grafo
Retículo Finito
TEMA 5. ENUMERACION
Introducción
Método de la Composición Latina
Enumeración de lo Caminos
Enumeración de los Caminos Elementales
Enumeración de los Circuitos Elementales
Enumeración de las Secuencias Con Repetición
Enumeración de los Factores de un Grafo
4
FACULTAD DE INGENIERIA
III. BIBLIOGRAFIA
 RALPH GRIMALDI, "Matemática discreta y Combinatoria",
Iberoamericana. 576p., 1992
Segunda Edición, México,
Addison-Wesley
 KOLMAN-BUSBY-ROSS, "Estructuras de matemática discreta para la computación”
 KENNETH A. ROSS – Charles R.B. Wright, “ Matemáticas Discretas ” Segunda Edición, Impreso en México,
Prentice All, Inc. 672p., 1990
 WINFRIED K. GRASSMANN JEAN-PAUL TREMBLAY, “Matemática Discreta y Lógica.”
 SEYMOUR LIPSCHTZ, PH. D., “ Matemáticas finitas”, Primera Edición Español, Impreso en Colombia, Mc GRAW –
HILL BOOK COMPANY, INC., USA , 344p. ( Serie de Compendios Schaum), 1977
 COLMAN – BUSBY – ROSS, "Estructuras de matemática discreta para la computación”, tercera edición, México,
1995.
 GRIMALDI R, “Combinatoria y Matemática Discreta”, Editorial Addison Wesley.
 ROSS, “Estructuras de Matemáticas Discretas”, Editorial Prentice Hall
5
FACULTAD DE INGENIERIA
IV. CONTROL DE EVALUACIONES
1° evaluación parcial
Fecha
Nota
2° evaluación parcial
Fecha
Nota
Examen final
Fecha
Nota
APUNTES
6
FACULTAD DE INGENIERIA
WORK PAPER # 1
PROGRAMA DE CONTROL DE CALIDAD
No. DE PROCEDIMIENTO:
No. DE HOJAS 4
ELABORÓ:
CÓDIGO:
TÍTULO DEL WORK PAPER: : Métodos Combinatorios
DPTO.: Facultad de Ingeniería
DESTINADO A:
DOCENTES
ALUMNOS
X
ADMINIST.
OTROS
OBSERVACIONES:
FECHA DE DIFUSIÓN:
FECHA DE ENTREGA:
7
FACULTAD DE INGENIERIA
MÉTODOS COMBINATORIOS
Técnicas básicas
Sea S un conjunto finito no vacío. Se designar por | S | al cardinal de S, es decir, el número de elementos de S. En
particular | CV | = 0 (CV es el conjunto vacío).
Principio de Adición
Sean A1, A2, ... , An conjuntos finitos tales que Ai INT Aj = CV (INT es la intersección) para cada i # j, donde i, j pertenecen a
{1, 2, ... , n}, entonces:
| A1 U A2 U ... U An | = | A1 | + | A2 | + ... + | An |
En el lanzamiento de dos dados
¿De cuántas formas se pueden obtener un siete o un ocho?



Obtener un siete = A = { (1, 6) , (2, 5) , (3, 4) , (4, 3) , (5, 2) , (6, 1) }
Obtener un ocho = B = { (2, 6) , (3, 5) , (4, 4) , (5, 3) , (6, 2) }
| A U B | = | A | + | B | = 6 + 5 = 11
El experimento de lanzar una moneda al aire tres veces
¿De cuántas formas se puede obtener una, dos o tres caras?




Una cara = A = { (C, +, +) , (+, C, +) , (+, +, C) }
Dos caras = B = { (+, C, C) , (C, +, C) , (C, C, +) }
Tres caras = C = { (C, C, C) }
|AUBUC|=|A|+|B|+|C|=3+3+1=7
Principio de Multiplicación
Sea A1, A2, ... , An una colección de conjuntos finitos no vacíos, entonces:
| A1 x A2 x ... x An | = | A1 | · | A2 | · ... · | An |
Formación de placas de matrícula
¿Cuántas placas de matrícula pueden formarse con cuatro letras (en un alfabeto de 26 letras) seguidas de tres números?



Cuatro letras = A = B = C = D = 26
Tres dígitos = E = F = G = 10
| A x B x C x D x E x F x G | = | A |·| B |·| C |·| D |·| E |·| F |·| G | = 26·26·26·26·10·10·10 = 456976000
Se dispone de una baraja de 40 cartas
8
FACULTAD DE INGENIERIA
Se extraen 4 cartas por dos procedimientos:
a) sin devolución de la carta extraída
b) con devolución en cada extracción.



1ª carta = A , 2ª carta = B , 3ª carta = C , 4ª carta = D
a) | A x B x C x D | = | A |·| B |·| C |·| D | = 40 · 39 · 38 · 37 = 2193360
b) | A x B x C x D | = | A |·| B |·| C |·| D | = 40 · 40 · 40 · 40 = 2560000
Formación de números
¿Cuántos números naturales distintos existen entre 5000 y 10000 y tienen todas sus cifras diferentes?


1º dígito (5...9) = A , 2º dígito (0...9) = B , 3º dígito (0...9) = C , 4º dígito (0...9) = D
| A x B x C x D | = | A |·| B |·| C |·| D | = 5 · 9 · 8 · 7 = 2520
Principio de Distribución
Sean m, n y p números naturales. Si se distribuyen np + m objetos en n cajas entonces alguna caja deberá contener al
menos p + 1 objetos.
9
FACULTAD DE INGENIERIA
WORK PAPER # 2
PROGRAMA DE CONTROL DE CALIDAD
No. DE PROCEDIMIENTO:
No. DE HOJAS 4
ELABORÓ:
CÓDIGO:
TÍTULO DEL WORK PAPER: : Elementos Combinatorios
DPTO.: Facultad de Ingeniería
DESTINADO A:
DOCENTES
ALUMNOS
X
ADMINIST.
OTROS
OBSERVACIONES:
FECHA DE DIFUSIÓN:
FECHA DE ENTREGA:
10
FACULTAD DE INGENIERIA
ELEMENTOS COMBINATORIOS
Permutaciones
Cualquier arreglo de un conjunto de n objetos en un orden dado se llama permutación de los objetos (tomados todos al
mismo tiempo). Se designa por:
P( n ) = n! = n · (n - 1) · (n - 2) · ... · 2 · 1
Formaciones con personas
¿De cuántas maneras puede organizarse un grupo de 7 personas:
a) en una fila de 7 asientos?
b) alrededor de una mesa redonda?


a) P( 7 ) = 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040
b) P( 7 - 1 ) = 6! = 6 · 5 · 4 · 3 · 2 · 1 = 720
Permutaciones con repetición
Con frecuencia deseamos encontrar el número de permutaciones de objetos, algunos de los cuales son iguales. La fórmula
general es (r es el número de elementos repetidos):
PR( n ) = n! / n1! · n2! · ... · nr!
Permutaciones con letras
¿Cuántas permutaciones pueden formarse con las letras de la palabra "radar"?


Repeticiones: r = 2 , a = 2
PR( 5 ) = 5! / 2! · 2! = 5 · 4 · 3 · 2 · 1 / 2 · 1 · 2 · 1 = 120 / 4 = 30
Permutaciones con banderas
¿Cuántas señales de 6 banderas pueden formarse con 4 banderas rojas y 2 azules?
Repeticiones: rojas = 4 , azules = 2
PR( 6 ) = 6! / 4! · 2! = 6·5·4·3·2·1 / 4·3·2·1·2·1 = 720 / 48 = 15
Variaciones
Sea un conjunto finito con n elementos (n > 0) y r un número natural (r <= n). Una variación de orden r es una lista ordenada
de n elementos distintos tomados de r en r. Su fórmula es:
V( n, r ) = n! / (n - r)!
Variaciones con bolas
Una urna contiene 8 bolas. Encontrar el número de muestras ordenadas de magnitud 3.
11
FACULTAD DE INGENIERIA
V( 8, 3 ) = 8! / (8 - 3)! = 8! / 5! = 8·7·6·5·4·3·2·1 / 5·4·3·2·1 = 40320 / 120 = 496
Variaciones con números
¿Cuántos números de 3 dígitos pueden formarse con las cifras 2, 3, 5, 6, 7 y 9?
V( 6, 3 ) = 6! / (6 - 3)! = 6! / 3! = 6·5·4·3·2·1 / 3·2·1 = 720 / 6 = 120
Variaciones con repetición
Sea un conjunto finito con n elementos (n > 0) y r un número natural (r <= n). Una variación con repeticiones de orden r es
una lista ordenada de n elementos tomados de r en r. Su fórmula es:
VR( n, r ) = n^r
Los catorce en las quinielas
En el juego de las quinielas, ¿cuál es el número mínimo de columnas que han de rellenarse para acertar con seguridad los
catorce signos?
VR( 3, 14 ) = 3^14 = 4728969
Formaciones de palabras
En un alfabeto formado por las letras (a, b, c, d), ¿cuántas palabras distintas de diez letras pueden formarse?
VR( 4, 10) = 4^10 = 1048576
Combinaciones
Sea un conjunto finito con n elementos (n > 0) y r un número natural (r <= n). Una combinación de orden r es una lista de
elementos distintos, donde el orden no se tiene en cuenta. Se formula:
C( n, r ) = n! / r! . (n - r)!
El juego del póker
¿Cuántas manos de póker distintas (5 cartas) pueden formarse con una baraja de 52 cartas?
C( 52, 5 ) = 52! / 5!·47! = 52·51·50·49·48 / 5·4·3·2·1 = 311875200 / 120 = 2598960
Comité de personas
¿De cuántas maneras puede formarse un comité que consta de 3 hombres y 2 mujeres, a partir de 7 hombres y 5 mujeres?



A = Hombres = C( 7, 3 ) = 7! / 4! · 3! = 210 / 6 = 35
B = Mujeres = C( 5, 2 ) = 5! / 3! · 2! = 20 / 2 = 10
| A x B | = | A | ú | B | = 35 · 10 = 350
Combinaciones con repetición
12
FACULTAD DE INGENIERIA
Sea un conjunto finito con n elementos (n > 0) y r un número natural. Una combinación con repetición de orden r es una lista
ordenada de n elementos en donde los elementos pueden ser iguales. Su fórmula es:
CR( n, r ) = C( n + r - 1, r )
Distribución de objetos
¿De cuántas formas se pueden distribuir 10 canicas azules en 5 bolsas distintas?
CR( 5, 10 ) = C( 5 + 10 - 1, 10 ) = C( 14, 10 ) = 87178291000 / 87091200 = 1001
Suma de dígitos
¿Cuántos números hay en el conjunto {1, 2, ..., 1000 } que tengan la propiedad de que la suma de sus dígitos sea 5?
CR( 3, 5 ) = C( 3 + 5 - 1, 5 ) = C( 7, 5 ) = 5040 / 240 = 21
Resumen del empleo de elementos combinatorios
Se eligen r
objetos de un
Número de selecciones Número de selecciones
conjunto de n
ordenadas
no ordenadas
=========================================================
No están permitidas
las repeticiones
V(n,r) = n!/(n-r)!
C(n,r) = n!/(n-r)!·r!
Están permitidas
las repeticiones
VR(n,r) = n^r
CR(n,r) = C(n+r-1,r)
13
FACULTAD DE INGENIERIA
WORK PAPER #3
PROGRAMA DE CONTROL DE CALIDAD
No. DE PROCEDIMIENTO:
No. DE HOJAS 4
ELABORÓ:
CÓDIGO:
TÍTULO DEL WORK PAPER: : Teorema del binomio
DPTO.: Facultad de Ingeniería
DESTINADO A:
DOCENTES
ALUMNOS
X
ADMINIST.
OTROS
OBSERVACIONES:
FECHA DE DIFUSIÓN:
FECHA DE ENTREGA:
14
FACULTAD DE INGENIERIA
TEOREMA DEL BINOMIO
Se considera la expresión (x + y)^n . Su desarrollo puede obtenerse mediante la fórmula:
(x + y)^n = Sumatorio de r ( 0 ... n ) en C( n, r ) · x^n-r · y^r
Desarrollo de un binomio
Calcúlese el coeficiente de x^6 en el desarrollo de (x - 3)^11.
C( 11, 6 ) · x^6 · (-3)^5 = 462 · x^6 · (-243) = -112266x^6
Fórmula de Pascal
Si n y r son enteros tales que 1 <= r <= n - 1, entonces:
C( n, r ) = C( n - 1, r ) + C( n - 1, r - 1 )
La fórmula de Pascal da un método para el cálculo de los coeficientes binómicos, dado el valor inicial C( n, 0 ) = C( n, n ) = 1,
para todo n >= 0. Los coeficientes de sucesivas potencias (x + y)^n se pueden distribuir en una figura que se conoce como
triángulo de Pascal, en el cual se tiene:


El primer y el último elemento de cada fila es 1.
Cualquier otro número del tri ngulo se puede obtener sumando los dos números que aparecen encima de él.
Fórmula de Leibnitz
Se aplica a los coeficientes del tipo multinómicos:
(x1 + x2 + ... + xk)^n = n! / n1! · n2! · ... · nk!
Cálculo de un coeficiente
Calcúlese el coeficiente del término a^3b^2c^4 del desarrollo de (a + b + c + d)^9.
9! / 3!·2!·4!·0! = 9·8·7·6·5 / 3·2·1·2·1·1 = 15120 / 12 = 1260
15
FACULTAD DE INGENIERIA
WORK PAPER # 4
PROGRAMA DE CONTROL DE CALIDAD
No. DE PROCEDIMIENTO:
No. DE HOJAS 4
ELABORÓ:
CÓDIGO:
TÍTULO DEL WORK PAPER: : Conteo
DPTO.: Facultad de Ingeniería
DESTINADO A:
DOCENTES
ALUMNOS
X
ADMINIST.
OTROS
OBSERVACIONES:
FECHA DE DIFUSIÓN:
FECHA DE ENTREGA:
16
FACULTAD DE INGENIERIA
CONTEO
1. Cuántos números de cinco cifras se pueden formar utilizando los dígitos 123567 y 9 con la condición de que:





Todas las cifras sean distintas
Todas las cifras sean iguales
El número obtenido sea múltiplo de 4
El número obtenido sea capicúa
El número obtenido sea par y capicúa
2. De una caja que contiene 122 bolillos numerados de 1 a 122, se extraen 5. Cuántos posibles resultados hay si:


Los bolillos se extraen uno a la vez.
Los bolillos se extraen todos juntos
3. De cuántas maneras se pueden ubicar 22 bolitas indistinguibles en 59 cajas numeradas con la condición de que cada
caja debe contener a lo sumo una bolita.
4. Suponga que existen 10 caminos desde oz, hasta la tierra del centro, y 5 caminos desde la tierra del centro a la isla de
la fantasía.
a) De cuantas maneras diferentes se puede ir de oz a la isla de la fantasía pasando por la tierra del centro.
b) Cuántas rutas del tipo oz del centro isla de la fantasía, tierra del centro, oz hay?, si se exige que no se repita el
camino de oz a la isla de la fantasía en el viaje de regreso
5. Se tiene número enteros del 5 al 200 ambos inclusive
a)
b)
c)
d)
cuántos números hay
Cuántos números impares hay
Cuántos son mayores que 72
Cuántos contienen el dígito 7
17
FACULTAD DE INGENIERIA
WORK PAPER # 5
PROGRAMA DE CONTROL DE CALIDAD
No. DE PROCEDIMIENTO:
No. DE HOJAS 4
ELABORÓ:
CÓDIGO:
TÍTULO DEL WORK PAPER: : Grafos
DPTO.: Facultad de Ingeniería
DESTINADO A:
DOCENTES
ALUMNOS
X
ADMINIST.
OTROS
OBSERVACIONES:
FECHA DE DIFUSIÓN:
FECHA DE ENTREGA:
18
FACULTAD DE INGENIERIA
GRAFOS
Definición
Un grafo es un conjunto de puntos (vértices) en el espacio, que están conectados por un conjunto de líneas (aristas). Otros
conceptos básicos son:
 Dos vértices son adyacentes si comparten la misma arista.
 Los extremos de una arista son los vértices que comparte dicha arista.
 Un grafo se dice que es finito si su número de vértices es finito.
Representación gráfica de un grafo
Dado un grafo G = (V, E) donde V = {a, b, c, d, e} y E = {ab, bc, be, cd, de, ad}, constrúyase una representación gráfica de G.
a
/\
/ \
b /-------\--------/ e
\
\ /
\
\/
\------c d
Debido a lo dificultoso de realizar dibujos mediante el lenguaje HTML, he propuesto este ejemplo para que en los ejemplos
sucesivos, se haga una representación gráfica de un grafo uniendo los vértices con las aristas dadas, tal y como se ha hecho
en el dibujo.
Clases de grafos




Un multigrafo es un grafo con varias aristas entre dos v‚rtices.
Un pseudografo es un grafo en el que hay aristas (lazos) que tienen el mismo extremo.
Un digrafo es un grafo donde a cada arista se le indica un sentido mediante una flecha.
Los multidigrafos o pseudomultidigrafos son combinaciones de los anteriores.
Identificación de grafos




a) V = {a, b, c, d} y E = {aa, ab, bc, cd, dd} Representa un pseudografo
b) V = {a, b, c, d, e, f} y E = {b->a, b->c, c->d, d->e, e->f} Representa un digrafo
c) V = {a, b, c, d} y E = {ab, 2*bc, cd, 2*da} Representa un multigrafo
d) V = {a, b, c, d, e, f} y E = {ab, bc, cd, de, ef, fa, b->f, f->d} No representa un grafo
Teoremas





Dos grafos son isomorfos si tienen el mismo número de vértices y aristas y, éstas se corresponden con los mismos
extremos.
El grado del vértice de un grafo (gr) es el número de aristas que tienen por extremo dicho vértice.
Si dos grafos son isomorfos, los vértices que se corresponden tienen el mismo grado.
Primer Teorema de la Teoría de Grafos: todo grafo contiene un número par o cero de vértices de grado impar.
Un subgrafo es un grafo que está contenido dentro de otro grafo y que se obtiene elimando algunas aristas y vértices
del grafo principal.
19
FACULTAD DE INGENIERIA



Un grafo es regular si todos sus vértices tienen el mismo grado k (k-regular).
Un grafo es completo si cada par de vértices son los extremos de una arista.
Dos grafos completos con el mismo número de vértices son isomorfos.
Subgrafos de un grafo
Hallar todos los subgrafos del grafo:
a
/ \
/
\
/
\
---------b
c
Se realiza la lista de subgrafos del grafo de la figura por orden creciente al número de aristas (CV es el conjunto vacío):
1. Subgrafos con cero aristas:
1.1. Con un vértice:
grafo 1.1.1.: ({a}, CV)
grafo 1.1.2.: ({b}, CV)
grafo 1.1.3.: ({c}, CV)
1.2. Con dos vértices:
grafo 1.2.1.: ({a, b}, CV)
grafo 1.2.2.: ({b, c}, CV)
grafo 1.2.3.: ({a, c}, CV)
1.3. Con tres vértices:
grafo 1.3.1.: ({a, b, c}, CV)
2. Subgrafos con una arista:
2.1. Con dos vértices:
grafo 2.1.1.: ({a, b}, {ab})
grafo 2.1.2.: ({b, c}, {bc})
grafo 2.1.3.: ({a, c}, {ac})
2.2. Con tres vértices:
grafo 2.2.1.: ({a, b, c}, {ab})
grafo 2.2.2.: ({a, b, c}, {bc})
grafo 2.2.3.: ({a, b, c}, {ac})
3. Subgrafos con dos aristas:
3.1. Con tres vértices:
grafo 3.1.1.: ({a, b, c}, {ab, bc})
grafo 3.1.2.: ({a, b, c}, {ab, ac})
grafo 3.1.3.: ({a, b, c}, {ac, bc})
20
FACULTAD DE INGENIERIA
4. Subgrafos con tres aristas:
4.1. Con tres vértices:
grafo 4.1.1.: ({a, b, c}, {ab, bc, ac})
21
FACULTAD DE INGENIERIA
CAMINOS
Un camino en un grafo es una sucesión finita en la que aparecen alternadamente vértices y aristas de dicho grafo. Otras
definiciones básicas son:








Los extremos son los vértices inicial y final del camino.
La longitud de un camino es el número de aristas que contiene.
Un camino es cerrado si sus extremos coinciden.
Un camino es simple si en la sucesión de vértices no hay ninguno repetido.
Un ciclo es un camino cerrado donde los únicos vértices repetidos son el primero y el último.
Un circuito es un camino cerrado que no repite aristas.
Si en un grafo existe un camino que conecta dos vértices distintos, entonces existe un camino simple con extremos en
dichos vétices.
Un grafo es conexo si para cada par de vértices, existe un camino con extremos en dichos vértices.
Caminos en un grafo
Sea un grafo con V = {a, b, c, d, e, f, g} y E = {ab, bc, cd, da, ca, ce, ef, fg, ge, ga}.
a
b
g
d
c
f
e
Encontrar dentro del grafo (basta enumerar los vértices):






Un camino que conecta b y f: (b, a, g, f)
Un camino simple de longitud 5 entre b y f: (b, a, d, c, e, f)
Un camino de longitud 6 entre b y f: (b, a, d, c, e, g, f)
Un camino cerrado con origen en f de longitud 6: (f, g, a, b, c, e, f)
Un ciclo de longitud 3, otro de longitud 4 y otro de longitud 6: (b, a, c, b) - (a, c, e, g, a) - (f, g, a, b, c, e, f)
Un circuito de longitud 9: (a, b, c, d, a, g, f, e, c, a)
Tipos de caminos


Camino euleriano: es un camino o circuito que contiene todas las aristas apareciendo cada una de ellas exactamente
una vez. Un grafo que admite dicho circuito se denomina grafo euleriano, y sus vértices o tienen grado par o dos de los
vértices tienen grado impar.
Camino hamiltoniano: es un camino simple que contiene todos los vértices apareciendo cada uno de ellos exactamente
una vez. Un ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un
ciclo hamiltoniano se denomina grafo hamiltoniano.
22
FACULTAD DE INGENIERIA
Caminos eulerianos
Dibujar un camino euleriano para el siguiente grafo:
a
b
e
f
c
d
(c, b, f, c, d, f, e, b, a, e, d)
EXPLORACION
Los grafos son utilizados con frecuencia para representar vías y redes de comunicación. Aquí se ofrece una forma matricial
de representar un grafo. Se denomina matriz de adyacencia a una matriz cuyas entradas son unos y ceros siguiendo una ley:
a cada emtrada mij le corresponde la arista dada por vivj. Según sea grafo o digrafo será:
GRAFO
DIGRAFO
===================================================================
mij = 1 si vivj forma arista
mij = 1 si vivj forma arista y orientación = vi -> vj
mij = 0 si vivj no forma arista mij = 0 si vivj no forma arista y orientación = vj -> vi
Teoremas
Dos grafos con la misma matriz de adyacencia son isomorfos.
Un árbol es un grafo conexo sin ciclos.
Un grafo es un árbol si y sólo si cada dos vértices distintos se conectan por un único camino simple.
Un grafo es etiquetado si sus aristas tienen asignado un número.
Se llama distancia de un grafo etiquetado a la longitud mínima del camino entre dos vértices dados.
Matriz de adyacencia de un grafo
Con los siguientes vértices:
1
5
3
4
2

Hallar la matriz de adyacencia del grafo {12, 23, 34, 45, 51, 13, 35}
|0
|1
|1
|0
|1
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0|
0|
1|
1|
0|
23
FACULTAD DE INGENIERIA

Hallar la matriz de adyacencia del digrafo {1->2, 2->3, 3->4, 4->5,5->1, 1->3, 5->3}
|0
|0
|0
|0
|1
1
0
0
0
0
1
1
0
0
1
0
0
1
0
0
0|
0|
0|
1|
0|
Algoritmo de Dijkstra
Es un algoritmo que sirve para hallar la distancia más corta entre dos vértices de un digrafo. Sus reglas básicas son:




Se toma el vértice inicial y se comprueba todas las direcciones posibles de salida.
Se elige entre todos los vértices el de la distancia mínima y se accede a él.
Desde el siguiente vértice se efectúa el mismo paso hasta llegar al vértice final.
El algoritmo recorre todos los caminos posibles hasta tener la distancia mínima entre ambos vértices.
Hallar el camino más corto
Calcular la distancia desde el vértice s hasta el vértice t aplicando el Algoritmo de Dijkstra en el siguiente grafo etiquetado:
a
b
s
t
c
d
Distancias: (sa=18, sc=15, ac=6, ab=9, cd=7, cb=14, bd=10, bt=28, dt=36)
El camino más corto será (s, a, b, t) donde d(s, t) = 55
MAPAS
Definiciones






Un grafo se dice que es plano si admite una representación gráfica en el plano de modo que cada arista corta
únicamente a otra arista en un vértice que sea extremo de ambas.
Una representación de un grafo con estas condiciones se dice que es un mapa.
Un mapa es conexo si el grafo que representa es conexo.
Las regiones son las divisiones en varias partes de un plano.
El grado de una región es la longitud del camino que la bordea.
La suma de los grados de las regiones de un mapa es igual al doble del número de aristas del grafo que representa.
Fórmula de Euler
Sea M un mapa conexo con #R (número de regiones) que representa al grafo G con #V (número de vértices) y con #E
(número de aristas), entonces:
#V - #E + #R = 2
24
FACULTAD DE INGENIERIA
Teoremas






Si un grafo es plano conexo con #V > 2, entonces #E <= 3#V - 6.
Si en un grafo plano conexo con #V > 2, no existe ningún subgrafo isomorfo k3-regular, entonces #E <= 2#V - 4.
Dos regiones son adyacentes si los caminos que las bordean tienen alguna arista en común.
Una coloración es una aplicación de tal manera que dos vértices contiguos no puedan tener el mismo color.
Todo grafo plano admite una coloración con cuatro colores.
Un grafo es bipartito si existe una coloración con sólo dos colores, o si y sólo si no tiene ciclos con longitud impar.
25
FACULTAD DE INGENIERIA
WORK PAPER # 6
PROGRAMA DE CONTROL DE CALIDAD
No. DE PROCEDIMIENTO:
No. DE HOJAS 4
ELABORÓ:
CÓDIGO:
TÍTULO DEL WORK PAPER: : Estructuras algebraicas
DPTO.: Facultad de Ingeniería
DESTINADO A:
DOCENTES
ALUMNOS
X
ADMINIST.
OTROS
OBSERVACIONES:
FECHA DE DIFUSIÓN:
FECHA DE ENTREGA:
26
FACULTAD DE INGENIERIA
ESTRUCTURAS ALGEBRAICAS
Una Estructura Algebraica es un objeto matemático consistente en un conjunto no vacío y una relación ó ley de composición
interna definida en él.
En algunos casos más complicados puede definirse más de una ley de composición interna y también leyes de composición
externa.
Empecemos por recordar algunas definiciones:
Operación binaria ó Ley de composición interna definida en un conjunto no vacío A
Es una aplicación o función  del producto cartesiano de A x A en A
En símbolos:  es una ley interna en A   : A x A  A
Es decir
(a1, a2 )  a1  a2
Ejemplo 1
La suma ó la multiplicación en N , en Z , en Q , en R ó en C.
Ejemplo 2
Las siguientes tablas definen leyes de composición interna en el conjunto
A = {a , b , c }
i)
ii)
Ley de composición externa
Una ley de composición externa definida en A con operadores de B es toda función ó aplicación  de B x A en A.
En símbolos
 es ley externa en A con operadores en B  B x A  A
es decir, si b  B y a  A la imagen del par (b ; a) = b  a  A
Según las propiedades que deban satisfacer estas leyes de composición, se tienen los distintos tipos de estructuras ó
sistemas axiomáticos.
Monoide
El par (A ,  ) donde A es un conjunto no vacío dotado de una operación ó ley de composición interna  se denomina
monoide.
Ejemplos de monoides
( N , + ) , ( Z , + ) , ( Q , + ) , son monoides.
( N , - ) no es un monoide porque la sustracción no es ley de
27
FACULTAD DE INGENIERIA
composición interna en N.
( N ,  ) donde  está definido como a  b = máx.{a , b}
es un monoide.
Semigrupo
Un monoide asociativo se denomina semigrupo.
Si la ley de composición interna también es conmutativa se llama semigrupo conmutativo.
Si existe el elemento neutro se dice que es un semigrupo con unidad ó semigrupo con identidad.
El elemento neutro de llama identidad.
Ejemplos de semigrupos
( N , + ) es un semigrupo conmutativo sin elemento neutro.
( N0 , + ) es un semigrupo conmutativo con elemento neutro, el 0.
( N ,  ) es un semigrupo conmutativo con elemento neutro ó identidad igual a 1.
Grupo
Sea el par (A ,  ) , donde A es un conjunto no vacío dotado de una ley de composición interna binaria  :
(A ,  ) es un grupo ó se define sobre A una estructura de grupo sí:
a)  es asociativa. Es decir a , b , c : a, b, c  A 
a  b  c  a  b  c
b)  posee elemento neutro en A. Es decir e  A / a , si a  A  a  e  e  a  a
c) Todo elemento de A es invertible en A respecto de  .
Es decir a  A , a´ A / a  a´ a´ a  e
Grupo Abeliano ó Grupo conmutativo es cuando además de ser un grupo,
d)  es conmutativa. Es decir a , b : a, b  A  a  b  b  a
Si G = (A ,  ) es un grupo, se dice que es un grupo finito si el conjunto A es finito y su cardinal se llama orden del grupo.
Ejemplos
1) El par ( Z ,  ) donde Z es el conjunto de los números enteros y  es una operación definida como a  b = a + b +
3 forma un grupo abeliano.
Comprobación:
 es una ley de composición interna en Z pues si a y b  Z , a + b + 3  Z
 es asociativa pues
a  b  c = (a + b +3)  c = a + b +3 + c +3 = a + b + c + 6
y a  b  c  = a  (b + c + 3) = a + b + c + 3 + 3 = a + b + c + 6
28
FACULTAD DE INGENIERIA
 tiene elemento neutro e = –3 , pues
a  A , a  e = a entonces a + e +3 = a  e = –3
y e  a = a entonces e + a + 3 = a  e = –3
/ a  a  e , en nuestro caso a  a = –3  a  a  3 = –3 luego
a´ = – a – 6 es inverso a derecha a  a  3  a  a  3 = –3 luego a´ = – a – 6 es inverso a izquierda
 tiene inverso a
, a
 es conmutativa pues a  b = a + b + 3 = b + a + 3 = b  a
Otros ejemplos:
1) (Z,+) ; (Q,+) ; (R,+) y (C,+)
Son grupos abelianos . También se llaman grupos aditivos debido a la operación aditiva.
2 ) ( N , + ) No es grupo. No tiene neutro ni inverso de cada elemento.
3 ) ( N0 , + ) No es grupo. Tiene neutro, el 0 , pero no tiene inverso
aditivo.
4 ) ( Q ,  ) No es grupo, el 0 no tiene inverso multiplicativo.
5 ) ( R ,  ) No es grupo, el 0 no tiene inverso multiplicativo.
6 ) ( Q – { 0 } ,  ) y ( R – { 0 } ,  ) Son grupos.
Subgrupo
Un subconjunto no vacío B, del conjunto A es un subgrupo de ( A ,  ) si y solo sí ( B ,  ) es un grupo.
Por ejemplo, ( Z , + ) es un subgrupo de ( Q , + ).
Si en estas estructuras se introduce una nueva ley de composición interna con ciertas restricciones, se obtienen ternas
ordenadas del tipo (A ,  ,  ) que también son estructuras algebraicas.
Estas nuevas estructuras son:
Anillo
Dados, un conjunto no vacío A y dos leyes de composición interna  y  , la terna ordenada (A ,  ,  ) tiene
estructura de Anillo si y solo si
a)  es asociativa. Es decir a , b , c : a, b, c  A   a  b  c  a  b  c 
29
FACULTAD DE INGENIERIA
b)  posee elemento neutro en A. Es decir e  A / a , si a  A  a  e  e  a  a
c) Todo elemento de A es invertible en A respecto de  .
Es decir a  A , a´ A / a  a´ a´ a  e
d)  es conmutativa. Es decir a , b : a, b  A  a  b  b  a
Estas 4 propiedades muestran que ( A ,  ) es un grupo abeliano.
e)  es asociativa. Es decir a , b , c : a, b, c  A  (a  b)  c = a  ( b  c)
Esta propiedad muestra que ( A ,  ) es un semigrupo.
f)  distribuye doblemente sobre  . Es decir, a , b , c : a, b, c  A
 a  (b  c ) = ( a  b )  (a  c ) y (b  c )  a = (b  a )  ( c  a )
Resumiendo podemos decir que:
(A ,  ,  ) es un Anillo sii (A ,  ) es un grupo abeliano ; ( A ,  ) es un semigrupo y la segunda operación distribuye
sobre la primera.
Una aclaración oportuna
Como la operación  es aditiva y la operación  es multiplicativa, es común representarlas con los conocidos signos de la
suma y el producto, pero en todos los casos deberá respetarse la definición que corresponde a cada operación.
Con esta aclaración debe quedar claro que ( A , + ,  ) representa una estructura algebraica, talvez un anillo, pero que la
operación + y la operación  no representan la suma y el producto conocido, salvo ello esté expresamente indicado.
Con igual margen de tolerancia en la interpretación de este tema, debemos decir que el elemento neutro de la operación
aditiva se representa con 0 (cero) y el neutro de la operación multiplicativa con 1 (uno) sin que ellos sean necesariamente el
0 y 1 conocidos.
Si además
g)  conmutativa. Es decir a , b : a, b  A  a  b = b  a
entonces tenemos un Anillo conmutativo.
h)  posee elemento neutro en A. Es decir e  A / a , si a  A  a e  e a  a
entonces tenemos un Anillo con identidad ó Anillo con unidad.
i) Todo elemento de A distinto de cero es invertible en A respecto de  .
Es decir a  A , a  0 , a´ A / a  a´ = a´  a = e entonces se llama
Anillo de división.
Ejemplos
1.- ( N , + ,  ) con las operaciones conocidas no es un anillo, pues en N no existe neutro para la adición.
30
FACULTAD DE INGENIERIA
2.- ( N0 , + ,  ) con las operaciones conocidas no es anillo, pues N0 carece de inversos aditivos.
3.- ( Z , + ,  ) con las operaciones conocidas, es un anillo conmutativo con unidad.
Anillos sin divisores de cero
Un anillo (A ,  ,  ) se dice sin divisores de cero si y solo sí elementos no nulos de A dan producto no nulo.
En símbolos:
(A ,  ,  ) carece de divisores de cero si y solo sí a , b : a, b  A si a  0 y b  0
entonces a  b  0
Anillo de integridad
(A ,  ,  ) es un Anillo de integridad si y solo sí (A ,  ,  ) es un anillo y 0 es su único divisor de cero
Dominio de integridad
La terna (A ,  ,  ) se llama Dominio de integridad si y solo sí (A ,  ,  ) es un Anillo conmutativo con unidad y sin
divisores de cero.
Dicho de otra manera, un Dominio de integridad es un Anillo conmutativo con identidad y de integridad.
Ejemplos
1.- ( Z , + ,  ) con las operaciones conocidas es un dominio de integridad.
2.- ( Q , + ,  ) ; ( R , + ,  ) y ( C , + ,  ) con las operaciones conocidas son dominio de integridad.
3.- Los polinomios en una indeterminada ( o más ) con coeficientes en Q , R ó C forman dominio de integridad con las
operaciones conocidas.
Cuerpo
La terna ordenada ( A , + ,  ) es un cuerpo, o tiene estructura de cuerpo si y solo si
( A , + ,  ) es un anillo de división conmutativo.
Esto es: ( A , + ,  ) es un cuerpo si y solo si ( A , + ,  ) es un anillo conmutativo, con unidad cuyos elementos no
nulos admiten inverso multiplicativo.
Un cuerpo queda caracterizado por las siguientes estructuras:
( A , + ,  ) es un cuerpo si y solo si
a) ( A , + ) es un grupo abeliano.
b) ( A – {0} ,  ) es un grupo abeliano.
c)  distribuye respecto de +
31
FACULTAD DE INGENIERIA
Ejemplos
1.- ( Z , + ,  ) con las operaciones conocidas, no es cuerpo, pues Z carece de inversos multiplicativos.
2.- ( Q , + ,  ) ; ( R , + ,  ) y ( C , + ,  ) con las operaciones conocidas son cuerpos.
3.- Todo cuerpo es un dominio de integridad.
Para proveer de un ejemplo de estructura algebraica no tan conocida, definiremos el conjunto Zn llamado conjunto de los
enteros modulo n.
Enteros módulo n (Zn)
Si n es un número entero tal que n  2 , se denomina Zn al conjunto
Zn = { 0 , 1 , 2 , 3 ,..., n-1}
Este conjunto, provisto de las operaciones de suma y producto definidas así:
+ suma : si h y k pertenecen a Zn , entonces h + k es igual al resto de la división de h + k por n.
Ejemplo: si n = 8 ; h = 5 y k = 7 , entonces h + k = 4
 producto : si h y k pertenecen a Zn , entonces h  k es igual al resto de la división de h  k por n.
Ejemplo: si n = 8 ; h = 5 y k = 7 , entonces h  k = 3
La terna (Zn , + ,  ) es un anillo conmutativo con unidad. Se llama Anillo de los enteros módulo n.
( Zn , + ,  ) es un dominio de integridad si y solo sí n es primo.
Esto puede verse en las siguiente tablas de operaciones en el conjunto Zn
Para n = 3 Zn = { 0 , 1 , 2 } las tablas de operaciones son:
Para la suma
+
0
1
2
Para el producto
0
0
1
2
1
1
2
0
2
2
0
1

0
1
2
0
0
0
0
1
0
1
2
2
0
2
1
El producto No posee divisores de cero
Para n = 4 Zn = { 0 , 1 , 2 , 3 } las tablas de operaciones son:
Para la suma
Para el producto
32
FACULTAD DE INGENIERIA
+
0
1
2
3
0
0
1
2
3
1
1
2
3
0
2
2
3
0
1

3
3
0
1
2
0
1
2
3
0
0
0
0
0
1
0
1
2
3
2
0
2
0
2
3
0
3
2
1
El producto posee divisores de cero
Espacio Vectorial
Un espacio vectorial sobre un cuerpo K es un conjunto V , cuyos elementos se denominan vectores, provisto de dos
operaciones, una interna que se denomina suma y otra externa que se denomina producto y que cumplen ciertas
propiedades.
La operación externa , multiplica un elemento del conjunto K por un elemento del conjunto V.
Notación
Esta estructura suele representarse de las siguientes maneras:
Como la cuaterna ordenada ( V , + , K ,  ) ; como la terna ordenada ( K , V ,+ ) y también es muy usual la expresión
sintetizada VK  , todas ellas se leen Espacio Vectorial V sobre el cuerpo K . o simplemente K – espacio vectorial.
Las operaciones enunciadas deben cumplir las siguiente propiedades:
1. ( V , + ) es un Grupo conmutativo
a) + Es asociativa
b) + Es conmutativa
c) + Tiene neutro
d) + Tiene inverso
2. La operación externa asocia de la siguiente manera:
a , b : a, b  K y x  A , a  ( b  x ) = ( a  b )  x
3. La operación externa distribuye sobre la interna de la siguiente manera:
a : a  K y  x , y  A , a  ( x + y ) = a  x + a  y
4.
La operación externa tiene elemento neutro.
Ejemplos
1.- ( Rn, + , R ,  ) es un Espacio Vectorial con las suma y el producto conocidos. Siendo Rn , con n  1 el conjunto de las
n – uplas de números reales.
2.- ( K x , + , K ,  ) es un Espacio Vectorial con la suma y el producto conocidos, siendo K un cuerpo y K x el conjunto
de los polinomios en una indeterminada con coeficientes en K.
33
FACULTAD DE INGENIERIA
3.- ( Rm x n, + , R ,  ) en el Espacio Vectorial de la matrices de orden m x n en el cuerpo de los reales, con la suma y el
producto conocidos.
Morfismo u Homomorfismo
Una aplicación de conjuntos f: A  B se dirá que es un morfismo de la estructura
(A ,  ) en la estructura (B ,  ) o simplemente un morfismo de A en B si se cumple que:
x , y  A
; f(x  y) = f(x)  f(y)
Ejemplo:
Sean las estructuras ( R , + ) y ( R + ,  ) con las operaciones + y  usuales.
La aplicación f : R  R + definida por f(x) = 2 x es un morfismo de estas estructuras ya que cumple que:
f (x + y) = 2 x + y = 2 x  2 y = f (x)  f (y)
Endomorfismo
Se llama así a todo morfismo de A en A.
Monomorfismo
Se llama así a todo morfismo inyectivo.
Epimorfismo
Se llama así a todo morfismo sobreyectivo.
Isomorfismo
Se llama así a todo morfismo biyectivo.
Automorfismo
Se llama así a todo endomorfismo biyectivo.
Ejemplos
1.
Sean las estructuras ( R3 , + ) y ( R2 x 2 , + ) y la aplicación
 x1 0 

x2 x3 
f ( x1 , x2 , x3 ) = 
34
FACULTAD DE INGENIERIA
Las operaciones consideradas son las de suma de ternas ordenadas de números reales y la de suma de
matrices.
Entonces, como :
f  x1, x2 , x3    y1, y2 , y3   = f  x1  y1 ,x2  y2 ,x3  y3  =
0 
 x1  y1
 x1 0 
 y1 0 
x  y x  y  =  x x  +  y y  =
2
3
3
3
3
 2
 2
 2
=
f x1, x2, x3  + f y1, y2, y3 
f es un morfismo.
Además es inyectivo, es decir un monomorfismo.
puesto que x  y  al dominio, resulta:
0
x
f x1, x2, x3  =  1
  f y1, y2, y3  =
x2 x3 
 y1 0 
y y 
3
 2
1 2 
 no es imagen de nadie.
3 4
Para probar que no es sobreyectivo, basta ver que, por ejemplo 
2. f : R  R tal que f (x) = – 3x es un automorfismo respecto a la suma.
Es morfismo pues
f (x + y ) = – 3 (x + y ) = – 3x – 3y = f (x ) + f (y )
f es biyectiva porque:
es inyectiva:  x  y ; f (x )  f (y )
ya que – 3x  – 3y
y es suryectiva:  y  R  x  R tal que f (x ) = y ;
– 3x = y entonces x = –
y
3
3. f : R  R tal que f(x) = x + 1 no es homomorfismo respecto a la adición. Efectivamente no cumple la definición de
morfismo
f (x + y)  f (x) + f (y)
ya que
x + y + 1  x +1 + y + 1 = x + y + 2
35
FACULTAD DE INGENIERIA
Es interesante saber que la Topología es la parte de la matemática que se ocupa de estudiar los conjuntos estructurados
mediante relaciones que nos permiten decir cuando un elemento del conjunto es “contiguo” o próximo a una parte del
mismo.
Topología deriva del griego que significa:
Topos: Lugar , extensión ó posición.
Logos: Ciencia ó saber.
Luego la topología puede definirse como la “ Ciencia de la extensión ó del lugar”.
36
FACULTAD DE INGENIERIA
WORK PAPER # 7
PROGRAMA DE CONTROL DE CALIDAD
No. DE PROCEDIMIENTO:
No. DE HOJAS 4
ELABORÓ:
CÓDIGO:
TÍTULO DEL WORK PAPER: : Teoría de Conjuntos
DPTO.: Facultad de Ingeniería
DESTINADO A:
DOCENTES
ALUMNOS
X
ADMINIST.
OTROS
OBSERVACIONES:
FECHA DE DIFUSIÓN:
FECHA DE ENTREGA:
37
FACULTAD DE INGENIERIA
TEORÍA DE CONJUNTOS
Conjuntos numéricos
Recuerde las formas de definir un conjunto: por extensión y por comprensión
Números naturales
Los puntos sucesivos significan: "y así sucesivamente"
Son los que se utilizan para contar objetos existentes
En algunos casos este conjunto incluye el cero.
En ese caso se anota
N a veces se lo denomina: enteros positivos (
)
* ¿ Tiene este conjunto primer elemento ?
* ¿ Tiene este conjunto último elemento ?
* Dado un elemento cualquiera, ¿ se puede decir que elemento lo precede?
* Dado un elemento cualquiera, ¿se puede decir que elemento le sigue?
Podemos graficar mediante un diagrama de Venn de la siguiente manera:
También podemos verlos como una serie de puntos alineados y equidistantes
Operemos con estos números
3 +1
4 -3
=
=
4
1
38
FACULTAD DE INGENIERIA
3 -4
=
?
Como llegamos a una operación que no podemos resolver. Es necesario extender este conjunto.
Números enteros
Son los naturales más sus simétricos y el cero.
* ¿ Tiene este conjunto primer elemento ?
* ¿ Tiene este conjunto último elemento ?
* Dado un elemento cualquiera, ¿ se puede decir que elemento lo precede?
* Dado un elemento cualquiera, ¿se puede decir que elemento le sigue?
Podemos graficar mediante un diagrama de Venn de la siguiente manera:
También podemos verlos de la siguiente manera
Operemos con estos números:
3-4
2* 3
6: 2
3: 2
=
=
=
=
-1
6
3
?
Como llegamos a una operación que no podemos resolver. Es necesario extender este conjunto.
Números Racionales
Q = {a sobre b, tal que a y b pertenecen a Z y b es distinto de cero}
De aquí en adelante no aclararemos más que los denominadores deben ser distintos de cero.
También llamados fracciones
39
FACULTAD DE INGENIERIA
* ¿ Tiene este conjunto primer elemento ?
* ¿ Tiene este conjunto último elemento ?
* Dado un elemento cualquiera, ¿ se puede decir que elemento lo precede?
* Dado un elemento cualquiera, ¿se puede decir que elemento le sigue?
Podemos graficar mediante un diagrama de Venn de la siguiente manera:
También los podemos ver de la siguiente manera
Operemos con estos números
Reflexione sobre esta imposibilidad hasta comprender realmente.
Rehaga los ejemplos dados en clase.
Obviamente necesitamos crear un conjunto que agrupe este tipo de números.
Números irracionales
Son los que no se pueden expresar como racionales
* ¿ Tiene este conjunto primer elemento ?
* ¿ Tiene este conjunto último elemento ?
* Dado un elemento cualquiera, ¿ se puede decir que elemento lo precede?
* Dado un elemento cualquiera, ¿se puede decir que elemento le sigue?
40
FACULTAD DE INGENIERIA
Podemos graficar mediante un diagrama de Venn de la siguiente manera:
Podemos graficar de la siguiente manera
Números reales:
Con lo cual obtenemos la denominada recta real. (Piense en las dos rectas cribadas sobrepuestas)
Recuerde: una recta es una sucesión infinita de puntos alineados.
Entre dos puntos siempre existe otro punto, o bien entre dos puntos existen infinitos puntos (reflexione sobre estas dos
cuestiones)
A cada número real le corresponde un punto y a cada punto le corresponde un número real.
De aquí en más siempre que hablemos de número nos referiremos a un número real, en caso contrario se hará
expresa mención.
A cada número le corresponde un punto y a cada punto le corresponde un número.
* ¿ Tiene este conjunto primer elemento ?
* ¿ Tiene este conjunto último elemento ?
* Dado un elemento cualquiera, ¿ se puede decir que elemento lo precede?
* Dado un elemento cualquiera, ¿se puede decir que elemento le sigue?
Lamentablemente aquí no terminan los problemas.
41
FACULTAD DE INGENIERIA
Por ejemplo si queremos resolver:
nos veremos nuevamente en problemas. Pero para nosotros está bien por ahora. Mencionaremos este problema más
adelante cuando hablemos de parábolas. (Leibnitz agradecido,¿?)
División de un segmento en una razón dada.
Trate de comprobar que el valor 2/3 aparece, independientemente del ángulo elegido y el largo del segmento seleccionado,
en la misma posición en la recta real, recordando la explicación dada durante la clase.
Hallará la respuesta a continuación, pero trate de resolver por si mismo.
A continuación obtenemos un segmento de longitud 4/3 de dos formas distintas. Explique claramente cuál fue el criterio
utilizado en cada caso.
42
FACULTAD DE INGENIERIA
* Defina por extensión el conjunto de todos los nombres de varón, en Español, que no contengan ninguna
de las letras del nombre "Carlos".
* Defina por extensión el conjunto que contenga todos los números naturales en cuyo nombre, en Español,
tengan la misma cantidad de letras que representan.
* Defina por extensión el conjunto que contenga todos los números naturales en cuyo nombre, en Inglés,
tengan la misma cantidad de letras que representan.
* Defina por extensión el conjunto que contenga todos los números naturales en cuyo nombre, en Italiano,
tengan la misma cantidad de letras que representan.
* (en Alemán)?
* Recuerde la explicación sobre como hallar el punto que representa a
sobre la recta real.
Sobre la recta real halle:
*
*
*
En la tabla que sigue, siempre que sea posible ( pregunte en clase sobre las imposibilidades ):
* Marque a que conjunto/s pertenecen los números de la primera columna.
* Escriba el número como racional, de tres maneras distintas.
* Convierta cada número en notación decimal expresándolos con uno, dos, tres y cinco decimales.
(Piense que, en algunos casos, no es exactamente el mismo número)
43
FACULTAD DE INGENIERIA
* Ordene todos los números en forma creciente.
* Marque, de ser posible, su ubicación en la recta real.
(recuerde la explicación sobre "división de un segmento en una razón dada")
*
-5
8.3
Signo
Natural
Entero
Irracional
Racional
-10.3
8
0
-
Determine sobre una misma recta real los puntos que representan a: 0, 1,
Recién después de resolver vea la solución e las páginas siguientes.
44
FACULTAD DE INGENIERIA
45
FACULTAD DE INGENIERIA
Se muestran a continuación las reglas prácticas para convertir un número racional en notación decimal a notación racional.
Aproximación 1. Un número con parte entera igual a cero y la parte decimal periódica pura.
El numerador será igual a la parte periódica y el denominador tantos nueves como dígitos contenga el período:
Aproximación 2. Un número con parte entera distinta a cero y la parte decimal periódica pura.
Será igual a la parte entera más un racional que tendrá como numerador la parte periódica y como denominador tantos
nueves como dígitos contenga el período:
Observe que este caso contiene al anterior. Compruebe con algunos ejemplos.
Aproximación 3.
Un número con parte entera distinta a cero y la parte decimal periódica impura.
Será igual la parte entera más un racional que tendrá como numerador a la parte no periódica seguida de la parte periódica
menos la parte no periódica, y como denominador tantos nueves como dígitos contenga el período y tantos ceros como
dígitos contenga la parte no periódica:
46
FACULTAD DE INGENIERIA
Observe que este caso contiene al anterior. Compruebe con algunos ejemplos.
Por lo tanto podremos tomar este último caso como regla general. Obtenga los racionales correspondientes
47
FACULTAD DE INGENIERIA
WORK PAPER # 8
PROGRAMA DE CONTROL DE CALIDAD
No. DE PROCEDIMIENTO:
No. DE HOJAS 4
ELABORÓ:
CÓDIGO:
TÍTULO DEL WORK PAPER: : Conjuntos, relaciones y funciones
DPTO.: Facultad de Ingeniería
DESTINADO A:
DOCENTES
ALUMNOS
X
ADMINIST.
OTROS
OBSERVACIONES:
FECHA DE DIFUSIÓN:
FECHA DE ENTREGA:
48
FACULTAD DE INGENIERIA
CONJUNTOS , RELACIONES Y FUNCIONES
Conjuntos
Definición de Conjuntos
1) Enumerando
A = { 1,3,5,7 }
2) Por Propiedades
A = { x | x es impar } = { x | (x mod 2)=1 }
3) Intervalos
A = [ 1,5 ] = { 1,2,3,4,5 }
A = ( 1,5 ) = { 2,3,4 }
Conjuntos especiales
Conjunto Vacío
Conjunto Universal
Ø
U
Conjunto Números Enteros Positivos
1,2,3,...
Conjunto Números Naturales
0,1,2,3,...
Conjunto Números Enteros
...,-3,-2,-1,0,1,2,3,...
Conjunto Números Racionales
(Razones de enteros, i.e. quebrados)
y
Conjunto Números Irracionales
-1, ¾, ...
49
FACULTAD DE INGENIERIA
Cardinalidad
Operador de Cardinalidad
long(A): Numero de elementos del conjunto A
A=[1,5], long(A)=5
Finito
Número de elementos es finito
A=[1,5]
Infinito
Número indefinido de elementos
A = { x | x es par }
Contable
Sus elementos son enumerables
(puede ser infinito).
No Contable
Dado cualquier pareja de elementos siempre existirá un elemento intermedio entre ambos.
Operaciones para Conjuntos
x
| x
x
Unión
x
| x
Intersección
x
A-B=A\B={x
Equivalencia: B -
| x
x
Diferencia
(Complemento Relativo)
c
Complemento
Ac
= ~A = ¬A =
{ (x
x
x
=U-A={x
| x
Diferencia Simétrica
- A) =
x
x
x
x
x
Subconjunto
x( x x
50
FACULTAD DE INGENIERIA
i
={i
x
i
}
Unión / Intersección Múltiple
i
Conjunto Potencia
(A) = El conjunto de todos los subconjuntos de A
Si A tiene n elementos, entonces (A) tiene 2n subconjuntos.
Ej: A={0,1}, luego (A)={Ø, {0},{1},{0,1}}. Nota: (Ø)={Ø}
Formalmente: long( (A)) = 2long(A)
Producto Cartesiano
donde: <a,b> denota un par ordenado, i.e. tupla-2.
Relaciones entre Conjuntos
Conjunto Propio
Conjunto Impropio
Conjuntos Disjuntos
Relaciones
51
FACULTAD DE INGENIERIA
Sean A y B conjuntos. Una relación de A a B es cualquier subconjunto R del producto cartesiano
A×B.
A
se
conoce
como
dominio
y
B
como
rango
de
R.
Ejemplo: Sean
P={x
I={x
|x
|x
x<12 } = { 1, 3, 5, 7, 11 }
x<10 } = { 1, 3, 5, 7, 9 }
Por lo tanto:
P × I = { <1,1>, <1,3>, <1,5>, ... , <11,9>, }
Sea:
R = { <1,1>, <3,3>, <5,5>, <7,7>, <11,9> }
Gráficamente:
I
Matriz:
1
3
5
7
9
<1,1>
<1,3>
<1,5>
<1,7>
<1,9>
1
3
P
5
7
11
<3,1>
<3,3>
<3,5>
<3,7>
<3,9>
<5,1>
<5,3>
<5,5>
<5,7>
<5,9>
<7,1>
<7,3>
<7,5>
<7,7>
<7,9>
52
FACULTAD DE INGENIERIA
<11,1>
<11,3>
<11,5>
<11,7>
<11,9>
Grafo:
Relaciones Especiales
Relación de Equivalencia
{ < x,x
E
R-1
Relación Inversa
Propiedades para Relaciones
Reflexiva
Para toda x
Irreflexiva
Para toda x
xRx
xRx
Simétrica
Para toda xRy, existe yRx
Asimétrica
Para cada xRy, no existe yRx
53
FACULTAD DE INGENIERIA
Antisimétrica
Para cada xRy, no existe yRx, pero si xRx
Transitiva
Siempre que exista xRy, y yRz, existe xRz
La relación de equivalencia E es reflexiva, simétrica y transitiva.
Funciones
Sean X, Y conjuntos.
Una función f de X a Y es una relación R de X a Y tal que para cada f(x) existe un solo elemento y
Finalmente:
"La función f es una relación de X a Y".
< x,y
f
f(x) = y
"f mapea de X a Y".
f:
"f transforma X en Y",
donde: X es el dominio y Y es la imagen.
Existe una correspondencia uno-a-uno en f(x)=y, cuando para toda x
tienen el mismo número de elementos, i.e. cardinalidad.
existe una y
, y viceversa. Por lo que X y Y
Función Inversa: Toda función con correspondencia uno-a-uno posee una función inversa,
f-1(y) = x
si y solo si f(x) = y
54
FACULTAD DE INGENIERIA
WORK PAPER # 9
PROGRAMA DE CONTROL DE CALIDAD
No. DE PROCEDIMIENTO:
No. DE HOJAS 4
ELABORÓ:
CÓDIGO:
TÍTULO DEL WORK PAPER: : Teoría de Grafos
DPTO.: Facultad de Ingeniería
DESTINADO A:
DOCENTES
ALUMNOS
X
ADMINIST.
OTROS
OBSERVACIONES:
FECHA DE DIFUSIÓN:
FECHA DE ENTREGA:
55
FACULTAD DE INGENIERIA
TEORÍA DE GRAFOS
Definición:
Un grafo (o bien, un grafo o dirigido) G consiste en un conjunto de V de vértices (o nodos) y un conjunto E de lados
(o ramas) tales que cada lado e Є E está asociado a un par no ordenado de vértices. Si un lado e está asociado a un
único par de vértices v y w, se escribe e=(v,w) o bien e=(w,v). En este contexto, (v,w) denota un lado de un grafo no
dirigido y no un par ordenado de números.
Un grafo dirigido (o dígrafo) consiste en un conjunto V de vértices (o nodos) y un conjunto de E de lados (o ramas)
tales que cada lado e Є E está asociado a un par ordenado de vértices. Si un lado e está asociado a n par ordenado
único de vértices v y w, se escribe e=(v,w).
T
S
e2
e1
e3
e9
e10
W
e11
Z
U
e7
e6
e4
e8
V
X
e5
Y
En esta figura se muestra un grafo no dirigido donde {S,T,U,V,W,Y,Z} son los vértices y {e1,e2,e3,…..e11) son los lados.
La siguiente figura muestra un grafo dirigido:
V1
e1
e3
V2
V3
e4
e2
V5
e5
V4
V6
e6
Representaciones de grafos:
Existen dos métodos para la representación de un grafo:
56
FACULTAD DE INGENIERIA
Matriz de Adyacencia: Se selecciona un orden arbitrario para los vértices.
a
b
c
d
a
b
c
d
e
a
0
1
0
0
1
b c
1 0
0 1
1 1
0 0
1 1
d
0
0
0
0
1
e
1
1
1
1
0
e
Matriz de Incidencia: Se le asignan a las filas las marcas correspondientes a los vértices, y a las columnas las
correspondientes los lados.
b
x1
x2
x5
a
c
x6
x3
x7
e
x8
x4
a
b
c
d
e
x1
1
1
0
0
0
x2 x3 x4 x5 x6 x7 x8
0 1 0 1 1 0 0
1 0 0 0 0 0 0
1 0 1 1 0 1 0
0 0 1 0 0 1 1
0 1 0 0 0 1 1
d
57
FACULTAD DE INGENIERIA
WORK PAPER # 10
PROGRAMA DE CONTROL DE CALIDAD
No. DE PROCEDIMIENTO:
No. DE HOJAS 4
ELABORÓ:
CÓDIGO:
TÍTULO DEL WORK PAPER: : Arboles, Teoría de los cuatro colores
DPTO.: Facultad de Ingeniería
DESTINADO A:
DOCENTES
ALUMNOS
X
ADMINIST.
OTROS
OBSERVACIONES:
FECHA DE DIFUSIÓN:
FECHA DE ENTREGA:
58
FACULTAD DE INGENIERIA
ÁRBOLES TEORÍA DE LOS CUATRO COLORES
Cuatro colores son siempre suficientes para colorear un mapa.(Véase también:Colorear un mapa con 4 colores)
El mapa siguiente muestra que tres colores no bastan: Si se empieza por el país central a y se esfuerza uno en utilizar el
menor número de colores, entonces en la corona alrededor de a alternan dos colores. Llegando al país h se tiene que
introducir un cuarto color. Lo mismo sucede en i si se emplea el mismo método.
La forma precisa de cada país no importa; lo único relevante es saber cual país toca cual otro. Estos datos están incluidos en
el grafo donde los vértices son los países y las aristas conectan los que justamente son adyacentes. Entonces la cuestión
equivale a atribuir a cada vértice un color distinto del de sus vecinos.
Hemos visto que tres colores no son suficientes, y demostrar que con cinco siempre se llega, es bastante fácil. Pero el
teorema de los cuatro colores no es nada obvio. prueba de ello es que se ha tenido que emplear los ordenadores para
59
FACULTAD DE INGENIERIA
acabar la demostración (se ha hecho un programa que permitió verificar una multitud de casos , lo que ahorró muchísimo
tiempo a los matemáticos). Fue la primera vez que la comunidad matemática aceptó una demostración asistida por
ordenador.
Un juego muy conocido es el siguiente: Se dibuja tres casas y tres pozos. Los vecinos de las casas tienen todos el derecho
de utilizar los tres pozos. Como no se llevan bien en absoluto, no quieren cruzarse jamás. ¿ Es posible trazar los nueve
caminos que juntan las tres casas con los tres pozos sin que haya cruces ?
Cualquier disposición de las casas, los posos y los caminos implica la presencia de al menos un cruce.
Se nota Kn el grafo completo con n vértices, es decir en el cual cada par de vértices están conectadas por una arista. Kn,p es
el grafo compuesto de un grupo de nvértices y otro de p, tal que cada vértice del primer grupo está conectado con cada del
segundo,
y
no
hay
más
aristas.
El juego anterior equivale a descubrir si el grafo K3,3 es planario (se dice también plano), es decir si se puede dibujar en un
plano
sin
que
haya
cruces.
Y
la
respuesta
es
no.
Establecer qué grafos son planarios no es obvio, y tiene que ver con la topología.
60
FACULTAD DE INGENIERIA
PROGRAMA DE CALIDAD UDABOL
DIF – 001
TEORIA DE GRAFOS
En cierta competencia todos los alumnos gustan de Aritmética, algunos de Física y otros de química.
aritmética y Física y 470 de química o aritmética, cuántos no gustan de física?
Si 350 gustan de
Supongo que Alvaro toma huevos o tocino para su desayuno cada mañana durante el mes de enero. Si come tocino 26
mañanas y huevos 17 mañanas. ¿Cuántas mañanas come huevos y tocico?.
Un grupo de 70 personas ejecutan trabajos manuales utilizando tres materiales: barro madera y cartulina. Se sabe que
todos utilizan barro, 29 utilizan madera, 40 cartulina y 11 emplean los tres materiales. Cuántos utilizan únicamente barro?
Un ingeniero que dirige la construcción de un edificio de tres plantas, distribuye el personal de la siguiente manera: 43
trabajan en la primera planta, 58 en la tercera planta, 16 en la primera y segunda planta, 22 en la primera y tercera planta, 7
trabajan en las tres plantas. Si 52 trabajan en una sola planta y 37 dos plantas a la vez pero no en las tres. Cuántos
trabajan:
a) En la primera y segunda, pero no en la tercera
b) En la segunda o tercera pero no en la primera
c) Únicamente en la primera
d) Cuántos en total.
61
FACULTAD DE INGENIERIA
PROGRAMA DE CALIDAD UDABOL
DIF – 002
CAMINOS Y CIRCUITOS
Caminos y circuitos:
Veremos las definiciones formales de caminos y circuitos, y se estudian estos conceptos en detalle.
Sea G un grafo y sean v y w vértices en G.
Un Camino, de longitud n de v a w es una sucesión de lados que va de v a w y la cual tiene n lados distintos entre sí.
Un camino simple, de longitud n de v a w es uno de la forma (v0, v1,………vn), en donde V0=v y vn=w, y vo, v1, v2, ….vn,
son distintos entre sí.
Un circuito es un camino de v a v.
Un circuito simple, es un circuito de la forma (v0, v1,………vn), en donde v0=vn y v0, v1, v2, ….. Vn-1 son distintos entre
sí.
Ejemplo
c
d
b
g
a
e
f
62
FACULTAD DE INGENIERIA
Sucesión
de lados
Camino?
Camino simple?
Circuito?
(a,b,d,c,b,a)
no
no
no
(f,e,b,d,c,b,a)
si
no
no
(f,e,b,d)
si
si
no
(b.f.e.b,d,c,b)
si
no
si
(e,f,b,e)
si
no
si
Circuito
simple?
no
no
no
no
si
63