Tema I: Números

Subconjunto:

A, B conjuntos, si todos los elementos de A pertenecen a B, entonces se dice que A está incluido en B o que A es subconjunto de B.

Unión:

X, Y conjuntos, se define su unión por los elementos que pertenezcan a X o a Y.

Intersección:

X, Y conjuntos, se define su intersección por los elementos que pertenezcan a X y a Y.

Conjunto vacío:

es el conjunto que no tiene ningún elemento, que tiene la propiedad de ser subconjunto de todos los conjuntos.

Diferencia de conjuntos:

A-B, son los elementos que están en A y que no están en B.

Axioma de suma y producto de los enteros (Z):

sean a y b enteros,

• la suma de dos enteros es un entero

• el producto de dos enteros es un entero

• el resultado de una suma de dos enteros o un producto de ellos es indep del orden (conmutat)

• a + ( b + c ) = ( a + b ) + c = ( a + c ) + b (asociatividad)

• a ( bc ) = ( ab ) c = b ( ac )

• a + 0 = a (elemento neutro)

• a . 1 = a

• a ( b + c ) = ab + ac (distributividad)

• existe un elemento (-a) tal que a + (-a) = 0 (unicidad)

• si a ð 0 y ab = ac, b = c

Axioma del buen orden:

sea N un conjunto (por ejemplo N=Z); y sea N0 el conjunto de N u {0}, es decir que No contiene a 0; todo subconjunto X de N (o de N0) posee automáticamente una cota inferior, ya que todo elemento x de X satisface x >= 1 (o x >= o). En este caso, el axioma del buen orden toma la forma “si X es un subconjunto no vacío de N o No, entonces X tiene un mínimo”.

Teorema de inducción:

consideramos un subconjunto S de X tal que se cumple que 1 ð S y que para un k de S, si k ð S, entonces k+1 ð S, entonces X=S.

(en el caso general, sea n un entero cualquiera, no necesariamente positivo, y S={k ð Z / k >= n0} y sea ScX que satisface n0 ð S y si k ð S implica que si k ð S entonces k+1 ð S, entonces S=X).

Demostración: supongamos que S ð N, considero que ð S = N-S, ð S diferente de vacío, entonces por el axioma del buen orden, existe m ð ð S mínimo de ð S.

1 ð S ð 1 ð S ð m ð 1, m-1 ð N, y además m-1 ð S, entonces, por hipótesis de inducción, m ð S. ð N = S

Teorema de la división entera:

dados dos enteros a y b, con b ð ð, existen q y r tales que a = bq + r, con 0 >= r >= b

Demostración: sea R = {x ð N ð{0}/ ð y ð Z tal que a = by + x}

a >= 0 entonces a = b.0 + a

a <= 0 entonces a = b.a + (1-b)a [(1-b)a >= 0] ðRðð

según el axioma del buen orden, R tiene un mínimo r. Para algún q ð Z, a = bq + r.

a = bq + r

a = bq + b + r - b

a = b(q + 1) + (r - b)

si r >= b, r - b >= 0, r - b ð R pero r - b < r (contradicción por que r - b sería más pequeño que el mínimo) ð r < b

a = bq + r

supongo que a = bq' + r'

tomemos q' < q ð q - q' > 1

r' = a - bq' = a - bq' + bq - bq = a - bq + b(q - q') = r + b(q - q')

como q - q' > 1, b(q - q') > 1 y r + b(q - q') > r + b > b

r y q son únicos.

Divisibilidad:

sean x, y ð Z, decimos que y divide a x (y ð x) si existe algún q tal que x = qy, q = x/y ð Z, y si y no divide a x, q ð Z

Máximo común divisor:

dados a, b ð Z, decimos que d ð Z es un máximo común divisor o mcd de a y de b si y sólo si:

• d ð a y d ð b

• si c ð a y c ð b , entonces c ð d

• d >= 0

Si a = bq + r, entonces mcd(a, b) = mcd(b, r) entonces r < b; y si d ð a y dð b, entonces d ð a - bq entonces d ð r

Sean a, b ð Z y b >= 0, y sea mcd(a, b) = d, entonces existen m y n ð ð tales que d = ma + nb.

Si mcd(a, b) = 1, entonces se dice que a y b son primos entre sí (no tienes factores comunes).

Si k > 0, entonces mcd(ka, kb) = k.mcd(a, b)

Números primos:

decimos que todo p ð ð, p > 1 es primo si sus únicos factores comunes son 1 y p.

• Corolario: decimos que a > 1 es compuesto si no es primo.

• Observaciones: a) 1 no es primo

