Handshake (matematica)
Da Wikipedia, l'enciclopedia encyclopedia
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),
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.