3. Sea G un grafo de n vértices. (a) Demostrar que G puede obtenerse a partir del grafo trivial repitiendo n− 1 veces el siguiente paso: 1 p. agre...

Question

3. Sea G un grafo de n vértices. (a) Demostrar que G puede obtenerse a partir del grafo trivial repitiendo n− 1 veces el siguiente paso: 1 p. agregar un vértice y cierta cantidad de ejes (eventualmente ninguno) incidentes al vértice agregado. (b) Demostrar que si G es un árbol, lo dicho puede lograrse aún exigiendo que al final de cada paso se 1 p. obtenga un árbol. SUGERENCIA: Inducción en n.

Ed IA de Studenta · Answer

a)Sea G un grafo de n vértices. Podemos demostrar que G puede obtenerse a partir del grafo trivial repitiendo n−1 veces el siguiente paso:Agregar un vértice y cierta cantidad de ejes (eventualmente ninguno) incidentes al vértice agregado.La base de la inducción es el caso n=1. El grafo trivial tiene un solo vértice, por lo que el grafo trivial es el grafo trivial.La hipótesis de inducción es que para cualquier número natural k, si G es un grafo de k vértices, entonces G puede obtenerse a partir del grafo trivial repitiendo k−1 veces el paso anterior.Para el paso inductivo, supongamos que G es un grafo de n vértices. Entonces podemos agregar un vértice v a G y conectarlo a cualquier número de vértices de G. El grafo resultante G′ tiene n+1 vértices y es un árbol. Esto se debe a que G es un árbol, por lo que no tiene ciclos. Cuando agregamos v a G, no creamos ningún ciclo, porque solo conectamos v a vértices que ya están en G.Por lo tanto, por inducción, si G es un grafo de n vértices, entonces G puede obtenerse a partir del grafo trivial repitiendo n−1 veces el paso anterior.b)Ahora demostramos que si G es un árbol, lo dicho puede lograrse aún exigiendo que al final de cada paso se obtenga un árbol.La base de la inducción es el caso n=1. El grafo trivial es un árbol, por lo que el grafo trivial es un árbol.La hipótesis de inducción es que para cualquier número natural k, si G es un árbol de k vértices, entonces G puede obtenerse a partir del grafo trivial repitiendo k−1 veces el paso anterior, de modo que al final de cada paso se obtiene un árbol.Para el paso inductivo, supongamos que G es un árbol de n vértices. Entonces podemos agregar un vértice v a G y conectarlo a cualquier número de vértices de G. El grafo resultante G′ tiene n+1 vértices y es un árbol. Esto se debe a que G es un árbol, por lo que no tiene ciclos. Cuando agregamos v a G, no creamos ningún ciclo, porque solo conectamos v a vértices que ya están en G.Por lo tanto, por inducción, si G es un árbol de n vértices, entonces G puede obtenerse a partir del grafo trivial repitiendo n−1 veces el paso anterior, de modo que al final de cada paso se obtiene un árbol.

3. Sea G un grafo de n vértices. (a) Demostrar que G puede obtenerse a partir del grafo trivial repitiendo n− 1 veces el siguiente paso: 1 p. agre...

Computacional

Outros

Esta pregunta también está en el material:

2014-12-12

Computacional • Universidad Nacional de CórdobaUniversidad Nacional de Córdoba

💡 1 Respuesta

✏️ Responder

Otros materiales

Preguntas relacionadas

4. Sea G un grafo o digrafo en el cual cada eje e tiene asociada una longitud no necesariamente positiva ℓ(e) ∈ R. Dada una función f : R → R, def...

Decimos que un grafo pesado G es un árbol enredado si existe un ciclo C de 3 vértices tal que G− E(C) (i.e., el grafo que resulta de sacarle a G la...

Ayuda: Utilizar el hecho de que 3-coloreo es NP-Completo y elegir un k que, conociendo el tamaño n de un grafo arbitrario G, permita armar un grafo...

5. Dado un grafo H con pesos asociados a sus ejes, un árbol generador quasi-mı́nimo de H es un árbol generador de H que tiene peso mı́nimo entre ...

Materiales relacionados

Otros materiales