Kézfogás-lemma

A matematika, azon belül a gráfelmélet területén a kézfogás-lemma vagy kézfogási lemma az az állítás, hogy minden véges irányítatlan gráf páros darab páratlan fokszámú csúccsal rendelkezik (fokszám: a csúcsból kiinduló élek száma). Egy köznapi életből vett példával, ha egy partin néhány ember kezet fog egymással, a páratlan számú emberrel kezet rázók száma páros.

Ebben a gráfban páros számú csúcsnak (a 2, 4, 5 és 6 jelű csúcsoknak) van páratlan fokszáma. A csúcsok fokszámainak összege 2 + 3 + 2 + 3 + 3 + 1 = 14, ami az élek számának kétszerese

A kézfogás-lemma a (néha szintén kézfogás-lemmának hívott) fokszámösszeg-képlet következménye, miszerint:

$\sum _{v\in V}\deg(v)=2|E|$,

ha a gráf csúcshalmazát V-vel, élhalmazát E-vel jelöljük. Mindkét eredményt Leonhard Euler (1736) igazolta a Königsbergi hidak problémáját vizsgáló híres elemzésében, ami a gráfelmélet megalapozásául szolgált.

A páratlan fokszámú csúcsokat néha egyszerűen „páratlan csúcs”-oknak nevezik; ebben a terminológiában a kézfogáslemma úgy is megfogalmazható, hogy minden gráfnak páros számú páratlan csúcsa van.

Bizonyítás

Euler a fokszámösszeg-képletet a kettős leszámlálás nevű technikával bizonyítja: összeszámolja az érintkező (v,e) párosokat, ahol e egy él és a v csúcs az él valamely végpontja, két különböző módon. A v csúcs deg(v) párba tartozik bele, ahol deg(v) (azaz v fokszáma) a csúccsal érintkező élek száma. Tehát az érintkező párok száma a fokszámok összege. Azonban a gráf minden éle 1-1 végpontja révén pontosan két érintkező párba tartozik, ezért az érintkező párok száma 2|E|. Mivel a két képlet ugyanazt a halmazt számlálja meg, értéküknek azonosnak kell lennie.

Egész számok összegzésekor az összeg párosságát nem befolyásolják a páros tagok; a végösszeg akkor páros, ha páros darab páratlan tag van, és akkor páratlan, ha páratlan darab páratlan tag van. Mivel a fokszámösszeg-képlet egyik oldalán a 2|E| páros szám található, bármely oldalon csak páros számú páratlan tag lehet; ezért csak páros darab páratlan fokszámú csúcs létezhet.

Egy másik bizonyítási módszer lehet a teljes indukció, megmutatva, hogy adott gráfból egy él eltávolításával nem juthatunk páratlan darab páratlan fokszámú csúcsot tartalmazó gráfhoz.

Reguláris gráfok

A fokszámösszegképletből következik, hogy bármely n csúcsú r-reguláris gráf nr/2 éllel rendelkezik. Ha pedig r páratlan szám, akkor az élek számának oszthatónak kell lennie r-rel.

Végtelen gráfok

A kézfogás-lemmának ellentmondó végtelen gráf

A kézfogáslemma nem vonatkozik végtelen gráfokra, még akkor sem, ha csak véges számú páratlan fokszámú csúcsuk van. Például az ábrán látható végtelen útgráf egyetlen páratlan fokszámú csúccsal rendelkezik.

Cseregráfok

A (Cameron & Edmonds 1999) tanulmányban listázott több kombinatorikai struktúráról megmutatható, hogy páros számosságú, egy megfelelő „cseregráf” (exchange graph) páratlan fokszámú csúcsai segítségével.

Például, ahogy azt Cedric Smith bizonyította, bármely G 3-reguláris gráfban páros számú, a fix uv élen keresztülmenő Hamilton-körnek kell lennie; (Thomason 1978) a kézfogáslemma segítségével kiterjesztette a bizonyítást olyan gráfokra, ahol az összes csúcs fokszáma páratlan. A Thomason által definiált H cseregráf csúcsai kölcsönösen megfeleltethetők az eredeti gráf u-ban kezdődő és v-ben folytatódó Hamilton-útjainak. Két ilyen út, p₁ és p₂ akkor vannak H-ban éllel összekötve, ha p₂ megkapható p₁ végéhez egy él hozzáadásával és a közepéből egy másik eltávolításával; ez szimmetrikus reláció, ezért H irányítatlan gráf. Ha a p út a w csúcsban végződik, akkor H-ban p-nek megfelelő csúcs fokszáma éppen a lehetőségek száma, ahogy p kiterjeszthető u-ba vissza nem csatlakozó éllel; tehát H-ban a csúcs fokszáma vagy deg(w) − 1 (ami páros szám), ha p nem alkot Hamilton-kört uv-n keresztül, vagy deg(w) − 2 (ami páratlan szám), ha p része egy uv-n keresztülmenő Hamilton-körnek. Mivel H páros számú páratlan csúccsal rendelkezik, G-nek páros számú uv-n keresztülmenő Hamilton-köre kell legyen.

Számítási bonyolultság

A cseregráf segítségével bizonyítani lehetett egyes kombinatorikai struktúrák létezését, felmerül azonban a kérdés, hogy milyen hatékonysággal találhatók meg ezek a struktúrák. Például, tegyük fel, hogy bemenetként megkapjuk egy 3-reguláris gráf Hamilton-körét; Smith tételéből következik, hogy léteznie kell egy második körnek is. Milyen gyorsan lehet ezt a kört megtalálni? (Papadimitriou 1994) vizsgálta az ilyen jellegű, számítási bonyolultságra vonatkozó kérdéseket, valamint általánosabban vizsgálta, hogy egy nagyméretű, impliciten megadott gráf egy páratlan csúcsát ismerve hogyan található meg egy második páratlan fokszámú csúcs. Meghatározta a PPA, illetve az irányított gráfokra vonatkozó PPAD bonyolultsági osztályokat az ilyen jellegű problémák lefedésére. Ezek fontos szerepet kapnak az algoritmikus játékelmélet területén, mivel a Nash-egyensúly kiszámítása ekvivalens a PPA osztály legnehezebb problémáinak kiszámításával.

Más alkalmazásai

A kézfogáslemmát felhasználják a Sperner-lemma és a hegymászóprobléma lineáris esetének bizonyításához is.

Fordítás

• Ez a szócikk részben vagy egészben a Handshaking lemma című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• Cameron, Kathie & Edmonds, Jack (1999), "Some graphic uses of an even number of odd nodes", Annales de l'Institut Fourier 49 (3): 815–827, doi:10.5802/aif.1694, <http://www.numdam.org/item?id=AIF_1999__49_3_815_0>.
• Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis", Commentarii Academiae Scientiarum Imperialis Petropolitanae 8: 128–140, <http://math.dartmouth.edu/~euler/docs/originals/E053.pdf>. Reprinted and translated in Biggs, N. L.; Lloyd, E. K. & Wilson, R. J. (1976), Graph Theory 1736–1936, Oxford University Press.
• Papadimitriou, Christos H. (1994), "On the complexity of the parity argument and other inefficient proofs of existence", Journal of Computer and System Sciences 48 (3): 498–532, DOI 10.1016/S0022-0000(05)80063-7.
• Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), vol. 3, Annals of Discrete Mathematics, pp. 259–268, DOI 10.1016/S0167-5060(08)70511-9.