| Autor |
Mensaje |
Joaquin7
Nivel 3
Edad: 33
Registrado: 08 Ago 2008
Mensajes: 37
Ubicación: capital
|
|
Tenia un par de dudas cuando practicaba los coloquios:
Un grafo de Euler puede repetir vertices?
Cuando piden determinar m y n de K_mn (de un G bipartito completo) para que tenga un camino y circuito de Euler..como se piensa, porq no veo q restricciones tiene que tener (como no pide q sea G de Euler puede no usar todos los vertices ni aristas)
Que son los niveles en G? solo los conozco en digrafos. Y como se clasifican con la matriz de incidencia.
Como se demuestra que en un G existe un par de vertices de igual grado?
En el algoritmo de Ford para digrafos ponderados, cuando se 'pasa' a otra vuelta??
|
|
|
|
|
|
   |
     |
|
Freddy
Nivel 8
Edad: 34
Registrado: 29 Oct 2008
Mensajes: 630
Ubicación: Lanús
Carrera: Sistemas
|
|
| Joaquin7 escribió:
|
|
Un grafo de Euler puede repetir vertices?
|
Si
| Cita:
|
|
Cuando piden determinar m y n de K_mn (de un G bipartito completo) para que tenga un camino y circuito de Euler..como se piensa, porq no veo q restricciones tiene que tener (como no pide q sea G de Euler puede no usar todos los vertices ni aristas)
|
En cualquier grafo, un camino de Euler existe si y solo si existen dos vertices de grado impar y el resto es de grado par.
Y existe un circuito de Euler si y solo si todos los vertices tienen grado par.
| Cita:
|
|
Que son los niveles en G? solo los conozco en digrafos. Y como se clasifican con la matriz de incidencia.
|
Es en digrafos solamente, sino no tiene sentido redibujar un grafo porque la arista puede transportar cosas en ambas direcciones.
Un conjunto de vertices k esta en un nivel superior a un conjunto de vertices j si ningun vertice de k puede ser alcanzado por ningun vertice de j.
Para nivelar un digrafo, agarra la matriz de adyacencia y anda mirando las columnas. El/los primeros vertices que tengan todo 0 en las columnas, los eliminas de la matriz (tanto su fila como su columna) y vas repitiendo ese proceso hasta que no te quede nada adentro.
| Cita:
|
|
En el algoritmo de Ford para digrafos ponderados, cuando se 'pasa' a otra vuelta??
|
Una vez que el flujo llega al vertice sumidero, empezas a deshacer el camino y con ese valor de flujo "actualizas" los flujos de las aristas que intervinieron en el camino. Despues volves y elegis otro camino.
El algoritmo termina cuando no podes seguir aumentando el flujo de las aristas que alcanzan al vertice sumidero.
|
|
|
|
|
|
  |
 |
|
Joaquin7
Nivel 3
Edad: 33
Registrado: 08 Ago 2008
Mensajes: 37
Ubicación: capital
|
|
Gracias Freddy.
El camino/circuito de Euler tiene q pasar por todos los vertices?
En un ej de final pedian los niveles de un grafo y daban la matriz de incidencia y no tenia columnas ni filas nulas... Lo q me dijiste de col nulas no es para matrices de adyacencia?
La duda acerca del algoritmo de Ford era para digrafos solamente (no redes con flujo). Porq para redes si se que hay q seguir estrictamente un camino, pero en digrafos dice ¨mientras exista una arista q cumpla tal cosa seguir etiquetando¨
|
|
|
|
|
|
| |
|
|
|
|
|
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.
|
|
|
[ Tiempo: 0.3495s ][ Pedidos: 20 (0.2514s) ] |
