Mapas y Coloraciones.

Definición:

Un grafo o multigrafo es plano si se puede representar en el plano de modo que cada arista corta únicamente a otra arista en un vértice de ambas.

Una representación de un grafo o multigrafo plano es un mapa. El mapa es conexo si el grafo es conexo. El mapa divide al plano en regiones, y su número es #R

El grado de una región es la longitud del camino que la bordea.

Propiedad:

La suma de los grados de las regiones de un mapa es igual al doble del número de aristas del grafo.

Dado un mapa conexo con #R regiones, se cumple que #V-#E+#R=2

Si un grafo plano conexo tiene #V<2, entonces; #Eð3#V-6

Si un grafo plano conexo tiene #V<2, si no existe en el ningún subgrafo isomorfo a K3 (Grafo completo 3), entonces #Eð2#V-4

Definición:

Sea G un grafo, y u,v dos de sus vértices que forman arista. Entonces, una subdivisión elemental del grafo G es el grafo G' que es el grafo G al que se le añade un vértice w, se le quita la arista uv, y se le añaden dos aristas, una la uw, y otra la wv. Es como sustituir una de sus aristas por un vértice unido a los vértices que antes eran extremos de esa arista.

Una subdivisión de G es el grafo después de hacer un número finito (incluso 0) de subdivisiones elementales sucesivas.

Propiedad (Kuratowski)

Un grafo es plano sí y sólo si no contiene ningún subgrafo que sea isomorfo a una subdivisión de K5, o K3,3 (Grafo en el que cada vértice conecta con otros 3)

Definición:

Si M es un mapa y G su grafo, dos regiones de M son adyacentes si los caminos que las bordean poseen al menos una arista en común.

El pseudomultigrafo dual GM es el pseudomultigrafo construido tomando como conjunto de vértices las regiones de M y a cada arista del Grafo G se le asocia una arista de manera que si separa dos regiones adyacentes, se conecta con los vértices correspondientes a esas regiones.

Es un pseudomultigrafo plano.

Dado un grafo G y un conjunto de colores, k colores, una coloración con k colores del grafo es asociar a cada vértice un color de manera que si dos vértices forma arista, entonces sean de distinto color.

Propiedad:

Todo grafo plano admite cuatro colores.

Métodos combinatorios

Propiedades:

Dados n conjuntos finitos disjuntos dos a dos, el cardinal de la unión de todos es igual a la suma de sus cardinales.

Si los conjuntos son no vacíos, sean o no disjuntos dos a dos, el cardinal de su producto cartesiano es igual al producto de sus cardinales.

Propiedad (principio de la distribución)

Sean m, n y p números naturales. Si se distribuyen np+m objetos en n cajas, alguna caja debe contener por los menos p+1 objetos.

Si dados n enteros positivos, mi, de tal forma que su suma dividida entre n es mayor que p, entonces, alguno de los mi es mayor que p.

También podemos expresar esta desigualdad multiplicando p por n y considerando entonces que existe un número mayor que cero que sumado a p por n nos da la suma de los mi.

Permutaciones

Una permutación de A, siendo A un conjunto, no es más que una biyección de A en A.

Dadas permutaciones, la permutación producto no es más que la composición de la primera permutación con la segunda.

Propiedades: El conjunto de todas las permutaciones de un conjunto A con la operación producto tiene estructura de grupo (como la suma con los enteros) y es un grupo simétrico denominado SA.

Dados dos conjuntos A y B con n elementos, el número de biyecciones distintas de A a V es n! (Por tanto, como A tiene el mismo número n de elementos que A, el número de permutaciones es n!)

Variaciones.

Dado A conjunto finito de n elementos, n mayor que cero, y r menor o igual que n, una variacion de orden r es una lista ordenada de r elementos de A, todos distintos. V(n,r).

Propiedades: Una permutación es una variación V(n,n)

Dados dos conjuntos, A con cardinal r, y B con cardinal n, r menor o igual que n, el número de aplicaciones inyectivas de A a B es igual a n!/(n-r)! (O equivalentemente, multiplicar todos los números desde n hacia atrás, hasta llegar a n-r+1). Por tanto, ese también el número de variaciones de orden r de un conjunto A de n elementos.

Variaciones con repetición.

Dado A con n elementos y r un número natural, una variación con repetición es una lista ordenada de r elementos de A, donde los elementos pueden ser iguales. (VR(n,r))

Propiedad: Dados A y B no vacíos, con cardinales r y n, el número de aplicaciones de A a B es nr. Ese es también el número de variaciones con repetición de orden r de un conjunto con n elementos. nr

