Sucesiones, Grafos y Árboles: Un Recorrido por las Estructuras Discretas

Sucesiones

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 1 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 por debajo y por 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: a_n = a₁ + d(n − 1)
• Fórmula implícita o recursiva: { a_(n=1) = a₁ n = 1 ; a_n = a_n-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.

S_n=(a₁+a_n)/2*n

Demostración:

S=a₁+a₂+a₃+a_n-1+a_n se invierte el orden se suma miembro a miembro

2s=(a₁+a_n)+(a_n+a₁) pero a₁+a_n=a₂+a_n-1… ->2s=(a₁+a_n)n ->S=(a₁+a_n)/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 a_n = an^2 + bn + c

Para encontrar a, b, c:

1. a + b + c = a₁
2. 3a + b =1^ra diferencia entre a₁ y a₂
3. 2a = 2^da diferencia

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 llamamos razón.

• El término general es: a_n = a₁ q^(n-1) o a =a₀ 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=a₁*(1-q^n)/(1-q)

Demostración:

S=a₁+a₁q+a₁q^2+a₁q^(n-1) multiplicando por q:

qS=a₁q+a₁q^2+aq^n restando

S-qS=(a₁+a₁q^(n-1)-(a₁+a₁q^n) ->S(1-q)=a₁-a₁q^n->S=a₁(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

Principio de Inducción Completa

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.

Análisis Combinatorio

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.

V_n,r=n.(n − 1).(n − 2)…(r factores)=n!/(n-r)!

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.

P_n = n!

Permutación 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

P_c= (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 r elementos elegidos entre los n dados, prescindiendo del orden en que se los elija, de modo que:

• a) En cada grupo entran r de los n elementos.
• b) Dos grupos se consideran distintos cuando difieren en por lo menos un elemento.

V_n,r=C_n,r * P_r,r ⇒ C_n,r=V_n,r/ P_r,r dado que P_r,r=r! –> C_n,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 n₁ objetos indistinguibles de tipo 1, n₂ objetos indistinguibles de tipo 2, …, y n_k objetos indistinguibles de tipo k es

P_n ^{n₁,n₂,….,n_k} = n! /n₁!n₂!….n_k! donde n₁ + n₂ + ⋯ + n_k = n

Números Combinatorios

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

Propiedades

1. C n,r= C n, n-r son números complementarios
2. Fórmula de Stiefel o Pascal: (n-1 r-1)+(n-1 r)=(n r)

Corolarios

1. (n n)=1
2. (n 1)=n
3. (n 0)=1

Triángulo de Tartaglia

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 dos términos centrales.
5. Un término cualquiera puede calcularse mediante la fórmula: T_k+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.

1. Vértice y arista incidentes: Un vértice y una arista son incidentes si y solo si el vértice es extremo de la arista.
2. Aristas paralelas (o múltiples): Dos aristas son paralelas (o múltiples) si y solo si los vértices asociados a cada una de ellas coinciden.
3. Lazo (o bucle): Una arista es un lazo (o bucle) si y solo si, sus extremos coinciden.
4. Grado o valencia de un vértice: El grado o valencia de un vértice es el número de aristas que inciden en él.
5. Vértice aislado: Un vértice v se dice aislado si g (v) = 0 . Es decir no incide ninguna arista en él.
6. Vértice pendiente: Un vértice v es un vértice pendiente si g ( v ) = 1.
7. Vértices adyacentes: Dos vértices son adyacentes si son extremos de una misma arista.
8. Aristas adyacentes: Dos aristas son adyacentes si tienen un vértice en común.
9. Grafo regular: 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.
10. Grafo simple (o sencillo): Un grafo se llama simple (o sencillo) si no tiene lazos ni aristas paralelas.
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 caso contrario . 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 uno.
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 v y v 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 (o de los apretones de mano)

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 dos. 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

Definición: 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

Definición: 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 g_vi.

Subgrafo restante respecto de una arista

Definición: 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: a G~a

Subgrafo generado por un subconjunto de vértices W

Definición: 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

Definición: 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 (sendero o recorrido)

Definición: Dado un grafo G = ( V , A , φ ) se llama cadena (sendero o recorrido) 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

Definición: Una cadena simple (o trayectoria) es una cadena en la cual todos los vértices son distintos.

Ciclo

Definición: Un ciclo es una cadena cuyo vértice inicial coincide con el final.

Ciclo simple

Definición: 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

Definición: 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

El número de caminos que hay entre dos vértices de un grafo se puede determinar usando su matriz de adyacencia de vértices.

Teorema: Sea G un grafo y sea M_G 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 M_G^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

Definición: Sea G un grafo. Dos vértices vi y vj de G son conexos si y sólo si existe un camino de vi a vj. El grafo G es conexo si y solo si, 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

Definición: Un vértice v de un grafo conexo G es un istmo o punto de corte si y solamente si el subgrafo restante respecto de v es no conexo.

Puente

Definición: 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

Definición: 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 si y solamente si todos sus vértices tienen grado par.

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

Ciclo de Hamilton

Definición: 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

Definición: Una propiedad P se llama invariante del isomorfismo del grafo, si y sólo si, 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
5. Tiene un(m) ciclo simple de longitud k
6. Es conexo
7. Tiene un ciclo de euler
8. 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

Definición: El grafo completo de p vértices que simbolizaremos K_p 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 K_P

1. Todo vértice tiene grado p – 1.
2. El subgrafo restante de K_p respeto de cualquiera de sus vértices es isomorfo con K_{p – 1}.
3. Dados 3 vértices distintos de K_p ( p ≥3 ) existe un ciclo de longitud 3 que los contiene sólo a ellos.
4. Para p ≥3 , K_p es un bloque es decir que carece de itsmos y puentes
5. Si A es el conjunto de aristas de K_p entonces |A|=C p,2.
6. Un grafo completo K_p siempre tendrá un ciclo hamiltoniano, cuando p ≥ 3,

Grafo Complementario

Definición: 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

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

Grafo Bipartito Completo

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

Grafo Planar (Grafo Plano)

Definición de 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 si, y solo si, no contiene ningún subgrafo isomorfo a K₅ ni a K_3,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

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

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

Grafos planares y coloreado

Teorema: Cualquier grafo planar G es cinco-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

n-esima iteracion| vert resuelt conectado directamente a vert no resuelt| vert no resuelt + cercano conectado| dist tot involucrada| n-esimo vert + cercano| dist min| ult conex.

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

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

Rizo

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

Dígrafo sencillo

Definición: Un dígrafo se dice sencillo si no tiene rizos ni arcos estrictamente paralelos.

Grado negativo de un vértice Definición: Se llama grado negativo de un vértice y se simboliza g – (v) al número de arcos que llegan a ese vértice.

Grado positivo de un vértice Definición: Se llama grado positivo de un vértice y se simboliza con g + (v) al número de arcos que parten de ese vértice

Grado total de un vértice Definición: Se llama grado total de un vértice (o grado sin signo) a la suma de su grado negativo y su grado positivo. gt(vi) = g – (vi) + g+ (vi)

Grado neto de un vértice Definición: 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ébilmente conexos Definición: Un dígrafo es débilmente conexo si para todo par de vértices de V, existe una cadena que los une. En otras palabras, un dígrafo es débilmente conexo si el grafo subyacente es conexo.

Dígrafos Unilateralmente conexos Definición: Un dígrafo sin arcos estrictamente paralelos se dice que es unilateralmente conexo si para todo par de vértices vi y vj del dígrafo existe “al menos” un cadena que parte de vi a vj o de vj a vi . En otras palabras, si para todo par de vértices existe al menos un cadena que parte de una de ellos y llega al otro.

Dígrafos Fuertemente conexos Definición: Un dígrafo es fuertemente conexo si para todo par de vértices vi , vj de V existe una cadena de vi a vj y una cadena de vj a vi

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

2) Matriz de Adyacencia de vértices en un Dígrafo Es una buena representación si el dígrafo no tiene arcos estrictamente paralelos. Sea D = (V, A, ) un dígrafo de n vértices. Se llama matriz de adyacencia de vértices a una matriz cuadrada de orden n / Mv = ||mij ||de 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>