Caso real
Los grafos reales son dispersos
La red de carreteras de un país tiene millones de cruces, cada uno con 3 o 4 calles. Una red social, millones de usuarios con cientos de contactos. La web, miles de millones de páginas con decenas de enlaces cada una. En todos, E es del orden de V, no de V². Por eso casi todas las bibliotecas de grafos usan listas de adyacencia o su versión compacta, CSR, el siguiente tema.
Un caso nuevo con la misma forma: una enciclopedia en línea tiene 3 000 000 de páginas y cada una enlaza, en promedio, con unas 25 más. Los enlaces tienen sentido: de la página A a la B no implica de B a A.