Práctica 5: Clases de Grafos (Algoritmos III)

Ejercicio 05.01:

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 3*n = \sum_v 3 \leq \sum_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:

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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists G=(V, X)} , tal que, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle |V|=7} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle |X|=m} .

Para todo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v \in V} , Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle d(v) = 3} . Entonces, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \sum_{i=1}^{7} d(v_i) = \sum_{i=1}^{7} 3 = 21 = 2m \Rightarrow m = \frac{21}{2} \notin \mathbb{N}}

Absurdo! m debe ser entero.

Ejercicio 05.06:

Probar que un grafo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G=(V,X)} es conexo si y sólo si para toda partición de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V} en dos subconjuntos Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V_{1}} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V_{2}} (Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V_{1} \ne \emptyset} , Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V_{2} \ne \emptyset} , Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V_{1} \cap V_{2} = \emptyset} , Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V_{1} \cup V_{2} = V} ) hay un arco de G que une un punto de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V_{1}} con uno de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V_{2}} .

=>) 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.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)