Diferencia entre revisiones de «Práctica 5: Clases de Grafos (Algoritmos III)»

De Cuba-Wiki
Línea 83: Línea 83:
<br>b) Sup. que |E|>|E'| => existe e en E / e = (v,w) y no existe (f(v),f(w)) ABS
<br>b) Sup. que |E|>|E'| => existe e en E / e = (v,w) y no existe (f(v),f(w)) ABS
<br>c) Es equivalente a decir que d(v) = d(f(v))
<br>c) Es equivalente a decir que d(v) = d(f(v))
<br>d)
<br>d) Vale por la biyeccion entre circuitos simples entre G y H
<br>e)
<br>e)  
<br>f)
<br>f) *-*-*-*-*  *-*-*-*-*
<br>    *            *
<br>g)
<br>g)



Revisión del 17:19 15 nov 2006

Ejercicio 05.01:


3*n = Σv 3 <= Σv d(v) = 2*m = 2*19 = 38
Entonces n <= 38/3 ∼ 12

Ejercicio 05.02:


a)
2*n = Σv 2 = Σv d(v) = 2*m = 2*12 = 24
Entonces n = 24/2 = 12
b)
3*n + 3 = 12 + 3*n - 9 = 3*4+(n-3)*3 = Σv d(v) = 2*m = 2*15 = 30
Entonces n = 27/3 = 9
c)
k*n = Σv d(v) = 2*m = 2*20 = 40
Entonces n = 40/k

Ejercicio 05.03:

Ejercicio 05.04:

Sup. que todos los grados son distintos. Entonces los vertices tienen todos los grados posibles, de 0 a n-1. Pero si esto pasa, entonces tengo un vertice conectado a todos (el de grado n-1) y al mismo tiempo otro conectado a ninguno (el de grado 0). ABS => Existen 2 vertices del mismo grado.

Ejercicio 05.05:

Si esto pasara entonces Σv d(v) = 2*m <=> 21 = 3*7 = Σv 3 = 2*m <=> Impar = Par ABS => No es posible.

Ejercicio 05.06:

Ejercicio 05.07:

Ejercicio 05.08:


a)
b)

Ejercicio 05.09:

Ejercicio 05.10:


a)
b)
=>) !
<=) Sup G' es f. conexo. Si G' = G listo. Si G != G, Ex. v en G-G'
Como G es conexo, Ex. camino C de v a w (w en G'). Me quedo con el ultimo eje de C.
Ex. v' no en G' / e = (v',w).
Por HI e pertenece a un ciclo => G'U{C} es f. conexo -> G es f.conexo


c)

Ejercicio 05.11:


a)
b)

Ejercicio 05.12:

Ejercicio 05.13:


a)
b)

Ejercicio 05.14:

Ejercicio 05.15:

R es el conj. de grafos tq:

  • Г(v) inc Г(w) o Г(w) inc Г(v) v,w ady
  • Г'(v) inc Г'(w) o Г'(w) inc Г'(v) v,w no ady
OBS: 1. Sean S,T conj. Si |S|=|T| y S inc T o T inc S -> S=T
     2. |Г(v)|=d(v) y |Г'(v)|=d(v)+1
     3. v en Г(w) <=> v,w ady
     4. Sean S,T conj. Si |S|>=|T| y S inc T o T inc S -> T inc s


a)
Sup. no vale prop. -> Ex. u,v,w / d(u)=d(v)=d(w) y u en Г(v) y u no en Г(w)
|Г'(u)| = d(u)+1 = d(v)+1 = |Г'(v)| y 2. ->(1.) Г'(u) = Г'(v) -> v no en Г(w)
|Г(w)| = d(w)+1 = d(u)+1 = |Г(u)| y 1. -> Г(w) = Г(u) -> v en Г(w) ABS
-> Solo pueden ser todos ady o todos no ady.


b)
Sup. no vale prop. -> Todo vertices tiene un ady o un no ady.
Sean v el vertice de mayor grado, w no en Г(v)
|Г(w)|<=|Г(v)| y 1. ->(4). Г(v) inc Г(w)
d(w)>0 -> Ex. z en Г(w) -> z en Г(v)
|Г'(z)| = d(z)+1 <= d(v)+1 = |Г'(v)| y 2. -> Г(z) inc Г(v) -> w en Г(v) ABS

Ejercicio 05.16:


a)
b)
c)
d)

Ejercicio 05.17:

Ejercicio 05.18:

Ejercicio 05.19:


a) Vale por la biyeccion entre V y V'
b) Sup. que |E|>|E'| => existe e en E / e = (v,w) y no existe (f(v),f(w)) ABS
c) Es equivalente a decir que d(v) = d(f(v))
d) Vale por la biyeccion entre circuitos simples entre G y H
e)
f) *-*-*-*-* *-*-*-*-*
* *
g)

Ejercicio 05.20:


a)
b)

Ejercicio 05.21:


a)
b)

Ejercicio 05.22:


a)
b)

Ejercicio 05.23:


a)
b)
c)
d)
e)
f)
g)

Ejercicio 05.24:

Ejercicio 05.25:


a)
b)

Ejercicio 05.26:

Ejercicio 05.27:

Ejercicio 05.28:


a)
b)
c)

Ejercicio 05.29:


a)
b)
c)

Ejercicio 05.30:


a)
b)
c)