Tarea 01-Gráficas isomorfas y gráficas bipartitas PDF

Preview

Summary

Download Tarea 01-Gráficas isomorfas y gráficas bipartitas PDF

Description

Sean G y H gráficas:   1. Demuestren que si G es una gráfica simple entonces m ≤ n2 . Solución Primero tratemos de ver cual podría ser la idea detrás del enunciado. Que G sea simple significa que no tiene lazos ni multiaristas por lo que la función de incidencia debe asignar una sola arista a cada par de vértices y como es una función inyectiva esa asignación es única.   De forma que si solo hay dos vértices, es decir, un par de vértices, entonces habrá una sola arista ( mG = n2G ) y si seagregan más vértices se formarán más pares de vértices pero sólo se tendrá una arista por cada par ( mG < n2G ).   *mG es la cantidad de aristas y nG la cantidad de vértices de la gráfica G, así pues 2nG es el número de pares posibles de vértices del conjunto VG . Para la prueba utilicemos un resultado de Cálculo: Si una función f : X −→ Y esinyectiva entonces |X| ≤ |Y |.  En este caso, por ser G una gráfica simple, la función de incidencia Ψ: AG−→ VG 2 es inyectiva y por dicho  V      n  resultado tenemos que |AG | ≤ | V2G |. Retomando la notación, |AG | = mG y  2G  = 2G , por lo tanto mG ≤ n2G . 2. Den un ejemplo de una gráfica tal que m >

n  2

(esta gráfica no puede ser simple).

Solución Consideremos  donde el conjunto de aristas es A={a,b} y el de vértices V={u,v} por lo   un ejemplo muy sencillo que m=2 y 2n =1 y por lo tanto m> n2 .

Evidentemente si quitamos el lazo o la multiarista esto ya no se cumple, entonces una grafica simple no puede tener un mayor número de aristas que de combinaciones de vértices. 3. Muestren que si G y H son dos gráficas isomorfas entonces nG = nH y mG = mH . Solución = H por lo que existe un isomorfismo f = (fV , fA ) : G −→ H donde fV : VG −→ VH y Supongamos que G ∼ fA : AG −→ AH son funciones biyectivas. Es decir, existe una función biyectiva entre los conjuntos VG y VH , así como entre AG y AH , por lo que éstos deben tener la misma cardinalidad: |VG | = |VH | y |AG | = |AH |. Por lo tanto nG = nH y mG = mH . 4. Den un ejemplo de dos gráficas distintas G y H tales que nG = nH y mG = mH pero G ∼ 6 = H. Solución En este ejemplo nG = 4 = nH y mG = 3 = mH pero las reglas de correspondencia difieren pues en la gráfica G tenemos que G Ψ(a3 ) = v2 v4 , mientras que en la gráfica H Ψ H , (fA (a3 )) = u3 u4 = fv (v3 )fv (v4 ) 6= fv (v2 )fv (v4 ). Por lo que no se preserva la estructura de la gráfica G. Por lo tanto G 6∼ = H.

5. Demuestren que m(Kj,i ) = i j. Solución Sea V = U ∪ U ′ la bipartición de Kj,k . Por definición |U|=j y |U’|=k. Como la gráfica es completa cada vértice de U es adyacente a cada vértice de U’. Además tenemos que es simple por lo que cada vértice de U tiene asociado k aristas (o de forma simétrica, cada vértice de U’ tiene j aristas). Es decir, si vi ∈ U con i={1,...,j} entonces gKj ,k (vi ) = k y análogamente, si vl ∈ U ′ con l={1,...,k} entonces gKj ,k (vl ) = j Luego, X V

gKj ,k =

j X

gKj ,k (vi ) +

k X

(1)

gKj ,k (vl )

l =1

i =1

= jgKj ,k (vi ) + kgKj ,k (vl )

(2)

= jk + kj

(3)

= 2jk

(4)

Ahora, por el Teorema 1.23 de la suma de los vértices tenemos que X gKj ,k = 2jk 2m(Kj , k) =

(5)

V

