Sucesiones y Grafos

SUCESIÓN

Definición 1:

Una sucesión es una función que a cada número natural le hace corresponder un número real bien definido f: N → R / an = f (n)

La expresión an = f(n) recibe el nombre de término general (TG) y es la fórmula que permite calcular cualquier término de la sucesión dada.

Definición 2:

Sucesión es un conjunto infinito de números reales, repetidos o no, que están en correspondencia con los números naturales.

Tipos de sucesiones

Sucesiones explícitas:

Cuando se logra conocer el TG de la misma y se puede obtener cualquier término de la sucesión a partir de la misma.

Sucesión finita:

Si determinamos su último término.

Sucesión constante:

Si todos los términos tienen un mismo valor, es decir, un mismo número real cualquiera.

Sucesiones crecientes:

Son aquellas en las cuales los términos van en aumento.

Sucesiones decrecientes:

Son aquellas en las cuales los términos van decreciendo paulatinamente.

Sucesiones recurrentes (recursivas) o implícitas:

Define cada término más adelante en la sucesión en función de términos anteriores y también en función de uno o más valores iniciales de la sucesión. El TG de la sucesión queda definido de forma implícita si su valor depende de sus predecesores.

Suma de los términos de una sucesión:

Cuando los sumandos de una suma se deducen todos de una misma expresión dándole los valores sucesivos a una indeterminada (o índice) que aparece en ella, la suma se puede expresar en forma más abreviada, anteponiéndole a dicha expresión el símbolo Σ, colocando x debajo y x arriba de éste, el primero y el último valor que toma dicho índice. Dada una sucesión puede ocurrir, a veces, que se desee calcular la suma de algunos de los términos de la sucesión. Llamamos a k el subíndice de la suma, a m el límite inferior de la suma y a n el límite superior de la suma.

Propiedades de la sumatoria

1º) (n=1//k)Σλan=λΣan λ constante

2°) (n=1//k)Σan= (n=1//j)Σan+(n=j+1//k)Σan

3°) Corolarios: (i=1//n)Σan tiene n términos 2°) (i=m//n)Σan tienen n-m+1.

Sucesiones especiales

Sucesión Aritmética

Cuando la sucesión es tal que la diferencia entre dos términos consecutivos cualesquiera da como resultado una constante, se llama Progresión o Sucesión Aritmética. La constante se denomina diferencia y se la simboliza con la letra d. Tanto el término inicial como la constante d son números reales.

Fórmula explícita: an = a1 + d(n − 1)

Fórmula implícita o recursiva: { a(n=1) = a1 an = 1 ; an = an−1 + d n > 1}.

Suma de una sucesión aritmética

Teorema: La suma de n términos de una Sucesión Aritmética es igual a la semisuma del primero y el último término, multiplicada por el número de términos.

Sn=(a1+an)/2*n

Demostración: S=a1+a2+a3+an-1+an se invierte el orden se suma miembro a miembro 2s=(a1+an)+(an+1) pero a1+an=a2+an2… ->2s=(a1+an)n ->S=(a1+an)/2*n

Sucesiones cuadráticas

Es una sucesión de términos cuyas primeras diferencias no son constantes, pero si sus segundas diferencias son constantes, su TG es de la forma an = an ^2 + bn + c

Para encontrar a, b, c:

1°) a + b + c = a1

2°) 3a + b =1a2 − a1 a2 − a1

3°) 2a = a3 − 2a2 + a1

Sucesión Geométrica

Es una sucesión de términos dónde cada uno es igual al anterior multiplicado por un número fijo que llamado razón. El término general es: an = a1 q^(n-1) o a =a0 q^n .

Suma de una sucesión geométrica

Teorema: La suma de los n primeros términos de una sucesión geométrica es igual a

S=a1*(1-q^n)/(1-q)

