Matemática Discreta

UNIVERSIDAD DE GUADALAJARA
CENTRO UNIVERSITARIO DE CIENCIAS EXACTAS E INGENIERÍAS
DEPARTAMENTO DE MATEMÁTICAS

“APUNTES PARA LA
MATERIA DE
MATEMÁTICAS
DISCRETAS”
P R E S E N T A

M.S.I. JOSÉ FRANCISCO VILLALPANDO BECERRA

ÍNDICE
ÍNDICE ............................................................................................................................1RELACIONES....................................................................................................................2
DEFINICIÓN Y SU REPRESENTACIÓN................................................................................ 2
OPERACIONES CON RELACIONES .................................................................................... 5
COMPOSICIÓN DE RELACIONES...................................................................................... 8
PROPIEDADES DE LAS RELACIONES................................................................................. 9
RELACIONES DE EQUIVALENCIA.....................................................................................12
ORDENES PARCIALES ...................................................................................................15INDUCCIÓN MATEMÁTICA .............................................................................................17
EL CONJUNTO DE LOS NÚMEROS ENTEROS ......................................................................17
CONJUNTOS FINITOS E INFINITOS NUMERABLES..............................................................19
FÓRMULAS INDUCTIVAS Y GENERALIZACIÓN...................................................................21
PRINCIPIO DE INDUCCIÓN MATEMÁTICA .........................................................................24
RELACIONES DE RECURRENCIA .....................................................................................28
PROGRESIONES ARITMÉTICAS Y GEOMÉTRICAS ...............................................................28
SUCESIONES RECURRENTES YECUACIÓN DE RECURRENCIA ..............................................32
SOLUCIONES HOMOGÉNEAS..........................................................................................36
SOLUCIONES PARTICULARES.........................................................................................39
SOLUCIONES TOTALES.................................................................................................42
PRINCIPIOS DE CONTEO ...............................................................................................44
REGLAS DE LA SUMA Y EL PRODUCTO .............................................................................44
RECURSOS DE CONTEO: LISTAS Y ÁRBOLES ....................................................................47
PERMUTACIONES Y COMBINACIONES.............................................................................49
PERMUTACIONES Y COMBINACIONES GENERALIZADAS .....................................................53
PRINCIPIOS ................................................................................................................57
PRINCIPIO DEEXCLUSIÓN-INCLUSIÓN........................................................................57
PRINCIPIO DE DIRICHLET..........................................................................................60
APLICACIONES (IDENTIDADES BÁSICAS Y TEOREMA DEL BINOMIO)....................................62
GRAFOS .........................................................................................................................65
DEFINICIONES BÁSICAS Y SU REPRESENTACIÓN..............................................................65
GRAFOS DIRIGIDOS Y NO DIRIGIDOS .............................................................................66
MULTIGRAFOS Y GRAFOS PESADOS (GRAFOS PONDERADOS) ............................................71
PASEOS (CAMINOS) Y CIRCUITOS (CICLOS) ....................................................................72
PASEOS Y...