Reproducción de un gráfico mediante una matriz de incidencia

Question

Soy muy nuevo en la teoría de grafos. De hecho, sólo he empezado a estudiar el tema hace tres días. Así que, por favor, ¡tengan piedad si esta es una pregunta sin sentido!

Mientras estudiaba los isomorfismos de los grafos, se me ocurrió que una persona debería ser capaz de tomar una matriz de incidencia y reproducir a partir de esa matriz un grafo que -aunque quizás no sea el original- sea isomorfo al grafo original. ¿Es esto cierto? Si es así, ¿hay alguna buena prueba?

Answer 1

Un grafo está determinado (hasta el isomorfismo) por la lista de vértices y la lista de aristas. La matriz de incidencia es simplemente una forma de codificar la lista de vértices y aristas. Como el grafo se define por los vértices que son adyacentes, y la matriz de incidencia es una forma de presentar las adyacencias, se puede reproducir el grafo a partir de la matriz de adyacencia.