<?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>Multigrafo euleriano</title>
<meta name="wx_namespace" content="0"/>
<meta name="wx_pagename" content="Multigrafo_euleriano"/>
<meta name="wx_page_id" content="90876"/>
</head>
<body>
<div id="wx_article">
<wx:section level="1" title="Multigrafo euleriano" id="wxsec1"><h1 class="pagetitle" id="wx1">Multigrafo euleriano</h1>

<p id="wx2">In <a href="/wit/Teoria_dei_grafi" title="Teoria dei grafi" wx:linktype="known" wx:pagename="Teoria_dei_grafi" wx:page_id="25616" id="wx3">teoria dei grafi</a> si dice <b id="wx4">multigrafo euleriano</b> un <a href="/wit/Multigrafo" title="Multigrafo" wx:linktype="known" wx:pagename="Multigrafo" wx:page_id="89672" id="wx5">multigrafo</a> connesso, privo di cappi e dotato di un <a href="/wit/Cammino_euleriano" title="Cammino euleriano" wx:linktype="known" wx:pagename="Cammino_euleriano" wx:page_id="90853" id="wx6">cammino euleriano</a>, cioè di un cammino che tocca tutti i suoi spigoli una e una sola volta.</p>

<p id="wx7">Si pone il problema di stabilire se un multigrafo possiede un cammino euleriano o meno. Questo problema può risolversi piuttosto agevolmente attraverso un algoritmo individuato da <a href="/wit/Eulero" title="Eulero" wx:linktype="known" wx:pagename="Eulero" wx:page_id="2584" id="wx8">Eulero</a> (v. <a href="/wit/Problema_dei_ponti_di_K%C3%B6nigsberg" title="Problema dei ponti di Königsberg" wx:linktype="known" wx:pagename="Problema_dei_ponti_di_Königsberg" wx:page_id="90589" id="wx9">Problema dei ponti di Königsberg</a>) che è in grado per ogni multigrafo di costruire rapidamente tale cammino se esiste e di segnalare la sua inesistenza in caso contrario.</p>

<p id="wx10">Ricordiamo preliminarmente che un qualsiasi multigrafo possiede un numero pari di vertici di grado dispari. Infatti la somma dei gradi di tutti i vertici del multigrafo deve essere un numero uguale al doppio del numero degli spigoli, e quindi un numero pari.</p>

<p id="wx11">Conviene allora distinguere tre tipi di multigrafi connessi: quelli aventi tutti i vertici di grado pari, quelli aventi due vertici di grado dispari e quelli con più di due vertici di grado dispari. Questa distinzione si può effettuare con una semplice ispezione degli spigoli. Si dimostra che i primi sono dotati di un circuito euleriano, i secondi posseggono un cammino euleriano ma non un circuito euleriano, i terzi non sono multigrafi euleriani.</p>

<p id="wx12"><b id="wx13">Algoritmo</b> Consideriamo un multigrafo connesso qualsiasi M; se questo non possiede vertici di grado dispari, allora costruisce un suo circuito euleriano; se M possiede esattamente due nodi di grado dispari, allora individua un cammino euleriano che li collega; se possiede quattro o più vertici dispari, allora segnala che non è un multigrafo euleriano.</p>

<p id="wx14"><b id="wx15">Procedimento</b></p>

<p id="wx16">Se M possiede un nodo dispari si inizia da quello; in caso contrario si può iniziare da un qualsiasi nodo.</p>

<p id="wx17">Si procede a una prima fase di costuizione di un cammino euleriano aggiungendo via via nuovi spigoli e segnando quelli che risultano utilizzati. Questa manovra si può concludere con l'esaurimento di tutti gli spigoli. Nel primo caso si deve terminare il cammino nel vertice di partenza, nel secondo nel secondo vertice di grado dispari, nel terzo caso la cosa è impossibile.</p>

<p id="wx18">Se rimangono altri spigoli ci cerca di ampliare il cammino a partire da un vertice rimasto con un numero pari di spigoli non utilizzati. Questo è possibile per i grafi dei primi due tipi i quali potranno essere effettivamente ampliati fino ad esaurire i loro spigoli ed a giungere al vertice di partenza o al vertice rimasto di grado dispari. Non può invece proseguire indefinitamente nel terzo caso. Ogni ampliamento del cammino lascia tutti i vertici con grado rimanente pari nei primi due casi e lo stesso numero di vertici di grado dispari nel terzo.</p>

<p id="wx19"><i id="wx20"><b id="wx21">QED</b></i></p>

<a id="Voci_correlate" name="Voci_correlate"/>
<wx:section level="2" title="Voci correlate" id="wxsec2"><h2 id="wx22">Voci correlate</h2>

<ul id="wx23">
<li id="wx24"><a href="/wit/Multidigrafo_euleriano" title="Multidigrafo euleriano" wx:linktype="known" wx:pagename="Multidigrafo_euleriano" wx:page_id="91002" id="wx25">Multidigrafo euleriano</a></li>
</ul>

<p id="wx26"><br id="wx27"/>
</p>

<wx:template id="wx_t1" pagename="Template:Portale" page_id="949487"/>
<div style="margin-left:0; margin-right:0" id="wx28">
<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="wx29">
<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="wx30"><a href="/wit/Immagine:Stub_matematica.png" title="matematica" wx:linktype="image" wx:pagename="Immagine:Stub_matematica.png" wx:page_id="627197" id="wx31"><img src="/wit/Immagine:Stub_matematica.png" alt="matematica" width="25" height="25" id="wx32"/></a> <b id="wx33"><a href="/wit/Portale:matematica" class="new" title="Portale:matematica" wx:linktype="unknown" wx:pagename="Portale:matematica" id="wx34">Portale Matematica</a></b>
<p id="wx35">:  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=Multigrafo_euleriano" title="Speciale:Categories" wx:linktype="known" wx:pagename="Speciale:Categories" id="wx36">Categorie</a>: <span dir="ltr" id="wx37"><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="wx38">Teoria dei grafi</a></span> | <span dir="ltr" id="wx39"><a href="/wit/Categoria:Algoritmi" title="Categoria:Algoritmi" wx:linktype="known" wx:pagename="Categoria:Algoritmi" wx:page_id="42921" id="wx40">Algoritmi</a></span></div>
<div id="wx_languagelinks">
</div>
</body>
<wx:templatearguments for="wx_t1"><wx:argument name="1">
<p id="wx41">matematica</p>
</wx:argument></wx:templatearguments>
</html>