Y dividiendo entre dos ambas partes obtenemos que m(Kj , k) = j ∗ k . 6. Muestren que si G es una gráfica bipartita y H ≤ G con nH ≥ 2 entonces H también es bipartita. Sugerencia: Supongan que VG = U ∪ U ′ es la bipartición de G y hagan por separado el caso en el que |VH ∩ U |, |VH ∩ U ′ | ≥ 1 y el caso en el que alguna de las intersecciones es vacía, digamos VH ∩ U = ∅, entonces VH ⊆ U ′ ¿H puede tener aristas en este caso? Solución Sea G = (AG , VG ) con VG = X ∪ Y la bipartición de G, donde X ∩ Y = ∅, |X| = 6 ∅ 6= |Y | y es tal que para toda arista a∈ AG , Ψ (a) ⊆ {uv |u ∈ X, v ∈ Y }. Supongamos que H no es trivial, es decir, nH ≥ 2 y como H ≤ G, por definición VH ⊆ VG , AH ⊆ AG y Ψ H =Ψ G ↾AH . Sea b ∈ AH , Ψ H (b) = Ψ G (b) ⊆ {uv |u ∈ X ∩ VH y v ∈ Y ∩ VH } = B

(6)

Consideremos los siguientes dos casos: 1. |VH ∩ X |, |VH ∩ Y | ≥ 1 Tenemos que VH = (VH ∩ X) ∪ (VH ∩ Y ). Como H ≤ G entonces VH ⊆ VG = X ∪ Y . Por lo que VH ∩ X ⊆ X y

Page 2

VH ∩ Y ⊆ Y . Luego, (VH ∩ X) ∩ (VH ∩ Y ) ⊆ X ∩ Y = ∅ y (VH ∩ X) 6= ∅ 6= (VH ∩ Y ) y por (6) se cumplen todas las condiciones para que H sea bipartita . 2. VH ∩ X = ∅ y |VH ∩ Y | ≥ 1 Como VH ∩ X = ∅ entonces VH ⊆ Y y además B = ∅ (pues no existe un v ∈ X ∪ VH ) por lo que H no tiene aristas en este caso. Pero como tiene al menos dos vértices podemos formar una bipartición arbitraria VH = XH ∪ YH (XH ∩ YH = ∅ y XH 6= ∅ = 6 YH ) y se cumple por vacuidad que si b ∈ AH : Ψ H (b) = Ψ G (b) = ∅ ⊆ B = ∅.

(7)

Por lo tanto, en este caso H también es bipartita. 7. Sea A = AG la matriz de adyacencia de G, demuestren que si G es simple entonces los elementos de la diagonal de A2 son los grados de los vértices correspondientes de G . Sugerencia: Pueden usar sin demostrar que A es simétrica. Justifiquen brevemente y utilicen que la suma de los elementos de una de sus columnas (o renglones) es el grado del vértice correspondiente. Recuerden que 02 = 0 y 12 = 1. Solución Recordemos que dadas dos matrices A ≡ (ai ,k )m×n y B ≡ (bk,j )n×p , el producto de ambas se define como AB˙ ≡ (ci,j )m×p =

n X

ai,k bk ,j

(8)

k=1

Por lo que los elementos de la diagonal de A son de la forma: (A2 )ii =

n X

(9)

ai,j aj,i

j =1

Debido a que G es simple y sabemos que A es simétrica, tenemos primero que ai,j ∈ {0, 1} y ai ,i = 0 para cualesquiera i , j ∈ {0, 1, 2, . . . , nG } y a su vez aj,i = ai,j y a2i,j = ai ,j . Con esto la expresión (9) queda de la forma (A2 )ii =

nG X j =1

ai,j ai ,j =

nG X j =1

a2i,j =

nG X

ai,j = gG (vi )

(10)

j =1

donde en la penúltima igualdad usamos que 02 = 0 y 12 = 1 y la última igualdad es porque estamos sumando sobre todas las aristas que se unen a vi y esto es por definición el grado de un vértice. 8. Muestren que en una gráfica simple no trivial siempre hay dos vértices (por lo menos) que tienen el mismo grado. Solución Sea G = {VG , AG , Ψ G } una gráfica simple no trivial con |VG | = n, es decir, n>1 y no hay lazos ni multiaristas. Sea v ∈ VG . Debido a que G es simple existe a lo más una arista entre v y algún u ∈ VG , con u 6= v . Observemos que si v está unido con todos los demás vértices entonces su grado corresponde al grado máximo, gG (v ) = n − 1 y en ese caso el grado mínimo sería uno por lo que 1 ≤ gG (v ) ≤ n − 1. Otro caso es cuando hay un vértice que no está unido a ningún otro, el grado mínimo es cero y forzosamente el máximo grado podrá ser n-2: 0 ≤ gG (v ) ≤ n − 2. Dado que G tiene n vértices y |{0, 1, . . . , n − 2}| = |{1, 1, . . . , n − 1}| = n-1 entonces debe suceder que al menos dos vértices tengan el mismo grado.

Page 3...