Demostración: S=a1+a1q+a1q^2+a1q^(n-1) multiplicamos por q: qS=a1q+a1q^2+aq^n restando S-qS=(a1+a1q^(n-1)-(a1+a1q^n) ->S(1-q)=a1-a1q^n->S=a1(1-q^n)/(1-q)

Productoria

Cuando los factores de un producto son números que se deducen de una expresión única, en la cual figura una indeterminada i, dándole a ésta valores sucesivos, se representa el producto más brevemente utilizando el símbolo Π, que representa el producto de los términos de la sucesión en la cual se coloca un subíndice inferior y otro superior que marcan el inicio y el fin de la productoria.

Factorial de n(n!):

Para cada número natural n, la cantidad n factorial que se denota por n!, se define como el producto de todos los enteros de 1 a n. El factorial se simboliza: n!: n!=Π(i=1//n)i=n*(n-1)*2*1

Propiedades:

1) Dados dos números naturales n y r, tales que r ≤ n, se cumple que n! = r! (n – r)!

2) 0! = 1

Enunciado del Principio de Inducción Completa

“Si una propiedad de los números naturales se verifica para el número 1, y si, admitido que se verifique para un número natural cualquiera, se verifica también para el siguiente, entonces dicha propiedad se verifica para todos los números naturales”. En consecuencia el principio implica 4 pasos o etapas.

1) Verificar para n = 1

2) Admitir la validez de la propiedad para un cierto número natural. Esto se llama hipótesis inductiva.

3) Demostrar que la propiedad es verdadera para el siguiente número natural. O sea demostrar la tesis inductiva.

4) Concluir, entonces, que la propiedad es verdadera para todos los números naturales.

El Análisis Combinatorio

Estudia las distintas agrupaciones de elementos, prescindiendo de la naturaleza de los mismos. Se ocupa de las distintas formas en que se pueden agrupar los elementos, de las propiedades de esas agrupaciones y finalmente de las aplicaciones que esta teoría tiene.

Regla del producto:

Se aplica cuando una tarea se compone de diferentes partes, y dice: “Si una actividad puede efectuarse en “r” pasos sucesivos e independientes y si el primer paso puede efectuarse de n1 maneras, el segundo paso puede efectuarse de n2 maneras,…, el paso “r” puede realizarse en nr maneras, entonces la actividad podrá realizarse de n1* n2 * n3 * … * nr maneras

Regla de la suma:

Si “r” actividades pueden realizarse en n1, n2 , n3 , … nr maneras y si estas son disjuntas, es decir, no es posible efectuarlas de manera simultánea, entonces cualquiera de las “r” actividades pueden efectuarse en (n1 + n2 + n3+… + nr) formas

VARIACIONES sin repetición:

Dados n elementos distintos y de cualquier naturaleza, se llaman Variaciones de n elementos tomados de a r (o tomados de r en r) a los grupos de r (r

a) en cada grupo entran r de los n elementos.

b) dos grupos se consideran distintos cuando difieren en por lo menos un elemento o si teniendo los mismos elementos, difieren en el orden

Vn,r=n.(n − 1).(n − 2)…(r factores)

PERMUTACIONES sin repetición:

Dado un conjunto de n elementos distintos y de cualquier naturaleza, se llaman permutaciones de esos n elementos a las posibles formas de ordenar los n elementos dados. Las permutaciones de n elementos son los órdenes que se pueden formar con esos n elementos. En este tipo de agrupación los n elementos entran en cada grupo, por lo tanto, dos grupos sólo pueden diferir en el orden. Pn = n!

PERMUTACION CIRCULAR

Sea un conjunto de n elementos. Una permutación circular es una disposición de esos “n” elementos de forma tal que uno cualquiera de ellos se distinga de otro únicamente por variar la posición relativa de los elementos que la componen. Se designa por Pc= (n-1)!

COMBINACIONES sin repetición:

Dados n elementos distintos y de cualquier naturaleza, se llaman combinaciones de n elementos tomados de r en r ( con r

a) en cada grupo entran r de los n elementos.

b) dos grupos se consideran distintos cuando difieren en por lo menos un elemento.

Vn,r=Cn,r * P r,r ⇒ Cn,r=Vn,r/ P r,r dado que P r,r=r!

Cn,r = n! /(n−r)!r!

Variaciones con repetición:

Se llaman variaciones con repetición, de n elementos tomados de a r, a las selecciones de r elementos, no necesariamente distintos que se distinguen entre sí en algún elemento o en su orden. Dos variaciones son distintas si difieren en un elemento o si teniendo los mismos elementos, difieren en el orden. Solo que ahora se pueden repetir los elementos. V’n,r=n^r

