Lema lui Sperner
Lema lui Sperner este o teoremă a teoriei graficelor care are aplicații importante în topologie ; în special, permite ceea ce este probabil cea mai elementară dovadă a teoremei punctului fix al lui Brouwer .
Caz unidimensional
Luați în considerare un grafic format dintr-un număr finit de vârfuri aliniate pe un segment și considerați o colorare a vârfurilor cu două culori A și B. Numim un „segment complet” o margine a graficului care are cele două vârfuri colorate cu A și B.
Lema lui Sperner afirmă că
- dacă vârfurile extreme ale graficului au culori diferite, atunci numărul total de segmente complete ale graficului este un număr impar (și, în special, este mai mare sau egal cu 1).
Desenul alăturat ilustrează un exemplu de grafic colorat care satisface ipoteza lemei lui Sperner în care pot fi numărate 5 segmente complete.
Dovada poate fi obținută prin inducție asupra numărului de noduri ale graficului. Numărul minim de noduri este 2 și în cazul a două noduri există un singur segment care este complet deoarece vârfurile sale sunt vârfurile extreme ale graficului. Acum, să presupunem că pentru n- grafice de vârf avem un număr impar de segmente complete. Putem obține un grafic cu n + 1 vârfuri adăugând un vârf pe segmentul unui grafic cu n vârfuri. Posibilitățile sunt următoarele:
- adăugăm un vârf de culoare A între două de culoare A, apoi numărul segmentelor complete rămâne neschimbat
- adăugăm un vârf de culoare B între două de culoare B, este un caz identic cu cel care tocmai a fost analizat
- adăugăm un vârf de culoare A între două de culoare B sau invers, caz în care segmentele complete cresc cu două unități
- adăugăm un vârf de culoare A sau B într-un segment complet, atunci segmentul anterior AB nu mai există și cedează locul a două segmente, unul complet și celălalt nu, prin urmare numărul total de segmente complete rămâne neschimbat. În toate cazurile, dacă a existat un număr impar de segmente complete cu n vârfuri, numărul rămâne impar cu adăugarea unui n + 1 -al vârfului. Aceasta încheie dovada prin inducție.
Caz bidimensional
Să luăm în considerare graficul identificat prin vârfuri și laturi ale unui triunghi T cu o triangulație în interiorul său.
Prin urmare, considerăm o colorare a acestui grafic cu trei culori A, B, C.
Numim un triunghi complet un subgraf compus din trei vârfuri adiacente astfel încât cele trei vârfuri ale sale să fie colorate cu cele trei culori A, B și C.
Lema lui Sperner afirmă că:
- dacă cele trei vârfuri ale triunghiului T au culori diferite (A, B și C) și nodurile grafului care sunt de fiecare parte a lui T au doar una dintre cele două culori ale celor două vârfuri care delimitează acea parte (și, prin urmare, laturile satisfac ipotezele lemei în cazul unidimensional), atunci graficul conține un număr impar de triunghiuri complete (în special conține cel puțin unul).
Demonstrație
Pot fi oferite diferite tipuri de dovezi ale acestei afirmații. O posibilitate este de a lua în considerare graficul dual care are un nod în interiorul fiecărui sub-triunghi și în afara fiecărui segment pe laturi, ca în figură. Apoi se aleg două culori, să spunem R (roșu) și V (verde). Nodurile grafului dual sunt apoi conectate printr-un arc dacă și numai dacă acest arc traversează un segment cu extreme colorate cu R și V (ca în figură).
Acum să analizăm căile identificate de aceste noduri (urmărite în desen cu o cursă mai groasă). Se aplică următoarele proprietăți:
- Aceste căi nu pot avea niciodată bifurcații, deoarece un triunghi nu poate conține mai mult de două laturi cu culorile R și V.
- Între laturile exterioare ale triunghiului putem găsi arcuri ale graficului dual doar pe o parte: cea care avea colorarea cu R și V (ipotetic celelalte două au culoare verde-albastru și roșu-albastru).
- Căile care încep din partea exterioară se pot opri numai în două cazuri: dacă intră în interiorul unui triunghi complet sau dacă ies dintr-o parte externă. De fapt, dacă sunt situate în interior și sunt situate într-un triunghi care nu este complet, atunci trebuie să fie neapărat o altă latură cu culorile R și V.
- Apoi, există câteva căi care rămân mereu în interior: pentru vorbirea care tocmai a fost făcută, aceste căi trebuie să înceapă într-un triunghi complet și să se termine în alt triunghi complet.
Pentru a încheia dovada, ne referim la versiunea unidimensională a lemei: aceasta ne asigură că pe marginea exterioară există un număr impar de segmente RV. Prin urmare - fiind ciudat - nu toate căile care intră prin aceste segmente pot reuși apoi printr-un alt segment RV: trebuie să existe cel puțin o cale care intră dintr-un segment RV al marginii și se termină în interior, în acest caz pentru observațiile făcute mai sus (# 3) trebuie să se termine cu un triunghi complet. Prin urmare, trebuie să existe un triunghi complet. În plus, numărul triunghiurilor complete trebuie să fie impar, deoarece:
- segmentele RV ale muchiei care reușesc de la margine trebuie să fie în număr par, deci un număr impar de segmente avansează care se termină în triunghiuri distincte complete;
- atunci există triunghiuri complete interne din care încep căile care nu părăsesc muchia și în acest caz știm că aceste căi trebuie să se termine pe un alt triunghi complet, deci numărul acestor triunghiuri complete suplimentare este egal și adăugat la cel al completului triunghiurile legate de chenar dau un număr impar.
linkuri externe
- Tăiați nodul , la cut-the-knot.org .
