Metraipolis › archive › dc_beeed619273d
Handshake (matematica) — Wikipedia
- Source
- Wikipedia (it)
- Original
- https://it.wikipedia.org/wiki/Handshake_(matematica)
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T13:12:48.941Z
- SHA-256 of the archived text
0c01f764a59f270ebf50f0d67965c8a44e096fd62b01f7902f49fe757699880a- Stable URL of this page
https://metraipolis.com/documento/dc_beeed619273d
How to cite
Handshake (matematica) — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Handshake_(matematica) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_beeed619273d (Metraipolis archive dc_beeed619273d, sha256 0c01f764a59f270ebf50f0d67965c8a44e096fd62b01f7902f49fe757699880a)
BibTeX
@misc{dcbeeed619273d,
title = {Handshake (matematica) — Wikipedia},
howpublished = {Wikipedia (it)},
url = {https://it.wikipedia.org/wiki/Handshake_(matematica)},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_beeed619273d; sha256 0c01f764a59f270ebf50f0d67965c8a44e096fd62b01f7902f49fe757699880a},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Handshake_(matematica). Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Nella teoria dei grafi il lemma di handshaking è l'affermazione che ogni grafo non orientato finito ha un numero pari di vertici con grado dispari (il numero di archi che toccano il vertice). In termini più colloquiali, in un gruppo di persone alcune delle quali si stringono la mano, un numero pari di persone deve aver stretto la mano di un numero dispari di altre persone. I vertici di grado dispari in un grafo sono talvolta chiamati nodi dispari o vertici dispari; in questa terminologia, il lemma di handshaking può essere riformulato come l'affermazione che ogni grafo ha un numero pari di nodi dispari. Il lemma di handshaking è una conseguenza della formula della somma dei gradi (a volte chiamato a sua volta lemma di handshaking), ∑ v ∈ V deg v = 2 | E | {\displaystyle \sum _{v\in V}\deg v=2|E|} per un grafo con insieme di vertici V e archi E. Entrambi i risultati furono provati da Leonhard Euler (1736) nel suo famoso articolo sui sette ponti di Königsberg che iniziò lo studio della teoria dei grafi. Altre applicazioni includono la dimostrazione che per alcune strutture combinatorie, il numero di strutture è sempre pari, e l'assistenza con le prove del lemma di Sperner e del problema del "mountain climbing" (in italiano "alpinismo"). La classe di complessità PPA incapsula la difficoltà di trovare un secondo vertice dispari, dato uno di questi vertici in un grande grafo definito implicitamente.
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»).
Fonte: Wikipedia in italiano, voce «Handshake (matematica)» — https://it.wikipedia.org/wiki/Handshake_(matematica)
Wikidata Q954454: «lemma that every node-link graph has an even number of odd-degree vertices» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q954454
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Handshake_(matematica)?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 144301743, consultata il 2026-10-07T12:43:54.235Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: f28473fb5b9600b0d4c6ab1382305e28661d2c587a1457afd214d16c9cff70f8