Combinaciones con repetición:

Dados n elementos de cualquier naturaleza, y un número r εN, tal que r puede ser menor, igual o mayor que n, se llaman Combinaciones con repetición, a las selecciones de r elementos (no necesariamente distintos) elegidos entre los n dados, de manera que dos grupos son diferentes si difieren en algún elemento. C’n,r=C n+r-1,r

Permutaciones con repetición:

El número de permutaciones diferentes de n objetos, donde hay n1 objetos indistinguibles de tipo 1, n2 objetos indistinguibles de tipo 2, …, y nk objetos indistinguibles de tipo k es

Pn ^n1,n2,….,nk = n! /n1!n2!….nk! nótese que n1 + n2 + ⋯ + nk = n

Números Combinatorios:

Cn,r = n! /(n−r)!r!=(n r)

Propiedades:

1) C n,r= C n, n-r son números complementarios

2) fórmula de stieffel o pascal: (n-1 r-1)+(n-1 r)=(n r)

Corolarios:

1_ (n n)=1

2_ (n 1)=n

3_ (n 0)=1

El triángulo de Tartaglia

Se construye de la siguiente forma. En la primera fila se colocan dos unos. En las filas restantes, los extremos son unos y los números interiores son iguales a la suma de los dos números más próximos de la fila anterior.

BINOMIO DE NEWTON

Una de las aplicaciones más conocida de los números combinatorios es el cálculo de la potencia enésima de un binomio, también llamado Fórmula del Binomio de Newton, que dice:

(a+b)^n=(k=0//n)∑(n k)a^(n-k)*b^k

Propiedades:

En el desarrollo de: (a+b)^n se observa:

1º) El desarrollo de la potencia enésima de un binomio, es un polinomio que tiene n + 1 términos.

2º) Los números combinatorios correspondientes a los términos que equidistan de los extremos son números combinatorios complementarios.

3º) Si n es par, el desarrollo tiene un número impar de términos y por lo tanto hay un único término central.

4º) Si n es impar, el desarrollo tiene un número par de términos y por lo tanto hay 2 términos centrales.

5º) Un término cualquiera puede calcularse mediante la fórmula: Tk+1=(n k) a^(n-k)*b^k dónde k + 1 indica el lugar que ocupa el término en el desarrollo de ( a+b)^n

GRAFOS

Se llama Grafo a la terna G = (V, A, φ ), dónde V es un conjunto finito no vacío de vértices (o nodos), A es un conjunto finito de aristas, dónde cada arista está asociada a un conjunto compuesto por dos vértices extremos. La función φ de incidencia le hace corresponder a cada arista sus vértices extremos de V. ¥x€A :φ( x ) = { vi , vj }

Definiciones:

Sea G = (V, A, φ) un grafo.

Definición 1: Un vértice y una arista son incidentes sii el vértice es extremo de la arista.

Definición 2: Dos aristas son paralelas (o múltiples) sii los vértices asociados a cada una de ellas coinciden.

Definición 3: Una arista es un lazo (o bucle) sii, sus extremos coinciden.

Definición 4: El grado o valencia de un vértice es el número de aristas que inciden en él.

Definición 5: Un vértice v se dice aislado si g (v) = 0 . Es decir no incide ninguna arista en él.

Definición 6: Un vértice v es un vértice pendiente si g ( v ) = 1.

Definición 7: Dos vértices son adyacentes si son extremos de una misma arista.

Definición 8: Dos aristas son adyacentes si tienen un vértice en común.

Definición 9: Si todos los vértices de un grafo tienen el mismo grado, el grafo se dice regular. Si todos los vértices tienen grado k el grafo es k-regular.

Definición 10: Un grafo se llama simple (o sencillo) si no tiene lazos ni aristas paralelas.

