I grafi che passione... (ahem)

[pennywis3]

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~

[Fede_HistPop]

Perdona la mia ignoranza, pennywis3, ma che cos\'è un grafo?

[Ospite]

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]

Sì sì direi che per quel problema basta e avanza.

[pennywis3]

Sono ostinato UUUUUUP!

[pennywis3]

Ho sentito dire che chi risolverà questo quesito verrà baciato con la lingua da Nina Moric...
<BR>
<BR>
<BR>Fate vobis...

[alberto]

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]

Hmmm se non sbaglio non è detto che da a si dipartano degli archi che poi vadano a ricongiursi alla catena...

[alberto]

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]

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~

[DD]

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