Kézfogás-lemma

gráfelméleti állítás

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:

,

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 szerkeszté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 szerkesztés

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

Végtelen gráfok szerkesztés

 
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 szerkesztés

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, p1 és p2 akkor vannak H-ban éllel összekötve, ha p2 megkapható p1 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 szerkesztés

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.[2]

Más alkalmazásai szerkesztés

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.

Jegyzetek szerkesztés

  1. Aldous, Joan M. & Wilson, Robin J. (2000), "Theorem 2.2", Graphs and Applications: an Introductory Approach, Undergraduate Mathematics Series, The Open University, Springer-Verlag, p. 44, ISBN 978-1-85233-259-4
  2. Chen, Xi & Deng, Xiaotie (2006), "Settling the complexity of two-player Nash equilibrium", Proc. 47th Symp. Foundations of Computer Science, pp. 261–271, ECCC: Weizmann Institute of Science, DOI 10.1109/FOCS.2006.69

Fordítás szerkeszté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 szerkesztés