Definición 11: Matriz de incidencia de grafos Sea (V, A, φ ) un grafo de n vértices y k aristas. Entonces | V | = n el número de elementos de V es n y | A | = k el número de elementos de A es k. Se llama matriz de incidencia de un grafo (V, A, φ) (que no tenga lazos) a una matriz Mi = || mij || de n filas y k columnas, tal que. mij = { 1 si vi es extremo de aj, 0 en otro caso . Cada columna de una matriz de incidencia tiene dos unos. La suma de los elementos de cada fila da el grado del vértice correspondiente. Cuando estamos en presencia de lazos en las columnas tendríamos un solo 1.

Definición 12: Matriz de adyacencia de vértices de un grafo Es una buena representación para grafos sin aristas paralelas. Sea G = (V, A, φ) un grafo de n vértices. Se llama matriz de adyacencia de vértices de un grafo a una matriz Mv = || mij || de orden n x n tal que mij ={1 si vi y vj son adyacentes, 0 en todo otro caso . Esta matriz también se puede utilizar aún en presencia de aristas paralelas o múltiples haciendo la siguiente salvedad. Se coloca el número de aristas paralelas entre los vértices involucrados.

Teorema del saludo de manos:

Sea G = (V, A, φ ) un grafo , la suma de los grados de todos los vértices del grafo es igual al doble del número de aristas. V = {vi } | V | = n |A| = k->(i=1//n)Σg(vi)=2*|A|

Corolario: El grado total de un grafo es par.

Teorema: En todo grafo hay un número par de vértice de grado impar.

Demostración: Sea V el conjunto de vértices de un grafo. Sea Vp el conjunto de los vértices de grado par. Vp = { vp } Sea Vi el conjunto de los vértices de grado impar Vi = { vi } V = Vp u Vi –> (j=1//n)Σ g(vj)=2|A| La suma de los grados de todos los vértices es igual a la suma de los grados de los vértices de grado par más la suma de los grados de los vértices de grado impar. Σg(vp) es un número par porque es la suma de números pares 2 | A | es un número par porque es múltiplo de 2. En consecuencia Σg(vi) debe ser par. Pero g(vi) es una suma cuyos términos son todos impares. Si el resultado de esta suma es par, entonces el número de términos de esa sumatoria debe ser par. Por lo tanto, el número de vértices de grado impar es par, que es lo que queríamos demostrar.

SUBGRAFOS:

Una terna S = ( V´, A´, φ´ ) es un subgrafo del grafo G = ( V, A, φ ) si se cumple:

I ) V´c V

II) A´c A

III ) φ´ es una restricción de φ en A´ .

Subgrafo restante respecto de un vértice:

Se llama subgrafo restante respecto del vértice vi al grafo obtenido a partir del grafo original omitiendo el vértice vi y todas la aristas que inciden en él. Se simboliza Gvi.

Subgrafo restante respecto de una arista:

Se llama subgrafo restante respecto de una arista ai al grafo que se obtiene suprimiendo la arista a del grafo original y que se simboliza: G~a

Subgrafo generado por un subconjunto de vértices W:

Sea W un subconjunto de vértices de V. Se llama subgrafo generado por un subconjunto de vértices W al grafo que tiene a W como subconjunto de vértices y cuyo conjunto de aristas está formado por todas las aristas del grafos original que tienen ambos extremos en W.

Conexión de Grafos

Camino:

Sea G un grafo G = ( V , A , φ) y sean vi y vj dos vértices de G. Un camino de vi a vj es una sucesión finita alternada de vértices adyacentes y aristas de G. Un camino trivial de v1 a v1 consiste del único vértice v1. Un camino puede iniciar y terminar en el mismo vértice, puede repetir aristas y vértices.

Cadena:

Dado un grafo G = ( V , A , φ ) se llama cadena a una sucesión alternada de vértices adyacentes y aristas de la forma v1 a1 v2 a2 v3 a3 … an vn que comienza y termina en vértices y que cumple las siguientes condiciones:

i) Las aristas son todas distintas.

ii) Cada arista incide en el vértice precedente y en el siguiente.

Cadena simple:

Una cadena simple: es una cadena en la cual todos los vértices son distintos.

Ciclo:

Un ciclo es una cadena cuyo vértice inicial coincide con el final.

Ciclo simple:

Un ciclo simple es un ciclo en el que no se repite ningún vértice, salvo el primero (y el último)