b) a es compuesto implica que existen m1 y m2 ð N tales que a = m1.m2 (1 < (m1, m2) < a)

Lema de Euclides:

si a, b, c ð Z, a y c son primos entre sí si c ð ab implica que c ð b.

Demostración: a y c primos entre si, entonces ð m, n ð Z / ma + nc = 1 (= mba + nbc)

c ð nbc (c es uno de los factores de nbc) )

} c ð b

c ð mab (por la hipótesis c ð ab) )

Teorema fundamental de la aritmética:

si ð Z, n > 1, entonces existen primos p1, p2 ... pr tales que n = p1p2...pr

con p1 < p2 < ... < pr, y además la factorización es única en el sentido

de que n = q1q2 ...qs , con q1 < q2 < ... < qs entonces r = s y pi = qi.

Teoremas de los primos:

• El número de primos es infinito

• Sea a ð Z, a > 1, entonces si p <= (raíz cuadrada) a, p no divide a, entonces a es primo.

• (raíz)2 es irracional, a/b con a, b ð Z, y mcd(a, b) = 1

Dem: 2 = a2 / b2 ð a2 = 2b2 ð 2 ð a2 ð 2 ð a (lema de Euclides)

ð ð m ð Z / a = 2m ð 4m2 = 2b2 ð 2m2 = b2 ð 2 ð b2 ð 2 ð b

como mcd(a, b) = 1, es imposible que 2 ð a y 2 ð b. (raíz)2 es irracional.

Factorizaciones:

sean a = p1ððððð ptðt y b = q1ððððð qtðt factorizaciones canónicas.

b = p1ðð ððð ptðt donde algunos de los ði y ði pueden ser 0.

