Pagina 1 di 1
Inviato: 01 gen 1970, 01:33
da Athos
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">
Inviato: 01 gen 1970, 01:33
da Antimateria
Vorrai dire un grafo ad albero...???
Inviato: 01 gen 1970, 01:33
da Athos
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 ]
Inviato: 01 gen 1970, 01:33
da Antimateria
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.
Inviato: 01 gen 1970, 01:33
da colony
perdonate la somma ignoranza, ma cos\'è un \"grafo\"???
Inviato: 01 gen 1970, 01:33
da Antimateria
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.