Longitud de un camino:

Se llama longitud de un camino ( o cadena o ciclo) al número de aristas que la componen.

Número de caminos entre dos vértices:

Se puede determinar usando su matriz de adyacencia de vértices.

Teorema: Sea G un grafo y sea MG su matriz de adyacencia con respecto a la ordenación v1,v2,v3,…,vn (se admiten aristas múltiples o lazos). El número de caminos distintos de longitud r de vi a vj, siendo r un entero positivo, es igual al elemento en la posición (i,j) de la matriz MG^r .

Conectividad:

Un grafo está conectado si es posible viajar desde cualquier vértice a cualquier otro vértice a lo largo de una sucesión de aristas adyacentes del grafo.

Grafo Conexo:

Sea G un grafo. Dos vértices vi y vj de G son conexos sii existe un camino de vi a vj. El grafo G es conexo sii, dados dos vértices cualesquiera vi y vj de G hay un camino de vi a vj.

Lema: Sea G un grafo

a) Si G es conexo, entonces dos vértices distintos cualesquiera de G pueden conectarse con una cadena simple.

b) Si los vértices v y w forman parte de un ciclo en G y se quita una arista del ciclo, entonces aún existe una cadena de v a w en G.

c) Si G es conexo y contiene un ciclo, entonces se puede eliminar una arista del ciclo sin desconectar a G.

Grafo no conexo

Teorema: Un grafo G = ( V, A , φ) que no es conexo , es la unión de dos o más subgrafos conexos que dos a dos, no tienen ningún vértice en común. A estos subgrafos conexos disjuntos se les llama componentes conexas del grafo.

Desconexión de Grafos

Punto de corte:

Un vértice v de un grafo conexo G es un istmo o punto de corte sii el subgrafo restante respecto de v es no conexo.

Puente:

Una arista a de un grafo conexo G es un puente si el subgrafo restante respecto de esa arista es no conexo.

Ciclo de Euler:

Un ciclo en un grafo G = ( V , A , φ ) es un ciclo de Euler si recorre todas las aristas del grafo en estudio.

Teorema: Un grafo conexo G admite un ciclo de Euler sii todos sus vértices tienen grado par.

Teorema Un grafo conexo G contiene una cadena de Euler sii tiene exactamente dos vértices de grado impar, siendo todos los demás vértices de grado par.

Ciclo de Hamilton:

Sea un grafo conexo G = (V, A, φ) tiene un ciclo de Hamilton si existe un ciclo simple de G que contenga todos los vértices de V. Una cadena de Hamilton es una cadena simple de G que contiene todos los vértices.

Sugerencias para intentar hallar un ciclo de Hamilton según Grimaldi. En un grafo G = (V, A, φ) :

1) Si G tiene un ciclo de Hamilton, entonces para v € V, grad (v) ≥2.

2) Si v €V y grad (v) = 2, entonces las dos aristas incidentes en el vértice v deben aparecer en cualquier ciclo de Hamilton de G.

3) Si v €V y grad (v) > 2, entonces cuando se intenta construir un ciclo de Hamilton, una vez que se pase por v, las aristas no utilizadas incidentes en v se dejan de tener en cuenta.

GRAFOS ISOMORFOS

Dados dos grafos G = (V, A, φ) y G = (V,A,φ) se dice que G y G son isomorfos si existe una función biyectiva f : V → V y una función biyectiva g : A → A que conserven las relaciones de incidencia y adyacencia.

Invariante del isomorfismo:

Una propiedad P se llama invariante del isomorfismo del grafo, sii, dados dos grafos cualesquiera G y G , si G tiene la propiedad P y G es isomorfo a G, entonces G tiene la propiedad P.

Teorema: Cada una de las siguientes propiedades es un invariante del isomorfismo del grafo, dónde, n, m y k son todos enteros no negativos.

1) Tiene n vértices

2) Tiene m aristas

3) Tiene un(m) vértice de grado k

4) Tiene un ciclo de longitud k

6) Tiene un(m) ciclo simple de longitud k

8) Es conexo

9) Tiene un ciclo de euler

10) Tiene un ciclo de Hamilton.

Tipos especiales de grafos