mcd(a, b) = p1 min(ðð, ððð ððð ptmin(ðt, ðtð = d.

Mínimo común múltiplo:

sean a, b ð Z, a > 1 y b > 1. Llamamos mínimo común múltiplo de a y b al menor entero positivo que es múltiplo de a y de b.

Factorizaciones:

sean a = p1ðð... ptðt y b = p1ððððð ptðt. mcm(a, b) = p1max(ðð, ðððððð ptmax(ðt, ðt)

Relación entre mcm y mcd:

mcm(a, b) . mcd(a, b) = ab

Ecuaciones diofánticas (ax + by = n):

sean a, b, n ð Z, la ecuación lineal ax + by = n tiene solución entera si y sólo si mcd(a, b)ð n.

Dem: sean x0 , y0 solución de la ecuación con x0 , y0 ð ð.

ax0 + by0 = n. Si d = mcd(a, b) entonces dð ax0 y dð by0, dð ax0 + by0 ð dð n.

ð ð p ð ð / n = pd.

Supongamos que dð n, si n = 0, x0 , y0 = 0 (es solución)

si n ð 0, mcd(a, b) ð 0 (es d), am + bm' = d,

apm + bpm' = pd = n (pm = x y pm' = y)

x = (m.n)/d e y = (m'.n)/d

Tema II: Teoría de conjuntos

¡¡¡ a elemento del conjunto A, nunca es igual a un conjunto: no puedo escribir a = B aunque a = x y B = {x}!!!

• Dos conjuntos son iguales si sus elementos son iguales

• S es subconjunto de T si todo elemento de S esta en el conjunto T

S = T ð S ð T y T ð S

Conjunto vacío ð:

es aquel que no tiene ningún elemento

ð ð A para todo conjunto A

Si S ð T y S ð ð, S ð T, entonces S es subconjunto propio.

Intersección de conjuntos:

S, T conjuntos, S ðT = { x / x ð S y x ð T}

Propiedades:

1) S ð T ð S, S ð T ð T

2) Si S ð T = ð, decimos que S y T disjuntos.

3) A ð ( ð ð C ) = ( A ð ð ð ð C

A ð ð ð ð ð ð

A ð ð ð ðð ð ð ð ð ð

A ð ð ð ð si y sólo si A ð ð

Si i = 1, 2, ..., n; ð Si = S1 ð S2 ð ... ð Sn

Unión de conjuntos:

S ð T = {x / x ð S o x ð T}

Propiedades:

S ð S ð T; T ð T ð S

A ð (B ð C) = (A ð B) ð C

A ð A = A; A ð ð =A

A ð B = B si y sólo si A ð B

Leyes distributivas:

A ð (B ð C) = (A ð B) ð (A ð C)

A ð (B ð C) = (A ð B) ð (A ð C)

Diferencia de conjuntos:

S - T = { x / x ð S y x ðT}

Propiedades:

S - T ð S

S - T = ð ð S ð T

A - B = A ð A ð B = ð

A - B = A - C ð A ð B = A ð C

A - ð = A; A - A = ð

A - (B ð C) = (A - B) ð (A - C)

A - (B ð C) = (A - B) ð (A - C)

Producto cartesiano de conjuntos:

S*T = {(s, t) / s ð S y t ð T}

Proposiciones:

el orden es importante

en general, S*T ð T*S

S*(T*V) ð (S*T)*V

(A*B) ð (C*D) = (A ðC)*(B ð D)

(A ð C)*(B ð D) = (A*D) ð (A*B) ð (C*B) ð (C*D)

(A*B) - (C*D) = (A*(B - D)) ((A - C)*B)

Aplicaciones:

una aplicación f con dominio X y recorrido Y es un subconjunto de X*Y tal que se verifiquen:

ð x ð X ð ð y ð Y / (x, y) ð f

si (x, y) ð f, y (x, y') ð f ð y = y'

Igualdad de aplicaciones:

f, g ð X*Y, si f = g, entonces f ð g; g ð f

f = g si tienen mismo dominio, X; mismo codominio, Y; y misma acción.

Aplicación identidad:

X*X; ix = {(x, y) ð X2 / x = y}

(Ej, si X = {1,2}, X2 = {(1, 1); (1, 2); (2, 1); (2, 2)}, ix = {(1, 1); (2, 2)})

Imagen de un conjunto bajo una aplicación:

f:X → Y; A ð X; f(A) = { y ð Y / (x, y) ð f con x ð A};

f(A) = {y ð Y / f(x) = y con x ð A}.

Imagen inversa:

f:X → Y; B ð Y; f -1(B) = { x ð X / f(x) ð B}

Aplicación suprayectiva (o exhaustiva):

Cada y de Y es el valor f(x) de al menos un x de X. (todas las imágenes tienen antecedente)

Aplicación inyectiva:

Cada y de Y es el valor f(x) de un x de X como máximo.

f(x) = f(y) ð x = y; y x = y ð f(x) = f(y)

Aplicación biyectiva:

Cada y de Y es el valor f(x) de exactamente un x de X.

Composición de aplicaciones

Sean f:X → Y; g:Y → Z; se define la composición fog como

fog:X → Z

fog:x → g(f(x))

fog = {(x, z) ð X*Z / (f(x), z) ð g}

propiedades:

si f:X → Y; g:Y → Z; h:Z → W, entonces se cumple la propiedad asociativa (hog)of = ho(gof)

si f:X → Y es biyectiva y su inversa es f -1:Y → X, entonces f -1of = ix, y fof -1 = iy

Relación:

Cualquier subconjunto del producto cartesiano de dos conjuntos: R ð X*Y (relación con dominio X y recorrido Y)

Rx = {y ð Y / (x, y) ð R}

Relación de equivalencia:

Una relación de equivalencia en un conjunto X es un subconjunto R ð X*X que cumpla:

ð x ð X, (x, x) ð R (propiedad reflexiva)

ð x, y ð X, (x, y) ð R (propiedad simétrica)

ð x, y, z ð X, si (x, y) ð R y (y, z) ð R, entonces (x, z) ð R (propiedad transitiva)

Partición de un conjunto:

Sea un conjunto X y sean Ai ð X, se dice que los Ai proporcionan una partición de X si la intersección de los Ai = ð , y la unión de los Ai = X.

Proposición:

Si X es un conjunto y R una relación de equivalencia en X, entonces las clases de equivalencia proporcionan una partición de X. Además hay una biyección entre el conjunto de las particiones de X y el de las clases de equivalencia que se pueden definir en X

Números de Stirling:

S(n, k) número de particiones de un conjunto de n elementos en k partes.

S(n, 1) = 1; S(n, n) = 1

S(n, k) = S(n - 1, k - 1) + k.S(n - 1, k)

Conjuntos finitos y numerables:

Nk = {1, 2, 3, ..., k}

Se dice que un conjunto es finito si existe una biyección entre ese conjunto y algunos de los Nk.

Se dice que un conjunto es infinito cuando no es finito.

Conjunto numerable:

Un conjunto es numerable cuando existe una biyección entre él y el conjunto de los números naturales N.

Partes de un conjunto:

Si x es un conjunto llamamos P(X) al conjunto formado por todos sus subconjuntos (incluido el valor 0)

Proposición:

Es imposible construir una biyección entre un conjunto y el conjunto de sus partes.

Corolario:

Hay conjuntos no numerables

Si un conjunto X es finito y tiene n elementos, entonces P(X) tiene 2n elementos.

Tema III Conjuntos ordenados y relaciones de orden.

Propiedad antisimétrica:

Sea R una relación en un conjunto de X. Decimos que se cumple la propiedad antisimétrica cuando, si xRy y yRx, entonces x = y.

(x relacionado con y...).

Relación de orden:

Si R es una relación en A (ð ðð, decimos que R es una relación de orden si cumple las propiedades reflexiva, transitiva y antisimétrica.

Al par (A, <=) es le llama conjunto parcialmente ordenado.

Ejemplo, demostremos la relación de orden:

E; P(E) conjunto y subconjunto.

ð ; (P(E), ð ) parcialmente ordenado.

1) reflexiva: ð A ð P(E), A ð A

2) transitiva: A, B, C ð P(E): A ð B y B ð C ð A ð C

3) antisimétrica: A, B ð P(E): A ð B y B ð A ð A = B