Combinaciones.

Dado A conjunto finito con n elementos, n mayor que cero, y r menor o igual que n, una combinación de orden r de A es una lista de r elementos de A distintos. El orden no importa. Son distintas si algún elemento no se encuentra en la otra.

C(n,r) o el paréntesis con n arriba y r debajo, llamado número combinatorio.

Propiedad: C(n,r)=n!/(r!*(n-r)!).

Combinaciones con repetición.

Dado A conjunto infinito con n elementos, mayor que cero, y r un número natural, una combinación con repetición es una lista de r elementos de A, donde los elementos pueden ser iguales. Dos combinaciones con repetición son diferentes si algún elemento de una no se encuentra en la otra. CR(n,r)

Propiedades: Encontrar el número de combinaciones con repetición de orden r de un conjunto A con n elementos es como encontrar el número de soluciones enteras no negativas de la ecuación x1+x2+……xn=r.

Además, estas combinaciones pueden responder al problema de, dado un conjunto A que contiene unas categorías de elementos (n categorías), y sabiendo de que de cada categoría se pueden escoger todas las unidades que queramos, si nos dejan que escojamos hasta r elementos, que cada uno de ellos pertenezca a alguna de esas n categorías, las combinaciones con repetición nos indican cuantas posibilidades tenemos.

La relación entre las combinaciones con repetición y las combinaciones sin repetición, se obtiene de encontrar el número de soluciones enteras no negativas de la ecuación x1+x2+……xn=k, donde n son las n categorías, y k es el número de elementos que se nos permite sacar, y el número de soluciones de esta ecuación es C(n+k-1,k)

Por tanto, CR(n,k)=C(n+k-1,k)

Permutación circular de n objetos distintos de orden r, con r menor o igual que n, es colocar esos r objetos a elegir de n, en r posiciones igualmente espaciadas en la circunferencia. Nótese que el rotar una permutación circular no la hace diferente.

Propiedad: El número de permutaciones circulares de n objetos distintos de orden r es

C(n,r)(r-1)!

Teorema del binomio.

Propiedad: Dado un número combinatorio, C(n+1,k)=C(n,k)+(n,k-1)

Por tanto, C(n,k)=C(n-1,k)+C(n-1,k-1)

Triángulo de Pascal:

Los números combinatorios pueden sustituirse por el triángulo de Tartaglia, en el que los lados son unos, y cada elemento es igual a la suma de los dos que tiene arriba a derecha e izquierda.

Teorema del binomio:

Dado el binomio (x+y)n=Suma desde 0 hasta n de C(n,k)*xn-kyk. Alternativamente, es como sumar todos los elementos, multiplicados por su correspondiente número combinatorio, que es siempre n arriba, y empieza en 0 y acaba en n, y de tal manera de que el exponente de x empieza en n y el de y en 0 y luego esos exponentes van el primero disminuyendo una unidad en cada sumando y el segundo aumentando una unidad en cada sumando.

Nótese que si y=1, todo se reduce a sumar los x multiplicados cada uno por un número combinatorio y elevados al mismo k que ese número combinatorio.

Además, los número combinatorios usados se llaman coeficientes binómicos.

Además, 2n es igual a la suma de los números combinatorios C(n,k), desde k=0 hasta k=n.

Además, 0 también es igual a ir alternando los combinatorios de n de forma que el primero sume, el segundo reste, y así sucesivamente.

Propiedad: Dado m, k enteros, incluido el cero, y siendo k menor o igual que m

C(m+1,k+1)= C(k,k)+C(k+1,k)+…..+C(m,k)

Coeficiente multinómico: Dados k números enteros, no negativos, y la suma de todos igual a n, el coeficiente multinómico, P(n,n1,n2,….,nk) es igual a n!/(n1!n2!…..nk!).

Propiedad: Dados n objetos de k tipos, y ni el número de objetos del tipo i, con i entre 1 y k, y siendo la suma de los ni=n, entonces, hay P(n,n1,n2,….,nk) diferentes ordenaciones. Dos ordenaciones son iguales si para cada i los objetos que ocupan el lugar i son del mismo tipo.

Esto sirve para, si tenemos una colección n objetos, y cada uno de esos objetos es de un tipo (puede haber en esa colección dos o más objetos del mismo tipo) y el número de tipos es k, pues así se puede obtener el número de formas en que podemos ordenar esa colección. Es como una generalización de las combinaciones.

