Matemáticas Discretas

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

“APUNTES PARA LA
MATERIA DE
MATEMÁTICAS
DISCRETAS”
PRESENTA

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