Orden total:

Se dice que (A, <=) está totalmente ordenado si ð x, y ð A se cumple x <= y o y <= x.

Ejemplo: E = {a, b, c} B = {{a}, {a, b}, {a, b, c}}ð P(E). (B, ð ) es totalmente ordenado aunque (P(E), ð ) no.

Cota superior (inferior):

Se dice que k A es cota superior (inferior) de B si b <= k ð b ð B. (o k <= b ð b ð B).

Si B tiene alguna cota superior (o inferior) en A, entonces B está acotado superiormente (o inferiormente).

Supremo e ínfimo:

Se llama supremo a la “más pequeña” de las cotas superiores (no precedida por las demás).

Se llama ínfimo a la “más grande” de las cotas inferiores (precedida por las demás).

Máximo y mínimo:

Si el supremo B, entonces el supremo se llama máximo.

Si el ínfimo B, entonces el ínfimo se llama mínimo.

Si existen, el máximo y el mínimo son únicos.

Elementos maximales y minimales:

Se dice que un elemento de A es maximal si no hay elementos de A que precedan a este (que vayan después).

Se dice que un elemento de A es minimal si no hay elementos de A que antecedan a este (que vayan antes).

Buen orden:

Se dice que el orden <= definido en A es un buen orden si cualquier subconjunto de A con el orden inducido tiene mínimo.

Si en un conjunto hay buen orden, entonces el conjunto está totalmente ordenado.

Retículo:

Se dice que un conjunto ordenado (A, <=) es un retículo si x, y A se cumple que supA{x, y} e infA{x, y} existen.

Álgebra de Boole:

