I grafi che passione... (ahem)
Moderatore: tutor
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~
<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?
-
- Messaggi: 576
- Iscritto il: 01 gen 1970, 01:00
- Località: Tuenno, TN
- Contatta:
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]
<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]
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
<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
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~
<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?
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]