La deducción de la frase “El joven atrapa la pelota” con las reglas anteriores se describe por el árbol que se muestra a continuación. En el estudi...

La deducción de la frase “El joven atrapa la pelota” con las reglas anteriores se describe por el árbol que se muestra a continuación. En el estudio de la lingüística, la sintaxis se refiere a la estructura gramatical de las oraciones y semántica a los significados de las palabras y sus interrelaciones. Una frase puede ser sintácticamente correcta pero semánticamente incorrecta, como en la frase sin sentido “la joven pelota atrapa al hombre”, que se puede deducir de las reglas antes dadas. O una frase puede contener errores sintácticos pero no semánticos que, como, por ejemplo, cuando un niño de dos años, dice, ¡mi hambre! John Backus (1924-1998) Peter Naur (nació en 1928) Ejemplo 10.5.4 Estructura de moléculas de hidrocarburos El físico alemán Gustav Kirchhoff (1824-1887) fue el primero en analizar el comportamiento de árboles matemáticos en relación con la investigación de circuitos eléctricos. Poco después (e independiente), el matemático inglés Arthur Cayley utilizaron la matemática de árboles para enumerar todos los isómeros de determinados hidrocarburos. Las moléculas de hidrocarburos están compuestas de carbono e hidrógeno; cada átomo de carbono puede formar hasta cuatro enlaces químicos con otros átomos y cada átomo de hidrógeno puede formar un enlace con otro átomo. Por tanto la estructura de las moléculas de hidrocarburos se pueden representar por grafos, como los que aparecen después, en las que los vértices representan átomos de hidrógeno y carbono, denotados por H y C y las aristas representan los enlaces químicos entre ellos. IsobutanoButano Observe que cada uno de estos grafos tiene cuatro átomos de carbono y diez átomos de hidrógeno, pero los dos grafos muestran diferentes configuraciones de átomos. Cuando dos moléculas tienen las mismas fórmulas químicas (en este caso C4H10) pero diferentes enlaces químicos, se denominan isómeros. Ciertas moléculas de hidrocarburos saturados contienen el máximo número de átomos de hidrogeno para un determinado número de átomos de carbono. Cayley demostró que si dicha molécula de hidrocarburos saturados tiene k átomos de carbono, entonces tiene 2k 2 átomos de hidrógeno. El primer paso para hacerlo es demostrar que el grafo de una molécula de hidrocarburos saturados de éstas es un árbol. Demuéstrelo mediante la demostración de contradicción. (Se debe finalizar la deducción del resultado de Cayley en el ejercicio 4 al final de esta sección). Suponga que hay una molécula de hidrocarburos que contiene el número máximo de átomos de hidrógeno para el número de sus átomos de carbono y cuyo grafo G no es un árbol. [Se debe deducir una contradicción.] Ya que G no es un árbol, G no es conexo o G tiene un circuito. Pero el grafo de cualquier molécula es conexo (todos los átomos en una molécula deben estar conectados entre sí) y así G tiene un circuito no trivial. Ahora las aristas del circuito pueden enlazar sólo los átomos de carbono porque cada vértice de un circuito tiene grado mínimo de 2 y un vértice del átomo de hidrógeno tiene grado 1. Elimine una arista del circuito y agregue dos aristas nuevas a cada uno de los vértices del átomo de carbono recién desconectado de un vértice del átomo de hidrógeno, como se muestra a continuación. La molécula resultante tiene dos átomos de hidrógeno más que la molécula dada, pero no se ha modificado el número de átomos de carbono. Esto contradice la suposición de que la molécula dada tiene el máximo número de átomos de hidrógeno para el número de átomos de carbono. Por lo que la suposición es falsa y así G es un árbol. Caracterización de árboles Hay una relación un poco sorprendente entre el número de vértices y el número de aristas de un árbol. Resulta que si n es un entero positivo, entonces cualquier árbol con n vértices (no importa su forma) tiene n ฀ 1 aristas. Tal vez incluso más sorprendente, un converso parcial de este hecho también es verdadero; es decir, cualquier grafo conexo con n vértices y n ฀ 1 aristas es un árbol. Se deduce de estos hechos que si incluso una arista nueva (pero no nuevo vértice) se agrega a un árbol, el grafo resultante debe contener un circuito. También, del hecho de que la eliminación de una arista de un circuito no desconecta un grafo, se puede demostrar que cada grafo conexo tiene una subgrafo que es un árbol. Resulta que si n es un entero positivo, cualquier grafo con n vértices y menos de n ฀ 1 aristas no es conexo. Un pequeño pero muy importante hecho necesario para obtener el primer teorema principal acerca de los árboles es que cualquier árbol no trivial debe tener al menos un vértice de grado 1. Lema 6.5.1 Cualquier árbol que tiene más de un vértice tiene al menos un vértice de grado 1. Una forma constructiva de entender este lema es imaginar un árbol T dado con más de un vértice. Elija un vértice al azar y busque hacia fuera a lo largo de una trayectoria de en busca de un vértice de grado 1. Cómo llegar a cada vértice nuevo, compruebe si tiene grado 1. Si lo hace, habrá terminado. Si no es así, salga del vértice a lo largo de una arista diferente de la que entró él. Ya que T está libre de circuito, los vértices que se incluyen en la trayectoria nunca se repiten. Y dado que el número de vértices de T es finito, finalmente el proceso de construcción de una trayectoria debe terminar. Cuando esto sucede, el vértice final de la trayectoria debe tener grado 1. Este proceso se muestra a continuación. Aquí inicia Búsqueda hacia afuera desde para encontrar el vértice ' de grado 1. e e' Este análisis es una forma precisa en la siguiente demostración. Demostración: Sea T un árbol particular arbitrariamente elegido que tiene más de un vértice y considere el algoritmo siguiente: Paso 1: Seleccione un vértice de T y sea e una arista que incide en . [Si no hubiera ninguna arista que incida en , entonces sería un vértice aislado. Pero esto contradice la suposición de que T es conexo (ya que es un árbol) y tiene al menos dos vértices.] Paso 2: Mientras que deg( ) 1, repita los pasos 2a, 2b y 2c: Paso 2a: Elija e como una arista que incide en tal que e = e. [Tal que una arista existe porque deg( ) 1 y así hay al menos dos aristas que inciden en .] Paso 2b: Sea el vértice en el otro extremo de e para . [Ya que T es un árbol, e no puede ser un bucle y por tanto e tiene dos puntos distintos extremos.] Paso 2c: Sea e e y . [Esto es sólo un proceso de cambio de nombre en preparación para una repetición del paso 2.] El algoritmo que se acaba de describir debe terminar finalmente porque el conjunto de vértices del árbol T es finito y T está libre de circuitos. Cuando se hace, se habrá encontrado un vértice de grado 1. Usando el lema 10.5.1 no es difícil demostrar que, de hecho, cualquier árbol que tiene más de un vértice, tiene al menos dos vértices de grado 1. Esta extensión del lema 10.5.1 se deja en los ejercicios del final de esta sección. Definición Sea T un árbol. Si T tiene sólo uno o dos vértices, cada uno se llama un vértice terminal. Si T tiene al menos tres vértices, entonces un