Grafo semplice
Da Wikipedia, l'enciclopedia libera.
Si dice grafo semplice un grafo non orientato che non comprende cappi e archi multipli. I grafi semplici sono logicamente equivalenti alle relazioni simmetriche antiriflessive. Quindi la matrice delle adiacenze di un grafo semplice è una matrice binaria simmetrica avente nulle tutte le entrate della diagonale principale. Viceversa ogni matrice di questo tipo rappresenta un grafo semplice.
Di solito per grafo semplice si intende un grafo finito, cioè un grafo che presenta un insieme finito di nodi. Talora possono essere utili anche grafi semplici infiniti.
Gran parte delle teoria dei grafi non orientati riguarda i grafi semplici: infatti per molte proprietà dei grafi la presenza di cappi (o di archi multipli) non ha alcuna influenza. Questo accade ad esempio per proprietà come raggiungibilità, esistenza di cammini hamiltoniani, colorabilità, planarità e connettività dei diversi tipi. All'opposto i problemi riguardanti i cammini euleriani riguardano naturalmente grafi che presentani spigoli multipli. (o digrafi che presentano archi multipli).
Coerentemente quasi tutte le applicazioni dei grafi non orientati ad altre questioni matematiche si servono di grafi semplici. Ad esempio sono grafi semplici i grafi associati ai poliedri. Per la classificazione delle algebre di Lie semisemplici servono invece grafi con spigoli multipli come i diagrammi di Coxeter-Dynkin.