Grafos k-regulares

El grafo regular de grado k o grafo k-regular es aquél en el que todos los vértices tienen grado k. Los grafos k regulares pueden ser simples o no.

Grafo Completo de p vértices:

El grafo completo de p vértices que se simboliza Kp es un grafo simple cuyo conjunto de vértices tiene p elementos y tal que todo par de vértices distintos determina una arista. O lo que es lo mismo: un grafo simple es completo si todo vértice está conectado con todo otro vértice.

Propiedades del Grafo Completo KP

1) Todo vértice tiene grado p – 1.

2) El subgrafo restante de Kp respeto de cualquiera de sus vértices es isomorfo con Kp – 1.

3) Dados 3 vértices distintos de Kp ( p ≥3 ) existe un ciclo de longitud 3 que los contiene sólo a ellos.

4) Para p ≥3 , Kp es un bloque es decir que carece de itsmos y puentes

5) Si A es el conjunto de aristas de Kp entonces |A|=C p,2.

6)Un grafo completo Kp siempre tendrá un ciclo hamiltoniano, cuando p ≥ 3,

Grafo Complementario:

Dado un grafo simple G = ( V , A , φ ) se llama grafo complementario de G al grafo G = (V, A’ ,φ’) que tiene el mismo conjunto de vértices que G y cuyas aristas son justamente las que le faltan a G para ser completo.

Grafos bipartitos:

Un grafo simple G se dice bipartito si su conjunto de vértices se puede particionar en dos subconjuntos V1 y V2 tales que toda arista del grafo conecta un vértice de V1 con un vértice de V2. Recordemos que V1 y V2 forman una partición de V sii V1 u V2 =V y V1 n V2 =0.

Grafo Bipartito Completo:

Un grafo simple es bipartito completo cuando es bipartito y además cada vértice de V1 está conectado con cada vértice de V2 Un grafo bipartito completo se denota Kp,q (o también Kn1;n2) donde el primer subíndice es el número de elementos de V1 y el segundo subíndice es el número de elementos de V2. En general se acepta que siempre sea p≤ q .

GRAFO PLANAR (GRAFO PLANO):

Un grafo es plano si puede dibujarse en el plano de manera que ningún par de sus aristas se corte (por corte de aristas se entiende la intersección de las líneas que representan a las aristas) en un punto distinto de sus vértices.

Mapa

Se llama mapa a una representación plana particular de un grafo plano finito. El mapa es conexo si el correspondiente grafo es conexo. Un mapa dado divide el plano en varias regiones y también se presenta una región sin frontera, es decir no acotada. Así no hay pérdida de generalidad al contar las regiones si suponemos que nuestro mapa está contenido en algún rectángulo mayor en lugar de en el plano completo.

Frontera de una región:

Sea un grafo plano G, al conjunto de vértices y aristas que inciden en una región r de G se le llama la frontera de r.

Teorema de Euler para grafo plano conexo

Si G es un grafo plano conexo con | V |= nº de vértices, | A |= nº de aristas y que descompone al plano en r regiones entonces se cumple que | V | – |A| + r = 2

Para Grafo plano no Conexo

Si G es un grafo plano no conexo se cumple | V | – | A | + r = ν + 1 donde ν es el número de componentes conexas.

Teorema de Kuratowski:

Un grafo es plano sii, no contiene ningún subgrafo isomorfo a K5 ni a K3,3 ni a subdivisiones de ellos.

Grafos coloreados

El coloreado de un grafo G=(V,A,φ) es una asignación de colores a los vértices de G de tal forma que vértices adyacentes tengan colores distintos. Se dice que G es n-coloreable si existe un coloreado de G que usa n colores.

Número cromático: es el número mínimo de colores necesario para colorear G. Y se utiliza la letra griega chi para representar χ(G),

Si coloreamos un grafo completo χ(Kp)=p, necesitamos dos colores para colorear un grafo bipartito.

Grafos planares y coloreado

Teorema: Cualquier grafo planar G es 5-coloreable.

Teorema de los cuatro colores:

Si las regiones de un mapa M se colorean de forma que las regiones adyacentes tengan colores distintos, entonces no se necesitan más de cuatro colores.

