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

De Cuba-Wiki
m (Pequeño arreglo de LaTeX)
(No se muestran 37 ediciones intermedias de 13 usuarios)
Línea 1: Línea 1:
__NOTOC__
{{Back|Algoritmos y Estructuras de Datos III}}
==Ejercicio 05.01:==
==Ejercicio 05.01:==
<br>3*n = Σ<sub>v</sub> 3 <= Σ<sub>v</sub> d(v) = 2*m = 2*19 = 38
<math>3*n = \sum_v 3 \leq \sum_v  d(v) = 2*m = 2*19 = 38</math><br>
<br>Entonces n <= 38/3 ∼ 12
Entonces n <= 38/3 ∼ 12<br>


==Ejercicio 05.02:==
==Ejercicio 05.02:==
Línea 23: Línea 26:
<br>Sup. que vale para un digrafo de n-1 vertices. qvq vale para G, si agregamos un vertice w de k ejes de entrada y j de salida. Sabemos que
<br>Sup. que vale para un digrafo de n-1 vertices. qvq vale para G, si agregamos un vertice w de k ejes de entrada y j de salida. Sabemos que
<br>Σ{i=1..n} din(vi) = Σ{i=1..n-1} din(vi) + j + din(w)
<br>Σ{i=1..n} din(vi) = Σ{i=1..n-1} din(vi) + j + din(w)
<br>Σ{i=1..n-1} dout(vi) = Σ{i=1..n-1} dout(vi) + k + dout(w)
<br>Σ{i=1..n} dout(vi) = Σ{i=1..n-1} dout(vi) + k + dout(w)
<br>Entonces
<br>Entonces
<br>Σ{i=1..n} din(vi) = Σ{i=1..n} dout(vi) <=> Σ{i=1..n-1} din(vi) + j + din(w) = Σ{i=1..n-1} dout(vi) + k + dout(w) <=> (Por HI Σ{i=1..n-1} din(vi) = Σ{i=1..n-1} dout(vi)) j + din(w) = k + dout(w) <=> j + k = k + j -> OK
<br>Σ{i=1..n} din(vi) = Σ{i=1..n} dout(vi) <=> Σ{i=1..n-1} din(vi) + j + din(w) = Σ{i=1..n-1} dout(vi) + k + dout(w) <=> (Por HI Σ{i=1..n-1} din(vi) = Σ{i=1..n-1} dout(vi)) j + din(w) = k + dout(w) <=> j + k = k + j -> OK
Línea 32: Línea 35:


==Ejercicio 05.05:==
==Ejercicio 05.05:==
Si esto pasara entonces Σ<sub>v</sub> d(v) = 2*m <=> 21 = 3*7 = Σ<sub>v</sub> 3 = 2*m <=> Impar = Par ABS => No es posible.
¿Es posible que haya un grupo de 7 personas tal que cada persona conozca exactamente otras 3 personas del grupo?
 
Supongamos que <math>\exists G=(V, X)</math>, tal que, <math>|V|=7</math> y <math>|X|=m</math>.
 
Para todo <math>v \in V</math>, <math>d(v) = 3</math>. Entonces, <math>\sum_{i=1}^{7} d(v_i) = \sum_{i=1}^{7} 3 = 21 = 2m \Rightarrow m = \frac{21}{2} \notin \mathbb{N}</math>
 
'''Absurdo!''' m debe ser par.


==Ejercicio 05.06:==
==Ejercicio 05.06:==
Probar que un grafo <math>G=(V,X)</math> es conexo si y sólo si para toda partición de <math>V</math> en dos subconjuntos <math>V_{1}</math> y <math>V_{2}</math>
(<math>V_{1} \ne \emptyset</math>, <math>V_{2} \ne \emptyset</math>, <math>V_{1} \cap V_{2} = \emptyset</math>, <math>V_{1} \cup V_{2} = V</math>)
hay un arco de G que une un punto de <math>V_{1}</math> con uno de <math>V_{2}</math>.
=>) Sup. que no hay arcos de V1 a V2. Sea W1={V1} y W2={V2,..,Vn}. Pero como no hay arco de V1 a V2, entonces no existe camino de V1 a V2. G no es conexo. ABS  
=>) Sup. que no hay arcos de V1 a V2. Sea W1={V1} y W2={V2,..,Vn}. Pero como no hay arco de V1 a V2, entonces no existe camino de V1 a V2. G no es conexo. ABS  


