Un árbol T es un árbol generador de un grafo G si T es un subgrafo de G que contiene todos los vértices de G.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es así como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
En general un grafo G tendrá varios árboles generadores ,como el del ejemplo 1 el cual tiene a lo menos dos arboles generadores T1 yT2.
Algoritmos para hallar un árbol generador , que se base en el teorema de que el grafo G debe ser conexo, pueden ser los que se realizan a través de los métodos llamados buscar primero a lo ancho , buscar primero a lo largo y el de regreso al nivel anterior.
Arboles Generadores Mínimales.
Un Arbol Generador Minimal es el que resulta de la construcción en primer lugar de un Arbol generador, pero con la característica de ser el de menos peso del grafo al cual genera.
Por ejemplo sea un grafo ponderado ( con peso) con cinco vértices. La idea es construir un subgrafo que una a todos los puntos pero con el mínimo de peso (el peso se refiere al valor que se le da a cada uno de los lados de un grafo). Este subgrafo debe ser un árbol generador, ya que debe unir todos los vértices, debe ser conexo y debe haber un único camino entre cada par de vértices, por lo tanto, lo que se necesita es un árbol generador con el mínimo de peso, es a esto lo que se llama árbol generador minimal.
Sea G un grafo con peso. Un árbol generador mínimal de G es un árbol generador de G con peso mínimo.
Un árbol es un grafo simple en el cual existe un ún
ico camino entre cada par de vértices.
Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos.
Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz.
En la figura anterior G1 corresponde a lo que llamamos mediante la definición ARBOL, en el caso de G2, éste no corresponde debido a que contiene un ciclo.
Podemos destacar que cuando un grafo G es un Arbol, se reemplaza G, por R.
Para apoyar el entendimiento de las definiciones entregadas agregaremos algunos teoremas.
Teorema:
Si a, b son vértices de un árbol R (V,A), entonces hay un camino único que conecta estos vértices.
Teorema:
En cualquier árbol R= (V,A), |V| = |A| + 1.
Teorema:
Para cualquier árbol R = (V,A), si |A| >= 2, entonces R tiene al menos dos vértices colgantes.
Teorema:
Sea G un grafo simple con v vértices, entonces se puede decir:
· G es un árbol.
· G es conexo y no contiene circuitos.
· G es conexo y tiene (n-1) lados.
· G no contiene circuitos y tiene (n-1) lados.
Arboles con Raíz
Sea G un grafo dirigido, se denomina “árbol dirigido” si el grafo no dirigido asociado con G es un árbol. Cuando G es un árbol dirigido, se denomina “árbol con raíz” si hay un único vértice r, la raíz.
Sea G un grafo con raíz V0. Supóngase que x, y, z son vértices en G y que (v0, v1, ..., vn), es un camino en G.
· V(n-1) es el padre de v(n).
· V0, v1, ..., v(n-1) son los antepasados de v(n).
· V(n) es el hijo de v(n-1).
· Si x es un antepasado de y, entonces y es un descendiente de x.
· Si x e y son hijos de z entonces x e y son hermanos.
· Si x no tiene hijos entonces x es un vértice terminal.
· Si x no es un vértice terminal, entonces x es un vértice interno.
· El subgrafo de G que consiste en x y todos sus descendientes, con x como raíz, es el subarbol de G que tiene a x como raíz.
Sea R= (V,A) un árbol con raíz r. Si R no tiene otros vértices, entonces la raíz misma constituye el recorrido en orden previo, simétrico y posterior de R. Si |V| > 1, sean R1, R2, R3, ...., Rk los subarboles de R según se va de izquierda a derecha.
1. El recorrido de orden previo de R comienza en r y después pasa por los vértices de R1 en orden previo, a continuación por los vértices de R2 en orden previo, y así sucesivamente hasta que se pasa por los vértices de Rk en orden previo.
2. El recorrido en orden simétrico de R primero, se pasa por los vértices de R1 en orden simétrico, después por la raíz r y a continuación por los vértices de los subarboles R2, R3,...., Rk en orden simétrico.
3. El recorrido en orden posterior de R pasa por los vértices de los subarboles R1, R2,...., Rk en orden posterior y a continuación por la raíz.
Un árbol binario es uno con raíz en el cual cada vértice tiene un hijo a la derecha o un hijo a la izquierda, o viceversa, o bien ningún hijo. Un árbol binario completo es uno en el cual cada vértice tiene un hijo a la derecha y uno a la izquierda, o bien ningún hijo.
Teorema:
Si T es un árbol binario completo con i vértices internos, entonces T tiene i + 1 vértices terminales y 2i + 1 vértices en total.
Un árbol binario de búsqueda es un árbol binario T donde se han asociado datos a los vértices. Los datos se disponen de manera que para cualquier vértice v en T, cada dato en el subarbol a la izquierda de v es menor que el dato correspondiente a v.
La importancia de la matemática en el contexto del desarrollo científico y tecnológico de la humanidad, está determinada por la posibilidad de elaborar modelos matemáticos de los objetos estudiados por las diferentes ramas de la ciencia y la técnica es decir, describir mediante el lenguaje vigoroso de la matemática, las propiedades de los objetos reales. En la facultad de ingeniería a partir de la década de los ochenta se ha producido un paulatino desplazamiento de la matemática del continuo hacia la matemática discreta.
El acento en los algoritmos discretos usados en las ciencias de la computación hace necesario el trabajo con ciertas porciones de la matemática discreta suficientemente elementales como para poder formar parte con éxito de un programa inicial de matemáticas. La combinatoria clásica, la teoría elemental de números, la teoría de discretización de señales, etc., podrían ser considerados como candidatos para ello. No existe en la actualidad un texto adecuado que responda a estas necesidades que imponen los nuevos tiempos, sobre todo en las carreras de ingeniería electrónica e ingeniería de sistemas. No hay duda que en ingeniería, gran parte de la matemática del futuro tendrá otro sabor y este sabor será discreto.
La importancia de la "popularización" de la matemática discreta en los tiempos actuales creo que no admite discusión.
Veamos lo que dice Miguel De Guzmán en su texto "Tendencias innovadoras en educación matemática" en vez de elucubrar sobre su pertenencia:
"La matemática del siglo XX ha sido predominantemente la matemática del contínuo en la que el análisis, por su potencia y repercusión en las aplicaciones técnicas, ha jugado un papel predominante. El advenimiento de los ordenadores, con su inmensa capacidad de calculo, con su enorme rapidez, versatilidad, potencia de representación gráfica, posibilidades para la modelización sin pasar por la formulación matemática de corte clásico,... ha abierto multitud de campos diversos, con origen ya no en la fisica, como los desarrollos de siglos anteriores, sino en otras muchas ciencias como la economía, las ciencias de la organización, biología, ... cuyos problemas resultaban opacos, en parte por las enormes masas de información que había que tratar hasta llegar a dar con las intuiciones matemáticas valiosas que pudieran conducir a procesos de resolución de los dificiles problemas propuestos en estos campos. Por otra parte, el acento en los algoritmos discretos, usados en las ciencias de la computación, en la informática, asi como en la modelización de diversos fenómenos mediante el ordenador, ha dado lugar a un traslado de énfasis en la matemática actual hacia la matemática discreta. Ciertas porciones de ella son lo suficientemente elementales como para poder formar parte con éxito de un programa inicial de matemática. La combinatoria clásica, asi como los aspectos modernos de ella, tales como la teoría de grafos o la geometría combinatoria, podrían ser considerados candidatos adecuados. La teoría elemental de números, que nunca llegó a desaparecer de los programas en algunos países, podría ser otro. Se han realizado intentos por introducir estos elementos y otros semejantes pertenecientes a la matemática discreta en la enseñanza matemática inicial. Sucede que esto parece solo posible a expensas de otras porciones de la matemática con más raigambre de las que no se ve bien como se puede prescindir. Aunque parece bastante obvio que el sabor de la matemática del futuro será bastante diferente del actual por razón de la presencia del ordenador, aún no se ve bien claro cómo esto va a plasmarse en los contenidos de la enseñanza primaria y secundaria"
En la matemática actual no basta desarrollar una teoría para encontrar la solución de un problema, sino que los métodos derivados de la teoría deben ser algoritmizados y estos algoritmos discretos deben ser eficientes para poder ser realizados con la capacidad de cálculo actual. De otra parte el estudiante de ingeniería actual se enfrenta desarmado al diseño de circuitos digitales en las carreras de ingeniería electrónica y de sistemas; porque no conoce algoritmos elementales que proporciona, por ejemplo, la aritmética. La importancia de ésta en el diseño de juegos de estrategia es fundamental. Experiencias en semestres anteriores con algunos estudiantes me han convencido de ésta realidad.
Este curso pretende lograr los objetivos siguientes:
1. Introducir al alumno en técnicas de razonamiento lógico y razonamiento combinatorio, y en general, métodos discretos.
2. Se incluyen temas como algoritmos, inducción matemática, aritmética residual y sistemas numéricos.
3. Se hace un tratamiento matemático de lo que es un algebra de Boole, a partir del concepto de relación de orden.
4. Se introduce el concepto de grafos y de máquinas de tiempo finito que enfatiza la modelación y las aplicaciones.
5. Por ultimo, se tocan temas de discretización de señales haciendo énfasis en el concepto de sumatoria de convolución, ecuaciones en diferencias homogéneas y no homogéneas. Se finaliza con el estudio de la transformada Z.
6. Se incluyen gran variedad de aplicaciones, que buscan desarrollar la madurez matemática del estudiante mediante el estudio de un área tan diferente al cálculo. Los prerequisitos de este curso son principalmente una buena formación en álgebra de secundaria e interés por abordar y resolver ciertos tipos de problemas.
La visión que se presenta aquí es amplia, como requiere un curso general; posiblemente muchas personas tendrán una visión diferente de lo que acá se presenta de acuerdo a sus intereses y necesidades.
Pienso que para los cursos de la Universidad de Antioquia en Ingeniería de Sistemas e Ingeniería Electrónica, este es un adecuado curso introductorio.
Matemáticas Discretas
