Cambalache 3,14 - La vidriera irrespetuosa

Me ofrezco como evaluador adjunto O:-)

pregunta off-topic: Zifra, nunca he dado teoría de grafos... ¿para qué sirven las matrices de adyacencia e incidencia además de para meter los grafos en el ordenador y para calcular caminos de cierta longitud? No pensabe meter esto en las opos, pero ya que estoy... :P

Bueno, la matriz de adyacencia simplifica la demostración del lema de las encajadas:

2|A|=Sum_{vin V}{delta(v)}

y hay otras aplicaciones similares, aunque la mayoría son algoritmos de conexión, planaridad, enrutado,... ¿quieres apuntes?

saludos

no, gracias, sólo quería ver para qué servían... a nivel primero de carrera, para poner algo en ese tema (tema 2), queda bien eso de poner aplicaciones informáticas de lo que se ve en teoría. Pensaba que servían para algo más brutal, en plan... te demuestra ipso facto que el grafo es lalala viendo el elemento (bla,bli) de la matriz lelele... pero vamos, que tiene más sentido que sea una forma de meter los grafos en el ordenador, ya bastante hace con lo de los caminos.

Tiene gracia que en las opos no tengas que poner lo que se espera, sino lo que nadie pone. Hay que aprovechar que hay plazas a mansalva...

Y volviendo al post: por suerte los libros no son como la música y siempre nos quedará el encanto de poner un separapáginas :P

Bueno Ani,j te proporciona el número de caminos de longitud n entre los vértices i y j. Hay más propiedades de estas.

¡Vaya, no funcionan los tags!

A^n_{i,j}, donde A es la matriz de adyacencia

si, si, eso sí lo sabía... ok, con esto tengo más que de sobra. Total, el tribunal no tendrá ni idea de estas cosas...

(esto acabará convirtiéndose en un post de grafos...)

Hola; a ver, alguna cosilla más:
Si todos los elementos de la fila i son ceros alguno de la columna i no lo es, el vértice es un sumidero y si es a la inversa es fuente.
Si la matriz es simétrica, el grafo es no dirigido.
La implementación del algoritmo de Warshall es trivial si el grafo está representado mediante la matriz de adyacencias.
Si tenemos un grafo ponderado representado mediante la matriz de costes, las implementaciones de los algoritmos de Floyd (caminos más cortos de todos a todos) y de Dijkstra (caminos más cortos de uno a todos) son casi triviales, y de orden O(n^3) y O(n^2), respectivamente.

jajaja, Carlos A.

En tu especialidad, un grafo es, por defecto, dirigido. En la mía, por defecto, es simple (no dirigido y sin bucles)

¡Cáspita! (qué antiguo suena eso :) es cierto; incluso digo en clase que nuestros grafos son "distintos" a nuestros compis matématicos (ya sabes que soy un renegado :-)

Cuando queremos representar un no dirigido lo más sencillo es hacerlo mediante un dirigido con una arista en cada sentido.

Luego no hay fuentes, ni sumideros, todas las matrices son simétricas, etc.

Retiro el 50% de lo dicho, Lola

No retires, no... sigue siendo cierto :-)

Creo que lo de las consolas no está bien. Hay unas que son las "Nintendo DS". Eso de PS no me suena.

Está mal. De hecho, ya hay un imac G5 en mi casa y una nintendo(gs) DS. El esmárfono es del año de la pera y ya no lo uso y ando loco por un tablet.

ok, perfecto, pero creo que con lo otro ya me vale (bueno, lo de las filas de ceros y tal, no considero grafos con vértices aislados). Ya está estudiado y re-estudiado el tema, la verdad es que queda completito, con Euler, los mosaicos, su kuratowsky, árboles... Ojalá me caiga, me acordaré de vosotros durante el esxamen! :P

Oye, dais clases particulares por Internés? Necesito guía-instructor(a) que me ilumine el camino y me quite las telarañas. Contraprestación negociable.

Ah, para que no me den por la derriere los spammers os dejo mi correo en hex:
%67%61%72%6e%61%63%68%6f%40%77%61%6e%61%64%6f%6f%2e%6e%6c.
Saludos