<?xml version="1.0" encoding="UTF-8"?>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:wx="http://ilps.science.uva.nl/WikiXML/wx" xml:lang="it" lang="it">
<head>
<title>Lemma di Sperner</title>
<meta name="wx_namespace" content="0"/>
<meta name="wx_pagename" content="Lemma_di_Sperner"/>
<meta name="wx_page_id" content="618762"/>
</head>
<body>
<div id="wx_article">
<wx:section level="1" title="Lemma di Sperner" id="wxsec1"><h1 class="pagetitle" id="wx1">Lemma di Sperner</h1>

<p id="wx2">Il <b id="wx3">lemma di Sperner</b> è un teorema della <a href="/wit/Teoria_dei_grafi" title="Teoria dei grafi" wx:linktype="known" wx:pagename="Teoria_dei_grafi" wx:page_id="25616" id="wx4">teoria dei grafi</a> che ha delle importanti applicazioni in <a href="/wit/Topologia" title="Topologia" wx:linktype="known" wx:pagename="Topologia" wx:page_id="31713" id="wx5">topologia</a>.</p>

<div id="wx_toc"/>

<a id="Caso_unidimensionale" name="Caso_unidimensionale"/>
<wx:section level="2" title="Caso unidimensionale" id="wxsec2"><h2 id="wx6">Caso unidimensionale</h2>

<div class="wx_image" wx:align="right" wx:thumb="thumb" id="wx7"><a href="/wit/Immagine:Sperner1d.svg" title="Grafo colorato con 5 segmenti completi." wx:linktype="image" wx:pagename="Immagine:Sperner1d.svg" id="wx8"><img src="/wit/Immagine:Sperner1d.svg" alt="Grafo colorato con 5 segmenti completi." id="wx9"/></a> 

<div class="thumbcaption" id="wx10">
<p id="wx11">Grafo colorato con 5 segmenti completi.</p>
</div>
</div>

<p id="wx12">Si consideri un <a href="/wit/Grafo" title="Grafo" wx:linktype="known" wx:pagename="Grafo" wx:page_id="651611" id="wx13">grafo</a> costituito da un numero finito di vertici allineati su un segmento, e consideriamo una <a href="/wit/Grafo_colorato" class="new" title="Grafo colorato" wx:linktype="unknown" wx:pagename="Grafo_colorato" id="wx14">colorazione</a> dei vertici con due colori A e B. Chiamiamo "segmento completo" uno spigolo del grafo che abbia i due vertici colorati con A e B.</p>

<p id="wx15">Il lemma di Sperner stabilisce che</p>

<dl id="wx16">
<dd id="wx17"><i id="wx18">se i vertici estremi del grafo hanno colori differenti allora il numero totale di segmenti completi del grafo è un numero dispari (e in particolare è maggiore o uguale a 1).</i></dd>
</dl>

<p id="wx19">Nel disegno a fianco è illustrato un esempio di grafo colorato che soddisfa le ipotesi del lemma di Sperner in cui si possono contare 5 segmenti completi.</p>

<p id="wx20">La dimostrazione si può ottenere per <a href="/wit/Principio_di_induzione" title="Principio di induzione" wx:linktype="known" wx:pagename="Principio_di_induzione" wx:page_id="1314971" id="wx21">induzione</a> sul numero di nodi del grafo. Il numero minimo di nodi è 2 e nel caso di due nodi c'è un solo segmento che è completo perché i suoi vertici sono i vertici estremi del grafo. Ora supponiamo che per i grafi di <i id="wx22">n</i> vertici si abbia un numero dispari di segmenti completi. Un grafo di <i id="wx23">n+1</i> vertici lo possiamo ottenere aggiungendo in un vertice sul segmento di un grafo di <i id="wx24">n</i> vertici. Le possibilità sono le seguenti:</p>

<ol id="wx25">
<li id="wx26">
<p id="wx27">aggiungiamo un vertice di colore A tra due di colore A, allora il numero di segmenti completi rimane inalterato</p>
</li>

<li id="wx28">
<p id="wx29">aggiungiamo un vertice di colore B tra due di colore B, è un caso identico a quello appena analizzato</p>
</li>

<li id="wx30">
<p id="wx31">aggiungiamo un vertice di colore A tra due di colore B o viceversa, in tal caso i segmenti completi aumentano di due unità</p>
</li>

<li id="wx32">
<p id="wx33">aggiungiamo un vertice di colore A o B in un segmento completo, allora il segmento AB precedente non c'è più e lascia il posto a due segmenti di cui uno completo e l'altro no, dunque il numero totale dis egmenti completi rimane inalterato. In tutti i casi se si aveva un numero dispari di segmenti completi con <i id="wx34">n</i> vertici il numero rimane dispari anche con l'aggiunta di un <i id="wx35">n+1</i>-esimo vertice. Questo conclude la dimostrazione per induzione.</p>
</li>
</ol>

