| Autor |
Mensaje |
loonatic
Nivel 9
Edad: 32
Registrado: 16 May 2009
Mensajes: 1256
Carrera: Sistemas
|
|
Hola, estoy resolviendo el integrador que está acá, y tengo algunas dudas.
"Si un grafo tiene exactamente 2 vértices de grado impar, hay una trayectoria que une a esos dos vértices."
Lo que único que puedo decir sobre el grafo es que tiene un camino de Euler, pero qué más?
"El número máximo de aristas de un grafo no conexo simple con ![[tex]n[/tex]](images/latex/8c7447db63092942e0a39cfe01d3d94174a89707_0.png "[tex]n[/tex]") vertices y ![[tex]k[/tex]](images/latex/de61dde472a066a5b90a2ff0be7a2f756110011b_0.png "[tex]k[/tex]") componentes es ![[tex] (n-k) \frac{n-k+1}{2} [/tex]](images/latex/2cfe6c06c6329d00d7e092439efd83443113b501_0.png "[tex] (n-k) \frac{n-k+1}{2} [/tex]")
Este ni idea.
Y despues, el 4) 2) que pide demostrar el teorema que dice:
"Si T es un arbol binario completo con ![[tex]i[/tex]](images/latex/a4c1c5aa2403f597f891e4ee97abe072c60a5117_0.png "[tex]i[/tex]") vértices internos, entonces tiene ![[tex]i+1[/tex]](images/latex/8e28030acbbc1aaa5f8d9c581ac275a5771a395b_0.png "[tex]i+1[/tex]") hojas y ![[tex]2i+1[/tex]](images/latex/c55db851e7f2edc9c733db0e129d5d10e31bb7f3_0.png "[tex]2i+1[/tex]") vértices."
En este quise usar inducción pero llego a un resultado incorrecto... me puse a hacer dibujos con i =1,2,3 y me da que se cumple, pero creo que con eso no basta... alguna idea?
Gracias
|
|
|
|
|
|
   |
     |
|
loonatic
Nivel 9
Edad: 32
Registrado: 16 May 2009
Mensajes: 1256
Carrera: Sistemas
|
|
| Tengo otra duda con ese coloquio, el ultimo ejercicio da un grafo y pide definir y hallar el arbol generador minimo, como se hace eso?? Si solo se puede hacer para grafos ponderados :s ¿Está mal el enunciado?
|
|
|
|
|
|
| |
|
|
Rick_
Nivel 7
Registrado: 02 Mar 2010
Mensajes: 308
Ubicación: Balvanera
Carrera: Informática y Sistemas
|
|
puede ser q el enunciado este mal, ó durante el coloquio escribieron en el pizarron los pesos. de ultima hacelo con peso 1 en todas las aristas
para el primero, se cumple q es un grafo de euler (camino), y eso significa q hay un camino (de euler) q recorre todas las aristas y vertices, entonces en especial une v0 y w0, los vertices de grado impar. pero me suena a q sale de otra forma.
de las otras 2 no tengo ni idea de como hacerlos (q suerte q no tomaron eso en el coloquio de hoy).
concentrate mas en las demostraciones de { arbol } implica {aciclico y si le sacas una arista deja de ser conexo} , esas 7 implicaciones de arboles. como bien predijo la profe, hoy hubo dos de esos. y acordate las definiciones de flujo, red, etc
|
|
|
|
|
|
 |
