grafo

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
Athos
Messaggi: 22
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da Athos » 01 gen 1970, 01:33

dimostrare ke un grafo con n nodi possiede (n-1) lati
<BR>(come al solito,è preferito l\'uso dell\'induzione) <IMG SRC="images/forum/icons/icon_smile.gif">

Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria » 01 gen 1970, 01:33

Vorrai dire un grafo ad albero...???

Athos
Messaggi: 22
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da Athos » 01 gen 1970, 01:33

come vuoi tu <IMG SRC="images/forum/icons/icon_biggrin.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif">
<BR>
<BR>
<BR>cmq c sono grafi ke hanno nulla a ke vedere con gli alberi!<BR><BR>[ Questo Messaggio è stato Modificato da: Athos il 02-06-2004 19:00 ]

Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria » 01 gen 1970, 01:33

Eh, ok, ma quel risultato non vale mica per tutti i grafi!
<BR>
<BR>Lo dimostro per i grafi ad albero, per induzione.
<BR>Un grafo si dice ad albero se è connesso e non ha cicli. Se ha un nodo, non può avere archi (o lati, che dir si voglia), quindi ok. Se l\'albero ha n>1 nodi, ha almeno una foglia (ovvero un nodo con esattamente un arco), altrimenti sarebbe ciclico o sarebbe sconnesso. Togliamo questa foglia e l\'arco che la unisce al resto dell\'albero, ed otteniamo un nuovo albero con n-1 nodi (infatti è ancora connesso ed aciclico). Per ipotesi induttiva questo albero ha n-2 archi, dunque quello di partenza ne aveva n-1.

colony
Messaggi: 33
Iscritto il: 01 gen 1970, 01:00

Messaggio da colony » 01 gen 1970, 01:33

perdonate la somma ignoranza, ma cos\'è un \"grafo\"???

Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria » 01 gen 1970, 01:33

Un grafo è una coppia (N,A)...
<BR>Ok, scherzo. E\' un insieme finito di palline (nodi) che possono essere unite con degli archi. Ogni arco può unire un nodo con qualunque <!-- BBCode Start --><B>altro</B><!-- BBCode End --> nodo. Ogni coppia di nodi può avere al massimo un arco che li unisce. Un arco non può unire un nodo con sè stesso.
<BR>Un grafo è connesso se da ogni nodo puoi raggiungerne ogni altro passando attraverso gli archi. Un ciclo in un grafo è un percorso che parte da un nodo e ritorna in quel nodo passando attraverso qualche arco, e senza ripercorrere 2 volte lo stesso arco.

Bloccato