<a id="Caso_bidimensionale" name="Caso_bidimensionale"/>
</wx:section><wx:section level="2" title="Caso bidimensionale" id="wxsec3"><h2 id="wx36">Caso bidimensionale</h2>

<div class="wx_image" wx:thumb="thumb" id="wx37"><a href="/wit/Immagine:Sperner2d.svg" title="Grafo colorato che soddisfa le ipotesi del lemma di Sperner, in grigio sono evidenziati i triangoli completi" wx:linktype="image" wx:pagename="Immagine:Sperner2d.svg" id="wx38"><img src="/wit/Immagine:Sperner2d.svg" alt="Grafo colorato che soddisfa le ipotesi del lemma di Sperner, in grigio sono evidenziati i triangoli completi" width="400" id="wx39"/></a> 

<div class="thumbcaption" id="wx40">
<p id="wx41">Grafo colorato che soddisfa le ipotesi del <i id="wx42">lemma di Sperner</i>, in grigio sono evidenziati i triangoli completi</p>
</div>
</div>

<p id="wx43">Consideriamo il <a href="/wit/Grafo" title="Grafo" wx:linktype="known" wx:pagename="Grafo" wx:page_id="651611" id="wx44">grafo</a> individuato da vertici e lati di un <a href="/wit/Triangolo" title="Triangolo" wx:linktype="known" wx:pagename="Triangolo" wx:page_id="54610" id="wx45">triangolo</a> T con al suo interno una <a href="/wit/Triangolazione_%28matematica%29" title="Triangolazione (matematica)" wx:linktype="known" wx:pagename="Triangolazione_(matematica)" wx:page_id="619006" id="wx46">triangolazione</a>.</p>

<p id="wx47">Consideriamo quindi una colorazione di questo grafo con tre colori A,B,C.</p>

<p id="wx48">Chiamiamo <i id="wx49">triangolo completo</i> un sottografo composto da tre vertici adiacenti tale che i suoi tre vertici siano colorati con i tre colori A, B e C.</p>

<p id="wx50">Il <i id="wx51">lemma di Sperner</i> afferma che:</p>

<dl id="wx52">
<dd id="wx53"><i id="wx54">se i tre vertici del triangolo T hanno colori differenti (A, B e C) e i nodi del grafo che si trovano su ciascun lato di T hanno soltanto uno dei due colori dei due vertici che delimitano quel lato (e dunque i lati soddisfano le ipotesi del lemma nel caso unidimensioanle), allora il grafo contiene un numero dispari di triangoli completi (in particolare ne contiene almeno uno).</i></dd>
</dl>

<a id="Dimostrazione" name="Dimostrazione"/>
<wx:section level="3" title="Dimostrazione" id="wxsec5"><h3 id="wx55">Dimostrazione</h3>

<p id="wx56">Si possono dare diversi tipi di dimostrazioni di questo enunciato. Una possibilità è quella di considerare il <a href="/wit/Grafo_duale" title="Grafo duale" wx:linktype="known" wx:pagename="Grafo_duale" wx:page_id="89165" id="wx57">grafo duale</a> che ha un nodo dentro ciascun sotto-triangolo e all'esterno di cascun segmento sui lati, come in figura. Poi si scelgono due colori, diciamo R (rosso) e V (verde). I nodi del grafico duale vengono poi collegati da un arco se e solo se questo arco attraversa un segmento con estremi colorati con R e V (come in figura).</p>

<div class="wx_image" wx:align="center" id="wx58"><a href="/wit/Immagine:Spernerproof.svg" title="" wx:linktype="image" wx:pagename="Immagine:Spernerproof.svg" id="wx59"><img src="/wit/Immagine:Spernerproof.svg" alt="" id="wx60"/></a></div>

<p id="wx61">Ora analizziamo i cammini individuati da questi nodi (tracciati nel disegno con un tratto più spesso). Osserviamo innanzitutto che questi cammini non possono mai avere biforcazioni poiché un triangolo non può contenere più di due lati con colori R e V. Fra i lati esterni del triangolo possiamo trovare archi del grafo duale solamente su un lato: quello che aveva la colorazione con R e V. I cammini che partono dal lato esterno possono fermarsi solo in due casi: se entrano dentro un triangolo completo o se escono da un lato esterno: infatti se si trovano all'interno e si trovano in un triangolo non completo allora deve necessariamente esserci un altro lato con colori R e V. Ci sono poi dei cammini che rimangono sempre all'interno: per il discorso appena fatto questi cammini devono iniziare dentro un triangolo completo e concludersi dentro un altro triangolo completo.</p>