|
|
ezeperez26
Nivel 3
Edad: 34
Registrado: 11 Jul 2008
Mensajes: 43
Carrera: Informática
|
|
| Cita:
|
Y despues, el 4) 2) que pide demostrar el teorema que dice:
"Si T es un arbol binario completo con vértices internos, entonces tiene hojas y vértices."
|
Si el árbol es binario COMPLETO, significa que cada vértice (que no sea hoja) tiene 2 vértices hijos. Por lo tanto, teniendo vértices internos (incluye al vértice raíz) se lo multiplica por 2, que es la cantidad de hijos que posee cada vértice. Y se le suma 1 para incluir el vértice raíz que no aparece en el producto anterior. De ahí resulta que en total hay hojas.
Ahora, el total de vértices del árbol es ![[tex]|V| = i + h[/tex]](images/latex/b21cc412fbf8ae59a6ee692de710475f7eb7f1d4_0.png "[tex]|V| = i + h[/tex]") con ![[tex]h:cantidad de hojas[/tex]](images/latex/ef2ccacd6272ebd6018356ece1ca561a1133b70b_0.png "[tex]h:cantidad de hojas[/tex]") . Por lo tanto, la cantidad de hojas del árbol completo es ![[tex]h = |V| - i[/tex]](images/latex/91434c79bcd618c4c5bceb6c4d4972463a6622b3_0.png "[tex]h = |V| - i[/tex]") .
La ecuación de la cantidad de hojas que mostraste vos está mal.
|
|
|
|
_________________
Pampa
|
|
  |
|
|
loonatic
Nivel 9
Edad: 32
Registrado: 16 May 2009
Mensajes: 1256
Carrera: Sistemas
|
|
| ezeperez26 escribió:
|
| Cita:
|
Y despues, el 4) 2) que pide demostrar el teorema que dice:
"Si T es un arbol binario completo con vértices internos, entonces tiene hojas y vértices."
|
Si el árbol es binario COMPLETO, significa que cada vértice (que no sea hoja) tiene 2 vértices hijos. Por lo tanto, teniendo vértices internos (incluye al vértice raíz) se lo multiplica por 2, que es la cantidad de hijos que posee cada vértice. Y se le suma 1 para incluir el vértice raíz que no aparece en el producto anterior. De ahí resulta que en total hay hojas.
|
Que?? Eso ultimo que pusiste está mal...si tengo un arbol con 1 raiz y 2 hojas, hay 3 vértices, no 3 hojas.
| Cita:
|
|
Ahora, el total de vértices del árbol es con . Por lo tanto, la cantidad de hojas del árbol completo es .
|
Eso si está bien, y es bastante logico, porque un vértice puede ser interno u hoja, más opciones no hay.
|
|
|
|
|
|
| |
|
|
ezeperez26
Nivel 3
Edad: 34
Registrado: 11 Jul 2008
Mensajes: 43
Carrera: Informática
|
|
| Cita:
|
| Cita:
|
| Cita:
|
Y despues, el 4) 2) que pide demostrar el teorema que dice:
"Si T es un arbol binario completo con vértices internos, entonces tiene hojas y vértices."
|
Si el árbol es binario COMPLETO, significa que cada vértice (que no sea hoja) tiene 2 vértices hijos. Por lo tanto, teniendo vértices internos (incluye al vértice raíz) se lo multiplica por 2, que es la cantidad de hijos que posee cada vértice. Y se le suma 1 para incluir el vértice raíz que no aparece en el producto anterior. De ahí resulta que en total hay hojas.
|
Que?? Eso ultimo que pusiste está mal...si tengo un arbol con 1 raiz y 2 hojas, hay 3 vértices, no 3 hojas.
|
A ver si nos entendemos, la ecuación ![[tex] 2.i + 1 [/tex]](images/latex/e811079709fdbd40536b7466ea1d92ab770aa498_0.png "[tex] 2.i + 1 [/tex]") es para calcular la cantidad total de vértices, es decir, la ecuación debería ser ![[tex]|V| = 2.i + 1 [/tex]](images/latex/0739e06e1fa99e026540c4d478a6e55b5ac70d73_0.png "[tex]|V| = 2.i + 1 [/tex]") .
Si querés calcular la cantidad de hojas utilizas la ecuación .
Si reemplazo |V| por la ecuación te queda una ecuación de la cantidad de hojas en función de los vértices internos que posee quedando ![[tex]h = 2.i + 1 - i = i + 1[/tex]](images/latex/a37de8e29a741383e0dfbb1aa50a19d6bb7464ea_0.png "[tex]h = 2.i + 1 - i = i + 1[/tex]") .
Ahora que me doy cuenta, llegue a lo mismo que vos planteaste en el principio, operando con todos los artilugios matemáticos...
Este procedimiento creo que nos sirvió a ambos.. Espero que ahora te ayude y te quede mas claro. Cualquier cosa avisame!
|
|
|
|
_________________
Pampa
|
|
| |
|
|
emiliano3112
Nivel 0
Registrado: 10 Ene 2012
Mensajes: 1
|
|
| |
|
|
xsfr-nmbt
Nivel 3
Registrado: 02 Feb 2012
Mensajes: 42
Carrera: Informática
|
|
Yo si sin saber la demostración de:
El número máximo de aristas de un grafo no conexo simple con vertices y componentes es
Parece díficil, supongo que sale usando las propiedades de los grafos kn, porque cada componente conexa sería un grafo kn.
"Si un grafo tiene exactamente 2 vértices de grado impar, hay una trayectoria que une a esos dos vértices."
¿Estaría mal demostrarlo así?
1) Caso 1: no hay ninguna arista. Pero entonces el grado de los vértices es 0 (no es impar)
2) Caso 2: hay aristas.
La arista debe incidir en al menos un vértice, tiene dos posibilidades:
* Incide en el otro vértice (Entonces hay una trayectoria)
* Incide dos veces en el mismo vértice (lazo)
Pero si hay lazo, el grado pasa a ser par. Por lo tanto, no queda otra opción que formar una trayectoria con la arista.
|
|
|
|
|
|
| |
|
|
csebas
Nivel 9
Edad: 71
Registrado: 16 Feb 2009
Mensajes: 1634
Carrera: No especificada
|
|
el 1 anda a una clase de consulta y si queres exigile a alquien que te lo explique, yo nunca lo saque.
el 2 no te marees, 2 de grado impar, euler , existe 1 camino...... Tan simple como dijeron arriba.
|
|
|
|
_________________
━━━━━┓ ＼＼
┓┓┓┓┓┃
┓┓┓┓┓┃ ヽ○ノ
┓┓┓┓┓┃ /
┓┓┓┓┓┃ ノ)
┓┓┓┓┓┃
┓┓┓┓┓┃
▒▒▒▒▒▒▒▒▒▒▒▒▒▒
|
|
  |
 |