<=) Sup. que no es conexo -> existen 2 vertices vi,vj / no hay camino entre ellos.
<=) Sup. que no es conexo -> existen 2 vertices vi,vj tales que no hay camino entre ellos.
<br>Elegimos W1={vi} U Z1, / Z1 = conj. de vertices alcanzables desde vi.
<br>Elegimos W1={vi} U Z1, / Z1 = conj. de vertices alcanzables desde vi.
<br>Elegimos W2={vj} U Z2 U X, /Z2 = conj. de vertices alcanzables desde vj y X conj. de vertices NO alcanzables desde vi y vj.
<br>Elegimos W2={vj} U Z2 U X, /Z2 = conj. de vertices alcanzables desde vj y X conj. de vertices NO alcanzables desde vi y vj.
Línea 55: Línea 68:
** Si d(v) = 0 -> m(G) = m(G') > (n-1)(n-2)/2. Pero G' no puede tener mas ejes que el grafo completo K(n-1) -> ABS
** Si d(v) = 0 -> m(G) = m(G') > (n-1)(n-2)/2. Pero G' no puede tener mas ejes que el grafo completo K(n-1) -> ABS
*Sup. m(G') <= (n-2)(n-3)/2
*Sup. m(G') <= (n-2)(n-3)/2
**(n-1)(n-2)/2 < m(G) = m(G') + d(v) <= (n-2)(n-3)/2 + d(v) -> d(v) > n-1 -> ABS
**(n-1)(n-2)/2 < m(G) = m(G') + d(v) <= (n-2)(n-3)/2 + d(v) --> n > d(v) > n-2 --> d(v) = n-1 --> G es conexo.


==Ejercicio 05.08:==
==Ejercicio 05.08:==
<br>a) Sup. hay dos caminos C1={vi,wi,..,wn,vf} y C2={vi,xl,..,xm,vf} tq {wi,..,wn}∩{xl,..,xm}={}.
<br>a) Sup. hay dos caminos C1={vi,w1,..,wn,vf} y C2={vi,xl,..,xm,vf} tq {wi,..,wn}∩{xl,..,xm}={}.
Entonces, si se elige otro camino C3 = {vi,wi,..,wn,vf,xm,..,x1,vi} se obtiene un circuito.
Entonces, si se elige otro camino C3 = {vi,w1,..,wn,vf,xm,..,x1,vi} se obtiene un circuito.
<br>b)
<br>b) Se forma un circuito no simple


==Ejercicio 05.09:==
==Ejercicio 05.09:==
Sean G conexo y 2 de los caminos de long. maxima C1 = {vi,vi+1,..,wi+k} y C2 = {wi,wi+1,..,wi+k}. Sup. que no tienen un vertice en comun. Como es conexo, hay un camino de Vi a Vj.
Sean G conexo y 2 de los caminos de long. maxima C1 = {vi,vi+1,..,vi+k} y C2 = {wi,wi+1,..,wi+k}. Sup. que no tienen un vertice en comun. Como es conexo, hay un camino de vi a wj para todo i y j. Tomemos al camino mínimo P de todos los de la forma: P = vi-P'-wj .
* 1. Si vi y vj estan conectados -> ABS (el camino simple de long. maxima seria la union de C1 y C2, que es mas largo que la long. maxima)
 
* 2. Si no estan conectados a traves que no estan en C1 o C2, esos vertices podrian ser agregados a C1 o C2 -> ABS (C1 y C2 ya no tendria long maxima)
Veamos primero que en el "subcamino" P' no puede haber vértices ni de C1 ni C2.
* Supongamos que vl pertenece a P' . Entonces P = vi-P1-vl-P2-wj . Pero entonces el camino vl-P2-wj es más corto que P y es de la forma  vi-P'-wj. Absurdo, ya que P era mínimo dijimos. Entonces P' no puede tener vértices de C1 ni C2 (con un razonamiento análogo se ve para C2).
 
Ahora, sigamos con P. Los siguientes caminos son simples (gracias al resultado anterior), y se ve que alguno de ellos tiene mayor longitud que C1 y C2 (se ve ya que tanto vi como wj están antes o después o en la mitad de C1 y C2, entonces nos quedamos con la parte más larga de C1 y la más larga de C2):
* v1...vi - P' - wj...w1
* v1...vi - P' - wj...wk
* vk...vi - P' - wj...w1
* vk...vi - P' - wj...w1
 
Esto es absurdo, ya que C1 y C2 eran de longitud máxima, y este absurdo provino de suponer que no tenían ningún vértice en común.


==Ejercicio 05.10:==
==Ejercicio 05.10:==
Línea 73: Línea 95:


<br>b)
<br>b)
<br> =>) !
<br> =>)
<br>G orientable de forma que quede fuertemente conexo => todos los nodos tienen grado mayor o igual que 2.
<br>Todo camino que no es ciclo tiene al menos un nodo de grado 1 (extremos) => como no hay nodos de grado 1, G no tiene caminos que no sean ciclos
<br>Por lo tanto, todos los nodos de G pertenecen a un ciclo.
<br> <=) Sup G' es f. conexo. Si G' = G listo. Si G != G, Ex. v en G-G'
<br> <=) Sup G' es f. conexo. Si G' = G listo. Si G != G, Ex. v en G-G'
<br>Como G es conexo, Ex. camino C de v a w (w en G'). Me quedo con el ultimo eje de C.
<br>Como G es conexo, Ex. camino C de v a w (w en G'). Me quedo con el ultimo eje de C.
Línea 79: Línea 104:
<br>Por HI e pertenece a un ciclo => G'U{C} es f. conexo -> G es f.conexo
<br>Por HI e pertenece a un ciclo => G'U{C} es f. conexo -> G es f.conexo


<br>c)
<br>c) Tiene que formar un grafo fuertemente conexo


