Historia

1

´ I.T.I. GESTION ´ CON LOS EJERCICIOS RESUELTOS BOLETIN

´ MATEMATICA DISCRETA

1. Introducci´n a la teor´ de grafos o ıa
1. a) ¿Cu´ntas aristas tiene Kn ? a b) ¿Cu´ntas aristas tiene Km,n ? a Soluci´n. o a) Con generalidad, ocurre en teor´ de grafos que un mismo problema se puede resolver de varias ıa formas distintas, algunas m´s cortas que otras, algunas m´s elegantes que otras.Aunque basta a a resolver el problema por uno de entre los m´todos disponibles, siempre es enriquecedor plantearse e alternativas distintas para resolver un mismo problema. En el caso que nos lleva, el n´mero de u n(n − 1) aristas de Kn es a = , cuesti´n que vamos a demostrar de tres formas distintas. o 2 a.1) Si tratamos de contar las aristas una a una, resulta que del primer v´rtice, x1 , salen n −1 e aristas; del segundo, x2 , n − 2 que no se hayan contado (todas, salvo la que une x2 con x1 , que se ha contado antes); y, as´ sucesivamente, del i-´simo v´rtice, xi , salen n − i aristas que ı e e no se hayan contado antes. De hecho, de xn−1 sale una sola arista que no se haya contado antes, precisamente la que une este v´rtice con xn . Y de xn no hay ninguna arista que salga e que no hayasido contemplada con anterioridad. En definitiva, el grafo tiene tantas aristas como suma la expresi´n a = (n − 1) + (n − 2) + · · · + 1 + 0, progresi´n aritm´tica de paso 1 o o e n(n − 1) que se puede hallar sumando los t´rminos extremos dos a dos; de manera que a = e . 2 a.2) Utilizando argumentos de combinatoria, el grafo Kn tiene todas las aristas que caben entre los n v´rtices. Como una aristaes un par no ordenado de v´rtices, Kn consta de todos e e los pares no ordenados que se pueden formar con n v´rtices, sin repetir ninguno; esto es, e n(n − 1) n combinaciones de n elementos tomados de 2 en 2, C2,2 = = . 2 2 e u a.3) El grafo completo Kn consiste en un grafo (n − 1)-regular de n v´rtices. Seg´n el lema del apret´n de manos, o
n

2a =
xi ∈V

δ(xi ) =
i=1

(n − 1) = n(n − 1)n(n − 1) . 2 b) Aunque este apartado se puede resolver tambi´n de varias formas, an´logas a las anteriores, s´lo e a o mostraremos la ultima modalidad, aplicando el lema del apret´n de manos. El grafo Km,n consta ´ o de m v´rtices de valencia n y otros n v´rtices de valencia m. De manera que ha de ser e e de donde a =
m m+n

2a =
i=1

n+
i=m+1

m = mn + nm = 2mn

de manera que a =mn.

2. Demostrar que todo grafo de 3n v´rtices de valencias comprendidas entre n y n + 2 contiene al menos e bien n v´rtices de valencia n, bien n + 2 v´rtices de valencia n + 1, bien n + 1 v´rtices de valencia e e e n + 2. Soluci´n. o

Matem´tica Discreta. Ingenier´ T´cnica en Inform´tica de Gesti´n a ıa e a o

2

Sea un grafo de 3n v´rtices de valencias n, n + 1 o n + 2. Si no tiene almenos bien n v´rtices de e e valencia n, bien n + 2 v´rtices de valencia n + 1, bien n + 1 v´rtices de valencia n + 2; entonces tiene e e a lo m´s n − 1 v´rtices de valencia n, n + 1 v´rtices de valencia n + 1 y n v´rtices de valencia n + 2. a e e e Pero como el grafo tiene 3n v´rtices, estas cantidades se alcanzan, de manera que n − 1 de los v´rtices e e tienen de hecho valencia n, otros n + 1tienen valencia n + 1 y los restantes n tienen valencia n + 2. As´ la lista de grados es de la forma (n+2, . n ., n+2, n+1, n+1, n+1, n, n−1, n). Pero esto es imposible, ı, . ... ... porque hay un n´mero impar de v´rtices de valencia impar: u e • Si n es par, los v´rtices de valencia impar son aquellos con valencia n + 1, que totalizan n + 1 e v´rtices, ¡en cantidad impar! e • Si n es impar, losv´rtices de valencia impar son aquellos con valencia n + 2 y valencia n, que e totalizan 2n − 1 v´rtices, ¡tambi´n en cantidad impar! e e De manera que el grafo ha de tener al menos bien n v´rtices de valencia n, bien n + 2 v´rtices de e e valencia n + 1, bien n + 1 v´rtices de valencia n + 2. e

3. Un conjunto de v´rtices I de un grafo G(V, A) se dice independiente si en I no hay dos v´rtices e e...