Grafos rotulados o ponderados

Un grafo G se llama un grafo rotulado o ponderado si sus aristas y/o vértices se le asignan datos de alguna clase. En particular, si a cada arista a de G se le asigna un número no negativo entonces a l(s) se le llama el peso o longitud l(s) de a.

Algoritmo del Camino más corto o de Dijkstra:

DÍGRAFOS

Se llama dígrafo o grafo dirigido a una terna D = (V, A,δ) dónde V es un conjunto de vértices, A es un conjunto de arcos y δ es una función que a cada elemento de A le hace corresponder un elemento de V x V. ¥ x €A: δ (x) = (vi, vj )

Arcos estrictamente paralelos:

Dos arcos de un dígrafo son estrictamente paralelos si tienen el mismo vértice inicial y el mismo vértice final.

Rizo:

Un arco es un rizo, si tiene inicio y final en el mismo vértice.

Dígrafo sencillo:

Si no tiene rizos ni arcos estrictamente paralelos.

Grado negativo de un vértice:

Se simboliza g – (v) y es número de arcos que llegan a ese vértice.

Grado positivo de un vértice:

Se simboliza con g + (v) y es número de arcos que parten de ese vértice

Grado total de un vértice:

Es la suma de su grado negativo y su grado positivo. gt(vi) = g – (vi) + g+ (vi)

Grado neto de un vértice:

Se llama grado neto de un vértice al número entero que resulta de restar el grado positivo y el grado negativo de ese vértice. gn(vi) = g+ (vi) – g – (vi)

Propiedades:

Σg^–(v)=Σg+(v)=|A|; Σgt(v)=2|A|; Σgn(v)=0

Dígrafos Isomorfos

Sean D = (V, A, δ ) y D´ = (V´, A´, δ´) dos dígrafos D y D´ son dígrafos isomorfos si sus respectivas estructuras de grafo subyacentes son isomorfas y además subsiste la orientación de los arcos homólogos.

Tipos de conexidad.:

Dígrafos débilmnt conexos: Un dígrafo es débilmnt conexo si p/todo par d vértices d V, existe una cadena q los une. En otras palabras, un dígrafo es débilmnt conexo si el grafo subyacent es conexo. Dígrafos Unilateralmnt conexos: Un dígrafo sin arcos estrictamente paralelos s dice q es unilateralmente conexo si p/todo par d vértices vi y vj dl dígrafo existe al menos un cadena q parte d vi a vj o d vj a vi . En otras palabras, si para todo par d vértices existe al menos un cadena q parte d una d ellos y llega al otro. Dígrafos Fuertemnt conexos: Un dígrafo es fuertemnt conexo si p/todo par d vértices vi , vj d V existe una cadena d vi a vj y una cadena d vj a vi

Rep Matricial d Dígrafos 1) Matriz d Incidencia d Dígrafos; Es una buena rep si el dígrafo no tiene rizos Def: Sea D = (V, A,δ ) un dígrafo dónde |V|= n y |A| = k . Se llama matriz d incidencia a una matriz M_i^n*k =||mij|| d orden nxk/ mij{ 1 si aj sale de vi, -1 si aj llega a vi, 0 en otro caso} La + d los elementos d una fila es = al grado neto dl vértice respectivo. Se puede utilizar si posee rizos, se coloca en la posición dl vértice inicial y final ± para indicar la presencia dl rizo.

2) Matriz d Adyacencia d vértices en un Dígrafo Es una buena rep si el dígrafo no tiene arcos estrictamente paralelos. Sea D = (V, A,δ ) un dígrafo d n vértices. Se llama matriz d adyacencia d vértices a una matriz cuadrada d orden n / Mv = ||mij ||d orden n x n tal que mij = {0 en todo otro caso 1 si hay un arco de vi a vj} Se puede utilizar en presencia de arcos estrictamente paralelos o múltiples colocando en los vértices involucrados el número correspondiente de aristas que haya

Sumidero : es un vértice al que sólo llegan arcos. El g+ (v) = 0

Fuente: es un vértice del que sólo parten arcos. No hay ningún arco que llegue a él. El g- (v) = 0