==Ejercicio 05.11:==
==Ejercicio 05.11:==
Línea 87: Línea 112:
==Ejercicio 05.12:==
==Ejercicio 05.12:==
<br>=>) Si d1,..,dn es una secuencia valida de grados de un grafo -> Σ di = 2*m = par
<br>=>) Si d1,..,dn es una secuencia valida de grados de un grafo -> Σ di = 2*m = par
<br><=) Mm.. esto creo que sale usando el algoritmo que esta en 5.13
<br><=) Como el grafo puede ser pseudografo, tomamos a todos los di pares y haces di/2 loops. Con todos los impares hacemos (di-1)/2 loops y como hay una cantidad par de di impares (pues la suma de todo es par) unimos los di imparers de a pares.


==Ejercicio 05.13:==
==Ejercicio 05.13:==
Línea 101: Línea 126:
</i>
</i>
<br> Usando esto se deberia llegar a que las del ej. no lo son.
<br> Usando esto se deberia llegar a que las del ej. no lo son.
Otra forma seria asi:
<br> (7,6,5,4,3,3,2), si la miramos fijo vemos que n=7 , pero hay un nodo que
<br> tiene 7 ejes y el grado máximo de un nodo (en un grafo simple) es n-1.
<br> (6,6,5,4,3,3,1), en un grafo simple no pueden existir dos nodos con n-1 ejes y un vértice con grado 1, pues todos los nodos son incidentes -al menos- a dos aristas.


