SUCESIONES SIMBOLICAS
Las respuestas certificadas contienen información fiable, avalada por un equipo de expertos cuidadosamente seleccionados. En Brainly hay millones de respuestas de alta calidad, que han sido moderadas por los miembros más destacados de nuestra comunidad. Pero las respuestas certificadas son las mejores de las mejores.
Las sucesiones o continuidades o seguidillas, es una forma para definir a un grupo de números, figuras, símbolos, valores, dibujos que llevan un orden especifico y predecible, ordenados de una manera tal, que facilita su apreciación.Es un conjunto ordenado de números, elementos, figuras, cada uno de ellos es denominado término (o elemento o figura), y dependiendo de la cantidaddefinida de miembros que tiene y lo compone se le denomina: Longitud de la sucesión.
Abajo colocare figuras sobre ejemplos gráficos de una sucesión.
En el primero se aprecia la diferencia entre una sucesión de objetos figuras y números, y la otra es una gráficacion con una sucesión de función numérica definida
SUCESIONES ALFANUMERICAS
Estas sucesiones están conformadas por sucesiones literales y sucesiones numéricas, cada término de ambas mezclado da origen a un solo término de la sucesión alfanumérica. Ejemplo:
Hallar el término siguiente:
7a, 10ch, 13g, 16l,…
Para los números descubrimos que la ley de formación está dada por:
3 n + 4
Por tanto debe seguir como numero el: 19
Y las letras van en progresión dada por una disminución en la razón (r-1)
Además se incluye la “ch”, lo que da lugar a que se incluya también a la “ll”
Teniendo en cuenta esto la letra que sigue es la “p”
Entonces el término que sigue es “19p” .
Sucesiones gráficas (Havel & Hakimi)
Este método desarrollado por Havel y Hakimi será el que implementemos en el proyecto. Es gráfico y está basado en la reconstrucción del grafo, el cual obtenemos tras ir insertando vértices y aristas en sucesivas iteraciones.
Condiciones
Las condiciones para que una sucesión de grados de un grafo sea gráfica son:
·La suma debe ser par
·El valor máximo debe ser menor que la longitud. Por ejemplo la sucesión 6,4,4,2,1,1 no es gráfica pues el valor mayor de la sucesión (6) es igual que la longitud de esta (6).
·Si la sucesión t1-1, t2-1, t3-1,....., ts-1, d1, d2,......, dk es gráfica entonces también lo es la sucesión s, t1, t2, t3,....., ts, d1, d2,......, dk.
Si dos grafos son isomorfos entonces tienen la misma sucesión de grados, pero que dos grafos tengan la misma sucesión de grados no quiere decir que sean isomorfos.Por ejemplo los dos siguiente grafos tienen la misma sucesión 4,4,3,2,2,2,1. Pero no son isomorfos porque por ejemplo en el grafo G los nodos de grado 4 no están unidos, mientras que en el grafo G' los nodos de grado 4 si lo están.
Caracterización
La sucesión s, t1, t2, t3,....., ts, d1, d2,......, dk es gráfica Û lo es la sucesión t1-1, t2-1, t3-1,....., ts-1, d1, d2,......, dk
Demostración
Sea G el grafo cuya sucesión es s, t1, t2, … , ts, d1, … ,dk y sean S, T1, T2, …Ts , D1, … , Dk los vértices correspondientes
·Si S es adyacente a T1, T2, …Ts, borramos S y el grafo H=G-{S} es el grafo buscado.
·Si no es así, S no es adyacente a un Ti pero SÍ es adyacente a un vértice Dj con ti ≥ dj
Si ti= dj , basta intercambiar los papeles de Ti y de Dj
Si ti >dj,
Ti tiene más vecinos que Dj. Sea Z vecino de Ti pero no vecino de Dj. Eliminamos las aristas dibujadas con líneas continuas ( SDj, ZTi ) y creamos las discontinuas ( STi, ZDj). Este grafo G1 tiene la misma sucesión grados en el vértice S pero tiene un vecino entre los Ti más que en el grafo G.
Si en G' ya es S adyacente a T1, T2,…Ts, se procede como antes. Y si no lo es se repite el cambio discontinuas-continuas. Como s es finito se alcanza en algún momento un grafo Gm cuya sucesión es la dada.
Algoritmo
Partiendo de una sucesión no creciente de enteros positivos o nulos para decidir si ésta es gráfica o no, lo que hay que hacer es aplicar la caracterización vista en el apartado anterior 2.2.2.2 hasta que suceda alguna de las dos situaciones siguientes:
·Se alcanza una sucesión de 0's Þ la sucesión si es gráfica.
·Se obtiene un número negativo Þ la sucesión no es gráfica.
Sucesiones gráficas (Havel & Hakimi)
Este método desarrollado por Havel y Hakimi será el que implementemos en el proyecto. Es gráfico y está basado en la reconstrucción del grafo, el cual obtenemos tras ir insertando vértices y aristas en sucesivas iteraciones.
Condiciones
Las condiciones para que una sucesión de grados de un grafo sea gráfica son:
·La suma debe ser par
·El valor máximo debe ser menor que la longitud. Por ejemplo la sucesión 6,4,4,2,1,1 no es gráfica pues el valor mayor de la sucesión (6) es igual que la longitud de esta (6).
·Si la sucesión t1-1, t2-1, t3-1,....., ts-1, d1, d2,......, dk es gráfica entonces también lo es la sucesión s, t1, t2, t3,....., ts, d1, d2,......, dk.
Si dos grafos son isomorfos entonces tienen la misma sucesión de grados, pero que dos grafos tengan la misma sucesión de grados no quiere decir que sean isomorfos.Por ejemplo los dos siguiente grafos tienen la misma sucesión 4,4,3,2,2,2,1. Pero no son isomorfos porque por ejemplo en el grafo G los nodos de grado 4 no están unidos, mientras que en el grafo G' los nodos de grado 4 si lo están.
Caracterización
La sucesión s, t1, t2, t3,....., ts, d1, d2,......, dk es gráfica Û lo es la sucesión t1-1, t2-1, t3-1,....., ts-1, d1, d2,......, dk
Demostración
Sea G el grafo cuya sucesión es s, t1, t2, … , ts, d1, … ,dk y sean S, T1, T2, …Ts , D1, … , Dk los vértices correspondientes
·Si S es adyacente a T1, T2, …Ts, borramos S y el grafo H=G-{S} es el grafo buscado.
·Si no es así, S no es adyacente a un Ti pero SÍ es adyacente a un vértice Dj con ti ≥ dj
Si ti= dj , basta intercambiar los papeles de Ti y de Dj
Si ti >dj,
Ti tiene más vecinos que Dj. Sea Z vecino de Ti pero no vecino de Dj. Eliminamos las aristas dibujadas con líneas continuas ( SDj, ZTi ) y creamos las discontinuas ( STi, ZDj). Este grafo G1 tiene la misma sucesión grados en el vértice S pero tiene un vecino entre los Ti más que en el grafo G.
Si en G' ya es S adyacente a T1, T2,…Ts, se procede como antes. Y si no lo es se repite el cambio discontinuas-continuas. Como s es finito se alcanza en algún momento un grafo Gm cuya sucesión es la dada.
Algoritmo
Partiendo de una sucesión no creciente de enteros positivos o nulos para decidir si ésta es gráfica o no, lo que hay que hacer es aplicar la caracterización vista en el apartado anterior 2.2.2.2 hasta que suceda alguna de las dos situaciones siguientes:
·Se alcanza una sucesión de 0's Þ la sucesión si es gráfica.
·Se obtiene un número negativo Þ la sucesión no es gráfica.