Árboles Definición: Se llama árbol a un grafo conexo y acíclico. Al ser acíclico no admite lazos, ni aristas paralelas. Def equiv: Todo par de vértices de G está conectado por una única cadena, G es acíclico pero si se le agrega una arista aparece un ciclo único; G es conexo si bien todas sus aristas son puentes.

Árbol con Raíz: Un árbol con raíz consta de un grafo árbol con un vértice designado como raíz del árbol. Todo árbol puede constituirse en un árbol con raíz simplemente escogiendo uno de los vértices como raíz.

Nivel de un vértice Definición: Se llama Nivel de un vértice v de un árbol con raíz r a la longitud de la única cadena que va de r a v

Altura de un árbol Definición: Se llama altura de un árbol al máximo nivel del árbol

Hojas o vértices terminales Definición: Se llaman Hojas de un árbol a sus vértices pendiente

Vértices internos Definición: Se llaman vértices internos a todos los vértices que no son terminales. La raíz es vértice interno.

Arboles genealógicos: Antepasados o antecesores: El vertice vi es antepasado de vj si la unica cadena que une a vi con la raiz incluye a vi.

Hijos: Un vertice vi es hijo de vj o vj es padre de vi si: 1) vi sigue a vj 2) vi es adyacente a vj. Todo vértice (excepto la raíz) es hijo de un solo vértice, pero puede ser padre de varios.

Hermanos: si vi y vj tienen el mismo padre

Descendientes de un vértice Definición: Los descendientes del vértice v, son todos los vértices que se encuentran por debajo de ese vértice en el árbol

Subárbol De la propia estructura de árbol surge que todo vértice es raíz de un subárbol contenido en el árbol original. Si en el árbol original borramos la raíz y las aristas que la unen con los vértices de nivel uno obtenemos árboles disjunto es decir un bosque. Estos bosques tienen la propiedad de que cada una de sus componentes conexas es un árbol.

Se llama Árbol con raíz ordenado a un árbol con raíz en el cuál se prescribe un orden para los vértices de cada nivel. Tales árboles se dibujan con la raíz R en la parte superior y las aristas dirigidas hacia abajo y los hijos ordenados de izquierda a derecha

Sistema universal de direcciones: el orden se denomina orden lexicográfico u orden de diccionario.

Árbol m–ario Siendo m un entero positivo, se dice que un árbol con raíz es un árbol m – ario si cada vértice interno tiene a los sumo m hijos

Árbol m -ario completo Si todos los vértices internos de un árbol con raíz tienen exactamente m hijos, se llama árbol m –ario completo.

Propiedades: Teorema 1: Un árbol de n vértices tiene n-1 aristas. Teorema 2: Los árboles son 2-coloreables. Teorema 3: Un árbol m-ario completo con i vértices internos tiene n(vertices)= mi+1 vértices y l(hojas)=(m-1)i+1. T4: Un arbol m-ario completo de altura h tiene a lo sumo m^h hijos.

Árbol m –ario posicional Son árboles m –arios en los cuales los hijos de cada vértice ocupan posiciones distintas.

Árbol binario posicional: Es un árbol con raíz en el cuál cada vértice interno tiene un hijo a la derecha y/o un hijo a la izquierda o bien, ningún hijo.

Árboles Etiquetados Casi siempre conviene etiquetar los vértices o las aristas de un grafo para indicar que se usarán para un propósito particular.

Árboles Binarios Posicionales que representan Expresiones Algebraicas: Las operaciones fundamentales: suma, resta, multiplicación y división son operaciones binarias y se pueden representar por árboles binarios etiquetados.En este árbol, la raíz se etiqueta con el operador central de la expresión dada. Los dos hijos de la raíz se etiquetan con los operadores de los argumentos izquierdo y derecho respectivamente. Si algún argumento está constituido por una constante o una variable, el hijo correspondiente se etiqueta con esa constante o variable.

Análisis o recorrido de un árbol es el proceso de visitar cada vértice del mismo exactamente una vez en algún orden específico. Se estudian 3 formas de recorrerlo: Orden inicial( preorden, prefija o notacion polaca)(RID), orden intermedio(IRD) y orden final(IDR)

=n>