<br>b)
<br>b)
Línea 112: Línea 142:
==Ejercicio 05.15:==
==Ejercicio 05.15:==
R es el conj. de grafos tq:
R es el conj. de grafos tq:
* Г(v) inc Г(w) o Г(w) inc Г(v)        v,w ady
* I) Г(v) inc Г(w) o Г(w) inc Г(v)        v,w ady
* Г'(v) inc Г'(w) o Г'(w) inc Г'(v)    v,w no ady
* II) Г'(v) inc Г'(w) o Г'(w) inc Г'(v)    v,w no ady


<pre>
<pre>
Línea 129: Línea 159:


<br>b)
<br>b)
<br>Sup. no vale prop. -> Todo vertices tiene un ady o un no ady.
<br>Sup. no vale la propiedad, entonces: todo vértice tiene un adyacente y uno no ady.
<br>Sean v el vertice de mayor grado, w no en Г(v)
<br>Sean v el vertice de mayor grado, w un vértice no en Г(v)
<br>|Г(w)|<=|Г(v)| y 1. ->(4). Г(v) inc Г(w)
<br>|Г(w)|<=|Г(v)| sumado a (I),  por (4) vale Г(v) inc Г(w)
<br>d(w)>0 -> Ex. z en Г(w) -> z en Г(v)
<br>d(w)>0 --> Existe z en Г(w), luego, z también está en Г(v)
<br>|Г'(z)| = d(z)+1 <= d(v)+1 = |Г'(v)| y 2. -> Г(z) inc Г(v) -> w en Г(v) ABS
<br>|Г'(z)| = d(z)+1 <= d(v)+1 = |Г'(v)| y por (II), --> Г(z) inc Г(v) --> w está en Г(v) ABSURDO. Entonces debe valer la propiedad.


==Ejercicio 05.16:==
==Ejercicio 05.16:==
Línea 142: Línea 172:
==Ejercicio 05.17:==
==Ejercicio 05.17:==
==Ejercicio 05.18:==
==Ejercicio 05.18:==
<br> 1. () 2. Si 3. () 4. Si
<br> 1. No
<br> 2. Si  
<br> 3. ()  
<br> 4. Si


==Ejercicio 05.19:==
==Ejercicio 05.19:==
Línea 154: Línea 187:


==Ejercicio 05.20:==
==Ejercicio 05.20:==
<br>a)
<br>a) No
<br>b)
<br>b) No
 
==Ejercicio 05.21:==
==Ejercicio 05.21:==
<br>a) o-o-o-o
<br>b) Si G es autocomplementario entonces m = n(n-1)/2 - m -> 2m = n(n-1)/2 -> m = n(n-1)/4 (entonces m ≡ 0(4)). Viendo las congruencias modulo 4:
<br> n=4k -> 4k(4k-1)/4 ≡ 0(4)
<br> n=4k+1 -> (4k+1)(4k+1-1)/4 = (4k+1)4k/4 ≡ 0(4)
<br> n=4k+2 -> (4k+2)(4k+2-1)/4 = (4k+2)(4k+1)/4 ≡ 2(4)
<br> n=4k+3 -> (4k+3)(4k+3-1)/4 = (4k+3)(4k+2)/4 ≡ 2(4)
<br> -> Con lo cual solo puede pasar que n=4k o n=4k+1
==Ejercicio 05.22:==
<br>a) o-o-o-o  
<br>a) o-o-o-o  
<br>b) Si G es autocomplementario entonces m = n(n-1)/2 - m -> 2m = n(n-1)/2 -> m = n(n-1)/4 (entonces m ≡ 0(4)). Viendo las congruencias modulo 4:  
<br>b) Si G es autocomplementario entonces m = n(n-1)/2 - m -> 2m = n(n-1)/2 -> m = n(n-1)/4 (entonces m ≡ 0(4)). Viendo las congruencias modulo 4:  
Línea 174: Línea 199:
<br>-> Con lo cual solo puede pasar que n=4k o n=4k+1
<br>-> Con lo cual solo puede pasar que n=4k o n=4k+1