|
xsfr-nmbt
Nivel 3
Registrado: 02 Feb 2012
Mensajes: 42
Carrera: Informática
|
|
OK, gracias por lo del punto 2.
Ambas demostraciones son del final del 20/07/2010, que tiene un par de cosas raras...
Por ejemplo, en el punto 4:
1) Dice ![[tex]f: V\rightarrow{} V'[/tex]](images/latex/f65288e122418dce8ca2940298e48bf4b43725ef_0.png "[tex]f: V\rightarrow{} V'[/tex]") y ![[tex]f^{-1} : V\rightarrow{} V'[/tex]](images/latex/5955afbb856f667afc07e1e70b3c28c075dcaa39_0.png "[tex]f^{-1} : V\rightarrow{} V'[/tex]") Y no puede ser ... Tiene que ser ![[tex]f^{-1} : V'\rightarrow{} V[/tex]](images/latex/c39fd06e1e30f08cda4fe3524e4f22cf2811d9c0_0.png "[tex]f^{-1} : V'\rightarrow{} V[/tex]")
2) Pide demostrar algo sobre un árbol binario completo con 25 vértices, pero 25 vértices es imposible si es completo. Porque ![[tex]n=2^{h+1}-1[/tex]](images/latex/754dee023df877efaad34e4ef1d5887c51458aff_0.png "[tex]n=2^{h+1}-1[/tex]") donde n es el número de vértices y h la altura, pero no hay h entero que cumpla eso con n=25.
|
|
|
|
|
|
| |
|
|
marinon87
Nivel 1
Registrado: 20 Oct 2007
Mensajes: 2
|
|
| xsfr-nmbt escribió:
|
OK, gracias por lo del punto 2.
2) Pide demostrar algo sobre un árbol binario completo con 25 vértices, pero 25 vértices es imposible si es completo. Porque donde n es el número de vértices y h la altura, pero no hay h entero que cumpla eso con n=25.
|
Completo no significa equilibrado
|
|
|
|
|
|
| |
|
|
pinus
Nivel 4
Edad: 36
Registrado: 20 Ene 2009
Mensajes: 100
Carrera: Informática, Sistemas y
|
|
| ezeperez26 escribió:
|
| Cita:
|
Y despues, el 4) 2) que pide demostrar el teorema que dice:
"Si T es un arbol binario completo con vértices internos, entonces tiene hojas y vértices."
|
Si el árbol es binario COMPLETO, significa que cada vértice (que no sea hoja) tiene 2 vértices hijos. Por lo tanto, teniendo vértices internos (incluye al vértice raíz) se lo multiplica por 2, que es la cantidad de hijos que posee cada vértice. Y se le suma 1 para incluir el vértice raíz que no aparece en el producto anterior. De ahí resulta que en total hay hojas.
Ahora, el total de vértices del árbol es con . Por lo tanto, la cantidad de hojas del árbol completo es .
La ecuación de la cantidad de hojas que mostraste vos está mal.
|
En el grimaldi este resultado esta enunciado en forma similar ... pero no me parece correcto que primero el enunciado diga que i es la cantidad de vertices internos y despues para que se cumpla la formula dentro de los vertices internos hay que considerar la raiz.
La formula seria |v| = 2i + 3
|
|
|
|
|
|
  |