<p id="wx62">Per concludere la dimostrazione ci rifacciamo alla versione unidimensionale del lemma: questa ci assicura che sul bordo esterno ci sono un numero dispari di segmenti completi RV. Dunque non tutti i cammini che entrano possono poi riuscire: deve esserci almeno un cammino che finisce all'interno e in tal caso deve finire in un triangolo completo. Dunque deve esistere un triangolo completo. Il numero di triangoli completi inoltre deve essere dispari perché i segmenti RV del bordo che riescono dal bordo devono essere in numero pari, dunque avanza un numero dispari di segmenti che finisce in triangoli completi distinti. Ci sono poi triangoli completi interni da cui partono cammini che <i id="wx63">non</i> escono dal bordo. In tal caso sappiamo che tali cammini devono finire su un altro triangolo completo, quindi il numero di questi triangoli completi addizionali è pari e sommato a quello dei triangoli completi collegati con il bordo da un numero dispari.</p>

<a id="Collegamenti_esterni" name="Collegamenti_esterni"/>
</wx:section></wx:section><wx:section level="2" title="Collegamenti esterni" id="wxsec4"><h2 id="wx64">Collegamenti esterni</h2>

<ul id="wx65">
<li id="wx66"><a href="http://www.cut-the-knot.org/Curriculum/Geometry/SpernerLemma.shtml" class="external text" wx:linktype="external" rel="nofollow" id="wx67">Cut the knot</a></li>
</ul>

<p id="wx68"><br id="wx69"/>
</p>

<wx:template id="wx_t1" pagename="Template:Portale" page_id="949487"/>
<div style="margin-left:0; margin-right:0" id="wx70">
<ul style="display:block; clear:both; list-style-image:none; list-style-type:none; width:100%; vertical-align:middle; margin:0; margin-bottom:1em; padding:0; min-height:27px" id="wx71">
<li style="float:left; height:27px; line-height:25px; width:100%; margin:0; margin-top:.5em; margin-left:0; margin-right:0; padding:0; border:1px solid #CCF; background-color:#F0EEFF" title="Accedi alle voci di Wikipedia che parlano di matematica" id="wx72"><a href="/wit/Immagine:Stub_matematica.png" title="matematica" wx:linktype="image" wx:pagename="Immagine:Stub_matematica.png" wx:page_id="627197" id="wx73"><img src="/wit/Immagine:Stub_matematica.png" alt="matematica" width="25" height="25" id="wx74"/></a> <b id="wx75"><a href="/wit/Portale:matematica" class="new" title="Portale:matematica" wx:linktype="unknown" wx:pagename="Portale:matematica" id="wx76">Portale Matematica</a></b>
<p id="wx77">:  accedi alle voci di Wikipedia che parlano di matematica</p>
</li>
</ul>
</div>

<wx:templateend start="wx_t1"/>
</wx:section></wx:section></div>
<div id="wx_categorylinks">
<a href="/wit/index.php?title=Speciale:Categories&amp;article=Lemma_di_Sperner" title="Speciale:Categories" wx:linktype="known" wx:pagename="Speciale:Categories" id="wx78">Categorie</a>: <span dir="ltr" id="wx79"><a href="/wit/Categoria:Teoria_dei_grafi" title="Categoria:Teoria dei grafi" wx:linktype="known" wx:pagename="Categoria:Teoria_dei_grafi" wx:page_id="37864" id="wx80">Teoria dei grafi</a></span> | <span dir="ltr" id="wx81"><a href="/wit/Categoria:Topologia" title="Categoria:Topologia" wx:linktype="known" wx:pagename="Categoria:Topologia" wx:page_id="42675" id="wx82">Topologia</a></span></div>
<div id="wx_languagelinks">
Altre lingue: <a href="http://en.wikipedia.org/wiki/Sperner%27s_lemma" class="external" wx:linktype="interwiki" wx:pagename="en:Sperner's_lemma" id="wx83">English</a> | <a href="http://hu.wikipedia.org/wiki/Sperner-lemma" class="external" wx:linktype="interwiki" wx:pagename="hu:Sperner-lemma" id="wx84">Magyar</a> | <a href="http://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%A8%D0%BF%D0%B5%D1%80%D0%BD%D0%B5%D1%80%D0%B0" class="external" wx:linktype="interwiki" wx:pagename="ru:Лемма_Шпернера" id="wx85">Русский</a></div>
</body>
<wx:templatearguments for="wx_t1"><wx:argument name="1">
<p id="wx86">matematica</p>
</wx:argument></wx:templatearguments>
</html>