Sea K ð ð , y dos operaciones binarias + y ., decimos que (K, +, .) es un álgebra de Boole si se cumplen:

• + y . asociativas: a + (b + c) = (a + b) + c y a . (b . c) = (a . b) . c

• + y . conmutativas: a . b = b . a y a + b = b + a

• + y . tengan elemento neutro: 0 para + y 1 para ., tales que a + 0 = a y a . 1 = a

• + y . distributivas una respecto de la otra: a + bc = (a + b)(a + c) y a (b + c) = ab + ac

• ð a ð K ð a'ð K / a + a' = 1 y a . a' = 0

Cálculo proposicional:

Proposición: afirmación sobre la que puedo afirmar de manera no ambigua algo que es cierto o algo que es falso.

Prop atómica: la proposición más sencilla posible.

Prop molecular: combinación de proposiciones atómicas.

Conectores lógicos: partículas o símbolos que me permiten construir proposiciones complejas a partir de otras atómicas.

• Disyunción “o”

• Conjunción “y”

• Negación “no”

• Condicional “si ... entonces ...”

• Doble condicional “... si y sólo si ...”

• Disyunción exclusiva “o ... o ...”

Tautologías:

Forma proposicional siempre verdadera independientemente del valor de las proposiciones que la componen.

Contradicciones:

Forma proposicional siempre falsa independientemente del valor de las proposiciones que la componen.

Implicación:

Condicional que es tautología.

Doble implicación:

Doble condicional que es tautología.

Contingencia:

Ni tautología ni contradicción.

Tautologías notables:

P ð Q ð P simplificación

P ð P ð Q adición

Q ð (P → Q) condicional

(P → Q) ð (Q → R) ð (P → R) silogismo hipotético

(P → Q) ð (R → S) ð (P ð R) ð Q ð S silogismo disyuntivo

(P → Q) ð P ð Q Modus Ponens

(P → Q) ð ðQ ð ðQ Modus Tollens

A ð B ð (ðA) → B Tollendo Ponens

P → Q ð ðP ð Q condicional disyuncional

(P → Q) ð (Q → P) ð P ð Q condicional bicondicional

(ðP ð Q) ð (ðQ ð P) ð P ð Q condicional bicondicional

Equivalencia de proposiciones ð

Dos proposiciones son equivalentes si sus tablas de verdad coinciden.

Propiedades:

• P ð Q ð Q ð P conmutativa

P ð Q ð Q ð P

• P ð (Q ð R) ð (P ð Q) ð R asociativa

P ð (Q ð R) ð (P ð Q) ð R

• P ð (Q ð R) ð (P ð Q) ð (P ð R) distributiva

P ð (Q ð R) ð (P ð Q) ð (P ð R)

• P ð ðP ð ð negación

P ð ðP ð ð

• P ð ð(ðP)

• P ð P ð P idempotencia

• P ð P ð P

• P ð ð ð ð

• P ð ð ð ð

Leyes de De Morgan

ð(P ð Q) ð ðP ð ðQ

ð(P ð Q) ð ðP ð ðQ

Inferencia lógica

Obtención de proposiciones ciertas a partir de otras proposiciones ciertas.

Ley de inferencia:

Ley de unión: si tengo dos premisas P y Q en un proceso de inferencia entonces puedo concluir PðQ.

Ley de inserción de tautologías: en cualquier punto de un proceso de inferencia puedo insertar una tautología.

Ley de uso de tautologías: si una tautología es una implicación, entonces si el antecedente es verdadero, el consecuente también lo es.

Implicaciones de la forma Að B

Að B ð ðB ð ðA

Bð A ð ðA ð ðB

Métodos de demostración

Método directo (usando las tautologías notables)

Método de reducción al absurdo

P1, P2, ... , Pn premisas

Queremos concluir S

Añadimos como premisa adicional ðS

Mediante las reglas de inferencia lógica buscamos obtener la negación de alguna de las premisas iniciales (1)

Si obtenemos la contradicción A ð ðA, llegamos a la contradicción y S es verdadero

Esquema del procedimiento:

