Estudio de dos familias de grafos combinatorios

Abstract

EN RELACION CON CIERTOS PROBLEMAS DE DISEÑO DE CIRCUITOS LOGICOS, SURGEN DOS CUESTIONES DE TIPO COMBINATORIO, QUE SE DESIGNAN RESPECTIVAMENTE COMO "PROBLEMA DE LOS RECUBRIMIENTOS" Y "PROBLEMA DE LOS ACOPLAMIENTOS", AL CONSIDERARLOS SOBRE GRAFOS, SE TRANSFORMAN EN OTROS PROBLEMAS SOBRE OBTENCION DE ACOPLAMIENTOS MAXIMOS EN UNOS GRAFOS CONCRETOS BK BIPARTITOS Y OTROS GN NO BIPARTITOS, AMBOS DE CARACTER COMBINATORIO. EL ESTUDIO SISTEMATICO DE DICHOS GRAFOS, ES EL PROPOSITO DE LA TESIS. LOS GRAFOS GN SE ESTUDIAN EXHAUSTIVAMENTE: CONEXION, DISTANCIAS, CICLOS MINIMOS, RELACION CON LAS JAULAS, NUMERO CROMATICO, FAMILIAS MAXIMAS DE VERTICES ENTRE AQUELLAS TALES QUE LA INTERSECCION DE DOS VERTICES CUALESQUIERA DE LAS MISMAS (CONSIDERADOS COMO SUBCONJUNTOS), SEA DE TAMAÑO AL MENOR R, CONJUNTOS INDEPENDIENTES MAXIMOS, CODIGOS PERFECTOS, ETC. TAMBIEN SE DETERMINAN LOS GRUPOS DE LOS AUTOMORFISMOS Y ARISTA-AUTOMORFISMOS DE GN, ASI COMO LOS DIVERSOS TIPOS DE SIMETRIA EN GN Y GN. RECOPILANDO RELACIONES YA CONOCIDAS Y APORTANDO OTRAS NUEVAS, SE EFECTUA UN ESTUDIO DE LAS RELACIONES ENTRE SIMETRIA, CONECTIVIDAD Y EXISTENCIA DE ACOPLAMIENTOS PERFECTOS O CASI-PERFECTOS EN LOS GRAFOS. LA APLICACION A LOS GRAFOS GN, ESTABLECE SU (N+1)-CONECTIVIDAD POR VERTICES Y ARISTAS, ASI COMO LA EXISTENCIA DE 1-FACTOR, O EL CARACTER FACTORCRITICO DE LOS MISMOS. ESTO MUESTRA LA EXISTENCIA DE SOLUCION AL "PROBLEMA DE LOS ACOPLAMIENTOS." EN CUANTO A LOS FRAFOS BK SE MUESTRAN SUS PROPIEDADES FUNDAMENTALES Y ESPECIALMENTE LOS ACOPLAMIENTOS MAXIMOS EN LOS MISMOS, RESOLVIENDOSE COMO CONSECUENCIA EL "PROBLEMA DE LOS RECUBRIMIENTOS" MEDIANTE UN ALGORITMO SIMPLE.