Formula de Leibnitz. Para coeficientes multinómicos: Se tiene que si sumamos x1,x2,….xn y lo elevamos a n, en cada sumando habrá un producto de los xi sumandos, cada uno de esos xi elevado a un exponente y de manera que la suma de todos los exponentes de cada sumando en un producto sea igual a n. Por lo tanto, elevar a n la suma de los xi sumandos es igual que hacer la suma de los P(n,n1,n2,….,nk)*x1n1 x2n2..xknk. O sea, multiplicado cada producto por el coefeciente multinómico correspondiente y los exponentes de cada xi sumando iguales a cada uno de los ni.

Principio de Inclusión-Exclusión.

Dado un conjunto finito S y Pi propiedades que pueden tener o no los elementos de S, o sea, que existen S(i) conjuntos con los elementos de S que satisfacen la propiedad número i, entonces, si consideramos la unión de todos los conjuntos S(i) de elementos que satisfacen al menos alguna de la esas propiedades, y por otro lado la intersección de todos los conjuntos S-S(i) (Esto es, la de todos los subconjuntos de S tales que no se cumple para ninguno de sus elementos la propiedad i, o sea los complementarios de los S(i) en S), resulta:

- Que el cardinal de la intersección de todos los complementarios es igual a la siguiente suma: Primero el cardinal del conjunto S, luego se le resta la suma de los cardinales de todos los subconjuntos S(i), luego se le suma la suma de los cardinales de todas las intersecciones dos a dos de todos los subconjuntos S(i), luego se le resta la suma de los cardinales de todas las posibles intersecciones tres a tres de todos los subconjuntos, y así sucesivamente, hasta que la última suma de cardinales de todas las intersecciones (Que por ser la de la intersección de los n subconjuntos correspondientes a las n intersecciones, sólo hay una interseccion) se suma o resta dependiendo de si n, el número total de propiedades es par o impar. Este cardinal es el número de elementos que no cumplen ninguna de las propiedades.

- Que el número de elementos que satisface al menos una de las propiedades será igual al cardinal del conjunto total menos el cardinal anterior (el que es el cardinal de la intersección de todos los complementarios, por tanto, el número de todos los elementos que no cumplen ninguna de las propiedades)

Desordenación: Una desordenación es una permutación en la que (puesto que una permutación es una biyección) a ningún elemento del conjunto A inicial, de n elementos, se le vuelve a asociar él mismo, o sea, todo elemento es sustituido por otro distinto. Se sabe que el número de desordenaciones posible es igual a, si n es el número de elementos, d(n)=n!*(Suma(Desde j=0 hasta n,(-1)j/(j!)).

Recursividad y Relaciones Recurrentes.

Definición: Una función f de N en R está definida recursivamente si para algún n0 se cumple que,

Una relación de recurrencia es lineal si la función r(n) puede expresarse como una combinación lineal de los valores anteriores de r(n) (r(n-1), r(n-2), …. r(n-t)) y sumada a ella la función k(n). Si k(n)=0, es lineal homogénea.

La sucesión de Fibonacci es una que se puede expresar así:

fib(n)=fib(n-1)+fib(n-2), si n=>3, y las condiciones iniciales son fib(1)=1 y fib(2)=2.

La ecuación característica de una relación de recurrencia lineal y homogénea es la que se obtiene al pasar a la izquierda a todos los componentes de la función, y sustituir los r(n), r(n-1)….r(n-t) de la siguiente forma:

xt-a1xt-1-a2xt-2-…-at-1x-at=0, donde los ai son los coeficientes de la combinación lineal de la relación de recurrencia lineal.

A partir de esta ecuación característica, si se encuentran sus raices (reales), una solución de la relación de recurrencia es de la forma r(n)=bn, si y sólo b es una raíz de la ecuación característica.

Además, si hay varias, b1, b2,… bt raíces no nulas y distintas, entonces, cualquier combinación lineal de b1n, b2n ,…,btn es también una solución de la ecuación de recurrencia, llamada también solución general.

Para obtener soluciones particulares, si se dan t condiciones iniciales del tipo r(i)=di, entonces, se puede obtener una solución particular, ya que se pueden usar esas di para construir un sistema de ecuaciones lineales que nos de los coeficientes de la combinación lineal que produjeron esas soluciones particulares.

La solución de la sucesión de Fibonacci es igual a multiplicar el inverso de la raiz cuadrada de cinco por la diferencia entre el número de oro elevado a n+1 y el número que es como el número de oro pero con la raiz cuadrada de cinco restando, también elevado ese número a n+1

El número de oro es 1+la raíz cuadrada de cinco, todo ello dividido entre 2.