==Ejercicio 05.23:==
==Ejercicio 05.22:==
<br>a)
<br>a)
<pre>
Mat. Adyacencia:
  ABCDEF  ABCDEF
A 011100 A 001100
B 101010 B 100000
C 110111 C 010001
D 101011 D 001001
E 011101 E 011100
F 001110 F 000010
  ABCDEFG  ABCDEFG
A 0111111 A 0110011
B 1000000 B 0000000
C 1001100 C 0000100
D 1010100 D 1010000
E 1011001 E 1001000
F 1000001 F 0000001
G 1000110 G 0000100
</pre>
<br>b)
<br>b)
<br>c)
<br>c)
Línea 182: Línea 228:
<br>f)
<br>f)
<br>g)
<br>g)
==Ejercicio 05.23:==
Si D es el grafo dirigido y G el subyacente, y MD y MG sus respectivas matrices de adyacencia, entonces:
Para todo i,j
MG(i,j) = max(MD(i,j), MD(j,i))
==Ejercicio 05.24:==
==Ejercicio 05.24:==
<br>a) Si se toman como filas/columnas de la matriz de adyacencia de un grafo bipartito a v1,..,vm,w1,..,wn, donde v1,..,vm son los vertices de una particion y w1,..wn los de la otra, entonces la matriz se puede dividir de la siguiente forma:
<pre>
M = [ 0 A ]
    [ B 0 ]
</pre>
<br>b) Como n es impar -> aii^n = cant. de recorridos de long. n desde el vertice vi a si mismo = cant. de circuitos de long. impar que contienen el vertice vi. Con lo cual, si aii^n = 0 para todo i y todo n impar, se esta asegurando que el grafo sea bipartito
==Ejercicio 05.25:==
==Ejercicio 05.25:==
<br>a)
Se puede hacer A^(n-1) y tomar todos los distintos de 0 como 1 (ya que son alcanzables)
<br>b)
 
==Ejercicio 05.26:==
==Ejercicio 05.26:==
Se puede hacer A^(n-1) y tomar todos los distintos de 0 como 1 (ya que son alcanzables)
Si dos grafos son isomorfos, entonces debe existir una forma de intercambiar las filas y luego las columnas de la matriz de adyacencia de uno para que sea igual a la del otro. Como el problema de isomorfismo es NP, no se conoce un buen algoritmo para decidirlo.


==Ejercicio 05.27:==
==Ejercicio 05.27:==
==Ejercicio 05.28:==
<br>a) Usando la prop. de 5.25 b)
<br>a) Usando la prop. de 5.25 b)
<pre>
<pre>
Línea 201: Línea 259:
<br>b)
<br>b)
<pre>
<pre>
for i = 1..n (i impar)
for i = 1..n
for j = 1..n (i impar)
for j = 1..n
invertir A[i,j];
invertir A[i,j];
</pre>
</pre>
Línea 208: Línea 266:
<br>c) a. O(n^4), b. O(n^2)
<br>c) a. O(n^4), b. O(n^2)


==Ejercicio 05.29:==
==Ejercicio 05.28:==
<br>a)
<br>a)
<br>b)
<br>b)
<br>c)
<br>c)
==Ejercicio 05.30:==
==Ejercicio 05.29:==
<br>a)
<br>a)
<br>b)
<br>b)
<br>c)
<br>c)
[[Category: Prácticas]]

Revisión del 01:47 6 may 2018

Plantilla:Back

Ejercicio 05.01:


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:

P(n) = G digrafo de n vertices -> Σ din(v) = Σ dout(v) (todo v en V)

  • CB: n = 1

Σ din(v) = Σ dout(v) <=> 0 = 0 OK

  • PI: P(n-1)->P(n)


