Existencia de una matriz simétrica binaria a partir de sumas de filas

Question

Dada una secuencia de sumas de columnas y filas, ¿es posible determinar (por otros medios que no sean la fuerza bruta) si existe una matriz simétrica binaria con las mismas sumas de columnas y filas?

Encontré este artículo, http://www.ams.org/journals/mcom/1987-48-178/S0025-5718-1987-0878703-6/home.html pero mis habilidades matemáticas no son lo suficientemente buenas como para extraer lo que estoy buscando o determinar realmente al 100% que esto es de lo que estoy hablando.

Answer 1

En https://en.wikipedia.org/wiki/Degree_%28graph_theory%29

Hakimi (1962) demostró que $(d_1, d_2, ..., d_n)$ es una secuencia de grados grafo simple si y sólo si $(d_2 − 1, d_3 − 1, ..., d_{d_1+1} − 1, d_{d_1+2}, > d_{d_1+3}, ..., d_n)$ es. Este hecho conduce a un algoritmo simple para encontrar un grafo simple que tenga una secuencia de grados realizable dada:

1) Empezar con un gráfico 2) Mantener una lista de vértices cuyo requisito de grado aún no se ha cumplido en orden no creciente de requisito de grado residual. 3) Conectar el primer vértice con los d1 vértices siguientes de la lista y eliminarlo de ella. Vuelva a ordenar la lista y repita la operación hasta que se cumplan todos requisitos de grado.