P1

P2

.

.

Pn

ðS

ð

ð

ðð

Concluye A ð ðA

Demostración condicional

Queremos demostrar A B

Añadimos como premisa auxiliar A

Ejemplo:

P1: R → (S → Q) Quiero concluir P Q

P2: ðP ð R

P3: S

P4: P premisa auxiliar

P5: P → R CD(2)

P6: R MP(4, 5)

P7: S → Q MP(1, 6)

P8: Q MP(3, 7)

C: P → Q

Cuantificadores

Universal ð: “para todo valor”. Se utiliza para la proposición que sea verdadera para todo elemento del conjunto.

Existencial ð: Se usa en el caso de existir elementos del conjunto para los que la proposición es verdadera.

Uso de los cuantificadores

ð(ðx ð E, P(x)) ð ðx ð E, ðP(x)

ð(ðx ð E, P(x)) ð ðx ð E, ðP(x)

(ðx ð E, P(x)) ð (ðx ð E, Q(x)) ð ðx ð E, P(x) ð Q(x)

(ðx ð E, P(x)) ð (ðx ð E, Q(x)) ð ðx ð E, P(x) ð Q(x)

(ðx ð E, P(x)) ð (ðx ð E, Q(x)) ð ðx ð E, P(x) ð Q(x)

(ðx ð E, P(x)) ð (ðx ð E, Q(x)) ð ðx ð E, P(x) ð Q(x)

Los cuantificadores son conmutativos: ð x1ðE1, ðx2 ðE2 ð ðx2 ðE2, ð x1ðE1

Tema IV: Combinatoria

Combinaciones

Sea A ð ð un conjunto finito de cardinal n. Se llama combinación a cada subconjunto de m elementos cogidos de entre los n.

Al número de combinaciones de m elementos de A se le llama número combinatorio.

(n m) = n! / m!(n - m)!

Dem por inducción:

Sabemos (n 0) = (n n) = 1 (base de inducción)

Supongo (k j) = k! / j!(k - j)! cierto para 0 ð j ð k y 0 ð k ð n.

Probamos que (n-1 m-1) + (n-1 m) = (n m)

• El número de subconjuntos de m - 1 elementos que puedo formar con A - {1}.

(n-1 m-1) número de subconjuntos de A de m elementos que contienen el elemento 1.

• (n-1 m) número de subconjuntos de m elementos que no tienen el elemento 1.

(n-1 m-1) + (n-1 m) = (m(n-1)! / m!(n-m)!) + ((n-m)(n-1)! / m!(n-m)!) = n! / m!(n-m)!

Propiedades

(n m) = (n n-m)

ð (n i)(m j) = (n+m k) con 0 ð k ð n+m y 0 ð i ð n

ð (n j)2 = (2n n)

ð (k n) = (n+1 m+1)

(n m) = (n-1 m-1) + (n-1 n)

Teorema del binomio de Newton

(a+b)n = ð (n k) ak.bn-k

Combinaciones con repetición

Sea A un conjunto de m elementos (An = A * A * ... * A -- n veces)

Definimos (a1, a2, ... , an) R ( b1, b2, ... , bn) -- R = relación de equivalencia

si aparecen los mismos elementos y si cada uno de ellos aparece repetido el mismo número de veces.

Def: cada una de las clases de equivalencia, definidas en An por la relación anterior recibe el nombre de MULTICONJUNTO DE ORDEN n o COMBINACIÓN ON REPETICIONES de m elementos tomados de n en n.

Prop: el número de combinaciones con repetición de m elementos tomados de n en n es (n+m-1 n)

Variaciones Vn,m

Dado un conjunto A de n elementos, llamamos variación de orden m a cada uno de los subconjuntos ordenados de m elementos.

Prop: Vn,m = n! / (n-m)!

Permutaciones Pn

Pn = n!

Variaciones con repetición VRn,m

Dado un conjunto A de n elementos, se llaman variaciones con repetición de n elementos tomados de m en m a los elementos de Am

Permutaciones con repetición

