kézfogás-lemma

Magyar

Kiejtés

• IPA: [ ˈkeːsfoɡaːʃlɛmːɒ]

Főnév

kézfogás-lemma

1. (matematika, gráfelmélet) 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.

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.

Fordítások

Tartalom

angol: handshaking lemma (en)