Matriz de incidencia de un grafo y su homología

Muchas veces cuando se da un curso de Teoría de Grafos se introduce el concepto de matriz de incidencia, una matriz cuyas filas representan las aristas del grafo y cuyas columnas representan los vértices, de tal modo que la posición $(i,j)$ de la matriz es un $1$ si la arista $i$ es incidente a vértice $j$, y un $0$ si no lo es. Existe una generalización más o menos natural de esta matriz para grafos dirigidos: la matriz de incidencia dirigida, que en la posición $(i,j)$ tiene un $1$ si la arista $i$ "sale" del vértice $j$, un $-1$ si la arista $i$ "entra" al vértice $j$, y un $0$ si la arista $i$ no es incidente a vértice $j$.

Dataset: Menéame

Me he bajado Menéame para un proyecto de minería de datos y pongo aquí el dataset que tanto esfuerzo me ha costado conseguir por si alguien lo quiere. El formato de los datos es texto plano. Consiste en 53.088 filas, cada una de ellas conteniendo información de una noticia publicada en la portada de Menéame entre septiembre de 2010 y hoy. Por algún motivo he tenido problemas para parsear las noticias más antiguas, así que hasta esa fecha he podido llegar. Contiene algunos fallos, pero son despreciables dado el volumen de datos.

La primera fila contiene los nombres de las columnas. A partir de la segunda, cada fila contiene 7 campos separados por la secuencia de caracteres ' ;; ' (espacio, punto y coma, punto y coma, espacio). Los campos son

1. Cabecera de la entrada (titular) [texto]
2. Entradilla [texto]
3. Número de meneos de la noticia [entero]
4. Número de clics de la noticia [entero]
5. Url de la noticia en Menéame [texto]
6. Url de la página a la que dirige la noticia [texto]
7. Nombre del usuario que publicó la noticia [texto]

El dataset se puede descargar aquí:

http://netkups.com/?d=5c60398812ce3

P, NP, NP-completo: aclaración para profanos

A mucha gente le suena el problema P vs. NP porque ha salido en Futurama, porque ha salido en Los Simpson, o porque ha leído algo sobre ello en una entrada de Menéame. Como todo concepto científico más o menos avanzado que se hace popular, mucha gente lo ha entendido mal y va por ahí diciendo burradas como que NP significa No Polinomial, y cosas así. Aunque entender con algo de profundidad el problema requeriría un curso entero dedicado a ello, sí que creo que se puede intentar explicar el asunto de manera rápida, sin reparar en las sutilezas pero también sin llevar a engaños.