Sup. que vale para un digrafo de n-1 vertices. qvq vale para G, si agregamos un vertice w de k ejes de entrada y j de salida. Sabemos que
Σ{i=1..n} din(vi) = Σ{i=1..n-1} din(vi) + j + din(w)
Σ{i=1..n} dout(vi) = Σ{i=1..n-1} dout(vi) + k + dout(w)
Entonces
Σ{i=1..n} din(vi) = Σ{i=1..n} dout(vi) <=> Σ{i=1..n-1} din(vi) + j + din(w) = Σ{i=1..n-1} dout(vi) + k + dout(w) <=> (Por HI Σ{i=1..n-1} din(vi) = Σ{i=1..n-1} dout(vi)) j + din(w) = k + dout(w) <=> j + k = k + j -> OK

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:

¿Es posible que haya un grupo de 7 personas tal que cada persona conozca exactamente otras 3 personas del grupo?

Supongamos que , tal que, y .

Para todo , . Entonces,

Absurdo! m debe ser par.

Ejercicio 05.06:

Probar que un grafo es conexo si y sólo si para toda partición de en dos subconjuntos y (, , , ) hay un arco de G que une un punto de con uno de .

=>) Sup. que no hay arcos de V1 a V2. Sea W1={V1} y W2={V2,..,Vn}. Pero como no hay arco de V1 a V2, entonces no existe camino de V1 a V2. G no es conexo. ABS

<=) Sup. que no es conexo -> existen 2 vertices vi,vj tales que no hay camino entre ellos.
Elegimos W1={vi} U Z1, / Z1 = conj. de vertices alcanzables desde vi.
Elegimos W2={vj} U Z2 U X, /Z2 = conj. de vertices alcanzables desde vj y X conj. de vertices NO alcanzables desde vi y vj.
Si no hay camino entre vi y vj. W1∩W2 = {}. Pero sabemos que debe haber un arco entre W1 y W2, por lo tanto sera desde un vertice alcanzable por vi (o desde vi) hacia uno NO alcanzable, pero entonces habra un camino de vi a vj o a algun vertice de X. ABS

Ejercicio 05.07:


Por induccion en n:

  • CB: n=2

m > (n-1)(n-2)/2 = 0. G es conexo <=> G=K2 -> m = 1 > 0 -> OK

  • PI:

Sea G'= G-v, tq { si m(G') > ((n-1)-1)((n-1)-2)/2 = (n-2)(n-3)/2 -> G' es conexo }. qvq si m(G) > (n-1)(n-2)/2 -> G es conexo

