Metraipolis › archive › dc_aff18cf1956c

Grafo semplice — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Grafo_semplice
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T14:48:35.596Z
SHA-256 of the archived text
a44ca9fa573c7c7dad888239ee791489e7e3e3adbc4172ddd87eab55ee593546
Stable URL of this page
https://metraipolis.com/documento/dc_aff18cf1956c

How to cite

Grafo semplice — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Grafo_semplice (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_aff18cf1956c (Metraipolis archive dc_aff18cf1956c, sha256 a44ca9fa573c7c7dad888239ee791489e7e3e3adbc4172ddd87eab55ee593546)
BibTeX
@misc{dcaff18cf1956c,
  title = {Grafo semplice — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Grafo_semplice},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_aff18cf1956c; sha256 a44ca9fa573c7c7dad888239ee791489e7e3e3adbc4172ddd87eab55ee593546},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Grafo_semplice. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Si dice grafo semplice un grafo non diretto 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.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»).
Fonte: Wikipedia in italiano, voce «Grafo semplice» — https://it.wikipedia.org/wiki/Grafo_semplice
Wikidata Q3774204 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q3774204
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Grafo_semplice?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 149121728, consultata il 2026-10-07T14:21:40.993Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 5eaacbf49278c526da3fca92aefd1ef33f20a682945e4865cc123e8efa792868