|
|
pinus
Nivel 4
Edad: 36
Registrado: 20 Ene 2009
Mensajes: 100
Carrera: Informática, Sistemas y
|
|
Sobre esta propiedad:
"Si un grafo tiene exactamente 2 vértices de grado impar, hay una trayectoria que une a esos dos vértices."
En ningún lugar se aclara que el grafo sea conexo, por ende no es valida ninguna demostración que implique usar que se trata de un grafo de euler.
Mas aún sospecho que este resultado es independiente de que el grafo sea o no conexo. Creo que tiene que ver mas con el hecho de que la cantidad de vertices de grado impar en cualquier grafo es siempre par, por ende un grafo tendra o ningún vertice de grado impar o por lo menos dos vertices de grado impar.
|
|
|
|
|
|
| |
|
|
pinus
Nivel 4
Edad: 36
Registrado: 20 Ene 2009
Mensajes: 100
Carrera: Informática, Sistemas y
|
|
| Además si se asume que es conexo, no tiene sentido el enunciado. Lo engañoso es que nos hace recordar una de las condiciones necesarias (pero no suficientes) para que tenga camino de euler (faltaria que ademas sea conexo).
|
|
|
|
|
|
| |
|
|
MarianAAAJ
Nivel 7
Edad: 35
Registrado: 14 Ene 2009
Mensajes: 437
Carrera: Informática
|
|
| loonatic escribió:
|
"El número máximo de aristas de un grafo no conexo simple con vertices y componentes es "
|
Lo acabo de resolver.
Para que sea máximo el número de aristas, tiene q tratarse de k subgrafos donde uno de ellos es completos, y el resto tendrán solo un vértice.
Por lo que el grado de k-1 vértices será cero, ya que dichos vértices perteneces a subgrafos con un solo vértice.
El número de vértices que pertenecen al subgrafo que es completo será de ![[tex]n- k + 1[/tex]](images/latex/f5cddd4a9337e67ab3da596539ee33530042ea03_0.png "[tex]n- k + 1[/tex]") (Número de vértices que pertenecen al subgrafo q es completo); mientras q el grado de cada uno de ellos será de ![[tex]n- k + 1 - 1 = n - k[/tex]](images/latex/7b1d496bd0c7c83e1f7d2e648806da4499e73774_0.png "[tex]n- k + 1 - 1 = n - k[/tex]") (por ser grafo completo).
|
|
|
|
|
|
 |
|
|
|
|
Ir a página 1, 2 Siguiente
|
Ver tema siguiente
Ver tema anterior
Podés publicar nuevos temas en este foro
No podés responder a temas en este foro
No podés editar tus mensajes en este foro
No podés borrar tus mensajes en este foro
No podés votar en encuestas en este foro
No Podéspostear archivos en este foro
No Podés bajar archivos de este foro
|
Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker365 Attacks blocked.
|