Sea A no vacío que tenga cardinal n. Sea BðA subconjunto de cardinal m. a, bðA son B - cromáticos si a, bðB.

Dos permutaciones son b - cromáticas cuando sólo difieren en el orden en el que están en el subconjunto (ej. ac1bc2c3 y ac2bc3c1 son permutaciones b - cromáticas)

Pnm1, m2... (con m1 + m2 + ... = n) = n! / (m1! + m2! + ...) = (n m1, m2, ...)

Ej. Cuantas palabras se pueden formar con las letras de la palabra MAMA (pudiendo repetir letras): P 4 2, 2 = 4! / (2! + 2!) = 6

Prop: ( a1 + a2 + ... + an) = (n m1, m2, ...) a1m1 ... anmn

Tema V: Grafos

Definición

Es un conjunto finito cuyos elementos reciben el nombre de vértices V y un conjunto E de subconjuntos de V de dos elementos (aristas)

Isomorfismo de grafos

Se dice que dos grafos son isomorfos si existe una aplicación biyectiva ð: v1→v2 de forma que {x, y} es una arista si y sólo si (ð(x), ð(y)) lo es. A la aplicación ð se la llama isomorfismo.

Dos grafos NO son isomorfos si:

no tienen el mismo número de vértices

no tienen el mismo número de aristas

los vértices no son de mismo grado

el orden de los ciclos no es el mismo

Grado de un vértice

Sea un grafo G(V, E) y V un vértice. Se llama grado de V, δ(V), al número de aristas que lo contienen.

Teorema

La suma de los grados de todos los vértices de un grafo es igual al doble del número de aristas. ðδ(V) = 2E.

El número de vértices impares en un grafo es siempre par.

Grafo regular de grado r

Si todos los vértices tienen grado r, el grafo es regular, y ðδ(V) = 2E.

Aplicación

Bajo un isomorfismo δ(ð(u)) = δ(u)

Recorrido

Sea G(V, E). Toda sucesión de vértices adyacentes V1, V2,..., Vn de forma que {Vi, Vi+1}ð E ð i = 1, 2, ..., n-1

Camino

Recorrido en el que todos los vértices son distintos

Equivalencias de vértices

Sea el grafo G y V = V1 ð...ð Vv la partición correspondiente a la relación de equivalencia r. Sea Ei (1 ð i ð r) el subconjunto de E formado por las aristas cuyos extremos están ambos en Vi entonces los grafos G(Vi, Ei) reciben el nombre de componentes del grafo G.

Un grafo es conexo si sólo tiene una componente.

Ciclo

Es el recorrido en el que sólo se repiten el primer y el último elemento (1º = ultimo)

Ciclo hamiltoniano

Ciclo que contiene a todos los vértices de un grafo.

Recorrido euleriano

Recorrido en el que aparece cada arista del grafo.

Prop: si x ð y, la condición para que haya un recorrido euleriano que empiece en x, y acabe en y, es que x e y sean impares y todos los demás pares.

La condición necesaria y suficiente para la existencia de un recorrido euleriano en un grafo es que tenga como máximo dos vértices impares.

Árboles

Un grafo T es un árbol si:

i) es conexo.

ii) no hay ciclos.

Si T(V, E) es un árbol que tiene al menos dos vértices, entonces:

ð x, y ðT existe un único camino que los une.

el grafo que se obtiene al eliminar una arista cualquiera tiene dos componentes.

E = V - 1

Coloreado de vértices

Consiste en dar colores diferentes a los vértices adyacentes.

Coloración de un grafo

Una coloración de los vértices de un grafo G(V, E) es una función C: V → N que cumple C(x) ð C(y) si {x, y}ð E.

Número cromático de un grafo X(G)

Es el menor número natural k tal que existe una coloración con k colores.

El algoritmo voraz indica una coloración aceptable.

Teorema

Si G es un grafo cuyo grado máximo es k, entonces:

X(G) ð k + 1

Si G es conexo y no regular, X(G) ð k

Grafo bipartido

Es un grafo con X(G) = 2.

Un grafo es bipartido si y sólo si no tiene ciclos de longitud impar.

1

5

- -