I grafi che passione... (ahem)

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
pennywis3
Messaggi: 148
Iscritto il: 01 gen 1970, 01:00
Località: Le fogne

Messaggio da pennywis3 » 01 gen 1970, 01:33

Ed ecco un fantasmagorico problema per tutti voi amanti dei grafi e delle loro simpatiche abitudini.
<BR>
<BR>Dato un grafo che abbia almeno tre spigoli per ogni vertice, dimostrare che contiene almeno un ciclo di lunghezza pari.
<BR>
<BR>
<BR>~p3~
ok, è vero, mangio i bambini, ma d\'altronde sono più teneri.... e poi voi per pasqua non mangiate tutti quei poveri agnellini?

Fede_HistPop
Messaggi: 576
Iscritto il: 01 gen 1970, 01:00
Località: Tuenno, TN
Contatta:

Messaggio da Fede_HistPop » 01 gen 1970, 01:33

Perdona la mia ignoranza, pennywis3, ma che cos\'è un grafo?
Co-founder and leader of Historiae Populorum.
0 A.D. Historian, Game Designer and Scenario Designer; maker of 0 A.D.'s Learning Campaign

Ospite

Messaggio da Ospite » 01 gen 1970, 01:33

va bene se ti rispondo io????spero solo sia giusto!!!!
<BR>
<BR>un grafo e\' formato da due insiemi: un insieme finito e non vuoto di vertici ed un insieme finito ed eventualmente vuoto di lati e/o archi.
<BR>un grafo nn orientato e\' quello in cui la coppia di vertici che rappresentano un lato qualsiasi non e\' ordinata mentre un grafo orientato e\' quello in cui un lato e\' rappresentato da una coppia ordianta di vertici (parliamo di coda e testa del lato)
<BR>
<BR>la definizione potrebbe essere piu complessa ma sinceramente credo che questa sia sufficiente(al max chiedimi o chiedi altre explanations)...fatemi sapere voi altri se c\'e\' qualcosa che nn va qui dentro!!! <IMG SRC="images/forum/icons/icon_confused.gif">
<BR>
<BR>ciaooooooooooooo[addsig]

pennywis3
Messaggi: 148
Iscritto il: 01 gen 1970, 01:00
Località: Le fogne

Messaggio da pennywis3 » 01 gen 1970, 01:33

Sì sì direi che per quel problema basta e avanza.
ok, è vero, mangio i bambini, ma d\'altronde sono più teneri.... e poi voi per pasqua non mangiate tutti quei poveri agnellini?

pennywis3
Messaggi: 148
Iscritto il: 01 gen 1970, 01:00
Località: Le fogne

Messaggio da pennywis3 » 01 gen 1970, 01:33

Sono ostinato UUUUUUP!
ok, è vero, mangio i bambini, ma d\'altronde sono più teneri.... e poi voi per pasqua non mangiate tutti quei poveri agnellini?

pennywis3
Messaggi: 148
Iscritto il: 01 gen 1970, 01:00
Località: Le fogne

Messaggio da pennywis3 » 01 gen 1970, 01:33

Ho sentito dire che chi risolverà questo quesito verrà baciato con la lingua da Nina Moric...
<BR>
<BR>
<BR>Fate vobis...
ok, è vero, mangio i bambini, ma d\'altronde sono più teneri.... e poi voi per pasqua non mangiate tutti quei poveri agnellini?

alberto
Messaggi: 197
Iscritto il: 01 gen 1970, 01:00
Località: milano

Messaggio da alberto » 01 gen 1970, 01:33

prendiamo la catena più lunga del grafo e prendiamo l\'ultimo spigolo VA. prendiamo l\'ultimo vertice (A) della catena. da questo vertice devono uscire almeno altri due spigoli che si congiungono con 2 vertici distinti (B e C) della catena. abbiamo così individuato 3 cicli:
<BR>A_V_......_B_A
<BR>A_B_...._C_A
<BR>A_V_........_C_A
<BR>
<BR>è facile vedere che di questi 3 cicli almeno 1 è pari: l\' ordine di uno dei tre cicli è dato dalla somma degli ordini degli altri due -2

pennywis3
Messaggi: 148
Iscritto il: 01 gen 1970, 01:00
Località: Le fogne

Messaggio da pennywis3 » 01 gen 1970, 01:33

Hmmm se non sbaglio non è detto che da a si dipartano degli archi che poi vadano a ricongiursi alla catena...
ok, è vero, mangio i bambini, ma d\'altronde sono più teneri.... e poi voi per pasqua non mangiate tutti quei poveri agnellini?

alberto
Messaggi: 197
Iscritto il: 01 gen 1970, 01:00
Località: milano

Messaggio da alberto » 01 gen 1970, 01:33

io invece credo di si perchè se per assurdo da A uno degli spigoli (o archi) andasse in X, con X non appartenente alla catena, allora la catena considerata non sarebbe quella massima inquanto la catena che ha tutti gli spigoli della precedente più lo spigolo AX è di uno spigolo più lunga.
<BR>

pennywis3
Messaggi: 148
Iscritto il: 01 gen 1970, 01:00
Località: Le fogne

Messaggio da pennywis3 » 01 gen 1970, 01:33

A quanto pare fraintendo la tua idea di catena. Per me una catena è il percorso di vertici A1_A2_..._An dove A1 e An hanno valenza 1. Altrimenti che senso ha parlare di catena?
<BR>
<BR>Spiegami cosa intendi tu per catena.
<BR>
<BR>(Per il resto la soluzione è uguale alla mia, devi risolvere (secondo me) quel discorso là...)
<BR>
<BR>~p3~
ok, è vero, mangio i bambini, ma d\'altronde sono più teneri.... e poi voi per pasqua non mangiate tutti quei poveri agnellini?

DD
Messaggi: 644
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, talvolta Torino

Messaggio da DD » 01 gen 1970, 01:33

valenza 1 vuol dire che parte 1 solo lato? può darsi che la tua definizione di catena sia quella più corretta, ma se ammetti che gli estremi possano avere valenza diversa da uno, chiamala Minnie anziché catena, la cosa funziona
[img:2sazto6b]http://digilander.iol.it/daniel349/boy_math_md_wht.gif[/img:2sazto6b]

Bloccato