m(G) = m(G')+d(v)

  • Sup. m(G') > (n-2)(n-3)/2
    • Si d(v) > 0 -> v conecta con algun vert. de G' -> Como G' es conexo, G sigue siendo conexo
    • Si d(v) = 0 -> m(G) = m(G') > (n-1)(n-2)/2. Pero G' no puede tener mas ejes que el grafo completo K(n-1) -> ABS
  • Sup. m(G') <= (n-2)(n-3)/2
    • (n-1)(n-2)/2 < m(G) = m(G') + d(v) <= (n-2)(n-3)/2 + d(v) --> n > d(v) > n-2 --> d(v) = n-1 --> G es conexo.

Ejercicio 05.08:


a) Sup. hay dos caminos C1={vi,w1,..,wn,vf} y C2={vi,xl,..,xm,vf} tq {wi,..,wn}∩{xl,..,xm}={}. Entonces, si se elige otro camino C3 = {vi,w1,..,wn,vf,xm,..,x1,vi} se obtiene un circuito.
b) Se forma un circuito no simple

Ejercicio 05.09:

Sean G conexo y 2 de los caminos de long. maxima C1 = {vi,vi+1,..,vi+k} y C2 = {wi,wi+1,..,wi+k}. Sup. que no tienen un vertice en comun. Como es conexo, hay un camino de vi a wj para todo i y j. Tomemos al camino mínimo P de todos los de la forma: P = vi-P'-wj .

Veamos primero que en el "subcamino" P' no puede haber vértices ni de C1 ni C2.

  • Supongamos que vl pertenece a P' . Entonces P = vi-P1-vl-P2-wj . Pero entonces el camino vl-P2-wj es más corto que P y es de la forma vi-P'-wj. Absurdo, ya que P era mínimo dijimos. Entonces P' no puede tener vértices de C1 ni C2 (con un razonamiento análogo se ve para C2).

Ahora, sigamos con P. Los siguientes caminos son simples (gracias al resultado anterior), y se ve que alguno de ellos tiene mayor longitud que C1 y C2 (se ve ya que tanto vi como wj están antes o después o en la mitad de C1 y C2, entonces nos quedamos con la parte más larga de C1 y la más larga de C2):

  • v1...vi - P' - wj...w1
  • v1...vi - P' - wj...wk
  • vk...vi - P' - wj...w1
  • vk...vi - P' - wj...w1

Esto es absurdo, ya que C1 y C2 eran de longitud máxima, y este absurdo provino de suponer que no tenían ningún vértice en común.

Ejercicio 05.10:


a)
Si un digrafo es fuertemente conexo -> se puede ir desde cualquier vertice a otro, lo que es la def. de grafo conexo, por lo que si hay camino orientado entre dos vertices cualquiera tambien habra uno no orientado entre esos vertices.
La reciproca no vale, por ej: o->o<-o. Si bien el grafo subyacente es conexo, no es posible llegar de un vertice cualquiera a otro.


b)
=>)
G orientable de forma que quede fuertemente conexo => todos los nodos tienen grado mayor o igual que 2.
Todo camino que no es ciclo tiene al menos un nodo de grado 1 (extremos) => como no hay nodos de grado 1, G no tiene caminos que no sean ciclos
Por lo tanto, todos los nodos de G pertenecen a un ciclo.
<=) 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) Tiene que formar un grafo fuertemente conexo

Ejercicio 05.11:


a)
b) (Hay que hallar las cliques maximas)

Ejercicio 05.12:


=>) Si d1,..,dn es una secuencia valida de grados de un grafo -> Σ di = 2*m = par
<=) Como el grafo puede ser pseudografo, tomamos a todos los di pares y haces di/2 loops. Con todos los impares hacemos (di-1)/2 loops y como hay una cantidad par de di impares (pues la suma de todo es par) unimos los di imparers de a pares.

Ejercicio 05.13:


a) Esto lo saque de una pagina:
Una secuencia numérica decreciente representa una lista de grados de una gráfica si el siguiente algoritmo devuelve una lista de ceros: (Algoritmo de Havel-Hakimi)

  • P.1 Leer la lista creciente (a1,a2,...,ap).
  • P.2 Mientras el primer elemento sea a1>0
    • P.3 Eliminar el elemento a1 de la lista.
    • P.4 Restar 1 a los primeros a1 elementos de la nueva lista.
    • P.5 Ordenar (decreciente) la nueva lista.
  • P.6 Retornar la lista (a1,a2,...).


Usando esto se deberia llegar a que las del ej. no lo son.

Otra forma seria asi:
(7,6,5,4,3,3,2), si la miramos fijo vemos que n=7 , pero hay un nodo que
tiene 7 ejes y el grado máximo de un nodo (en un grafo simple) es n-1.
(6,6,5,4,3,3,1), en un grafo simple no pueden existir dos nodos con n-1 ejes y un vértice con grado 1, pues todos los nodos son incidentes -al menos- a dos aristas.


b)

Ejercicio 05.14:


Si G tiene m ejes -> Gc tiene n(n-1)/2 - m ejes
Sea V={v1,..,vn} / v1,..,vn-1 tienen grado impar y vn tiene grado par.
Sea vi de grado impar -> dG(vi) = 2k+1. Si dG(vi) = 2k+1 -> dGc(vi) = (n-1)-(2k+1)=n-2-2k
->Si n es impar habra n-1 vertices de grado impar, sino habra 1

Ejercicio 05.15:

R es el conj. de grafos tq:

  • I) Г(v) inc Г(w) o Г(w) inc Г(v) v,w ady
  • II) Г'(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 la propiedad, entonces: todo vértice tiene un adyacente y uno no ady.
Sean v el vertice de mayor grado, w un vértice no en Г(v)
|Г(w)|<=|Г(v)| sumado a (I), por (4) vale Г(v) inc Г(w)
d(w)>0 --> Existe z en Г(w), luego, z también está en Г(v)
|Г'(z)| = d(z)+1 <= d(v)+1 = |Г'(v)| y por (II), --> Г(z) inc Г(v) --> w está en Г(v) ABSURDO. Entonces debe valer la propiedad.

Ejercicio 05.16:


a)
b)
c)
d)

Ejercicio 05.17:

Ejercicio 05.18:


1. No
2. Si
3. ()
4. Si

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) Vale por la biyeccion entre comp. conexas entre G y H
f)
g)

Ejercicio 05.20:


a) No
b) No

Ejercicio 05.21:


a) o-o-o-o
b) Si G es autocomplementario entonces m = n(n-1)/2 - m -> 2m = n(n-1)/2 -> m = n(n-1)/4 (entonces m ≡ 0(4)). Viendo las congruencias modulo 4:
n=4k -> 4k(4k-1)/4 ≡ 0(4)
n=4k+1 -> (4k+1)(4k+1-1)/4 = (4k+1)4k/4 ≡ 0(4)
n=4k+2 -> (4k+2)(4k+2-1)/4 = (4k+2)(4k+1)/4 ≡ 2(4)
n=4k+3 -> (4k+3)(4k+3-1)/4 = (4k+3)(4k+2)/4 ≡ 2(4)
-> Con lo cual solo puede pasar que n=4k o n=4k+1

Ejercicio 05.22:


a)

Mat. Adyacencia:

  ABCDEF   ABCDEF
A 011100 A 001100
B 101010 B 100000 
C 110111 C 010001
D 101011 D 001001
E 011101 E 011100
F 001110 F 000010

  ABCDEFG   ABCDEFG
A 0111111 A 0110011 
B 1000000 B 0000000 
C 1001100 C 0000100
D 1010100 D 1010000
E 1011001 E 1001000
F 1000001 F 0000001
G 1000110 G 0000100


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

Ejercicio 05.23:

Si D es el grafo dirigido y G el subyacente, y MD y MG sus respectivas matrices de adyacencia, entonces: Para todo i,j MG(i,j) = max(MD(i,j), MD(j,i))

Ejercicio 05.24:


a) Si se toman como filas/columnas de la matriz de adyacencia de un grafo bipartito a v1,..,vm,w1,..,wn, donde v1,..,vm son los vertices de una particion y w1,..wn los de la otra, entonces la matriz se puede dividir de la siguiente forma:

M = [ 0 A ]
    [ B 0 ]


b) Como n es impar -> aii^n = cant. de recorridos de long. n desde el vertice vi a si mismo = cant. de circuitos de long. impar que contienen el vertice vi. Con lo cual, si aii^n = 0 para todo i y todo n impar, se esta asegurando que el grafo sea bipartito

Ejercicio 05.25:

Se puede hacer A^(n-1) y tomar todos los distintos de 0 como 1 (ya que son alcanzables)

Ejercicio 05.26:

Si dos grafos son isomorfos, entonces debe existir una forma de intercambiar las filas y luego las columnas de la matriz de adyacencia de uno para que sea igual a la del otro. Como el problema de isomorfismo es NP, no se conoce un buen algoritmo para decidirlo.

Ejercicio 05.27:


a) Usando la prop. de 5.25 b)

for i = 1..n (i impar)
	si (diagonal A^i no es nula)
		devolver falso;
devolver verdadero;


b)

for i = 1..n
	for j = 1..n
		invertir A[i,j];


c) a. O(n^4), b. O(n^2)

Ejercicio 05.28:


a)
b)
c)

Ejercicio 05.29:


a)
b)
c)