Pages: [1]   Go Down
Print
Author Topic: Quesito/i su grafi...  (Read 1115 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Mimmo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 433


We don't need no thought control...


« on: 30-08-2011, 16:43:55 »

Salve a tutti, avrei un quesito:

Siano G1 e G2 due grafi orientati sullo stesso insieme di vertici V. Sia T un ordinamento topologico di G1 che è anche un ordinamento topologico di G2. Quale delle seguenti affermazioni non è vera?

a. Se G3 è il grafo sull'insieme di vertici V, ottenuto unendo gli archi di G1 e gli archi di G2, T è un ordinamento topologico anche per G3.
b. Se G3 è il grafo sull'insieme di vertici V, ottenuto unendo gli archi G1 e gli di G2, allora G3 è aciclico.
c. G1 e G2 sono uguali.
d. Nessuna delle precedenti

Allora...sono indeciso tra a, b e d perché:
Se G1 e G2 sono sullo stesso insieme di vertici ed hanno lo stesso ordinamento topologico (alias i nodi sono collegati nello stesso ordine) allora sono uguali, per cui la c va bene. Ora mi verrebbe da dire che l'unione di due grafi perfettamente identici forma un ciclo, per cui la b è errata, ma è anche vero che non sono sicuro che l'unione di due grafi uguali formi un nuovo grafo con lo stesso ordinamento topologico dei primi due originari...anche se mi verrebbe difficile immaginarlo.

Grazie  
« Last Edit: 30-08-2011, 16:49:32 by Mimmo » Logged

A strange game. The only winning move is not to play. How about a nice game of chess? [Joshua]
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #1 on: 30-08-2011, 17:08:30 »

guarda che quella sbagliata e' proprio la c testate

Grafo                    Ordinamento Topologico
A -> B -> C           ABC

A -> B                   ABC
A -> C

Ora mi verrebbe da dire che l'unione di due grafi perfettamente identici forma un ciclo, per cui la b è errata, ma è anche vero che non sono sicuro che l'unione di due grafi uguali formi un nuovo grafo con lo stesso ordinamento topologico dei primi due originari...anche se mi verrebbe difficile immaginarlo.
Te stai dicendo che unendo gli archi di due grafi uguali ottieni un grafo diverso? Spero tu stia scherzando testate
« Last Edit: 30-08-2011, 17:17:39 by shiny » Logged
Mimmo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 433


We don't need no thought control...


« Reply #2 on: 30-08-2011, 17:12:28 »

ah! 
  sarà bene che mi ripassi un pochetto i grafi... 
Logged

A strange game. The only winning move is not to play. How about a nice game of chess? [Joshua]
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #3 on: 30-08-2011, 18:56:39 »

Ma...in che senso unire gli archi? Non dovrei unire i vertici?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #4 on: 30-08-2011, 21:56:51 »

Ma...in che senso unire gli archi? Non dovrei unire i vertici?
Ma sei serio? hai letto il testo prima di commentare? Forse non avete chiaro cosa significa Unione Insiemistica perche' se A e' un insieme, A\cup A = A, quindi dall'unione di due insiemi uguali non puoi che avere lo stesso insieme ovvero non ha senso sprecare risorse per calcolare cio' che avevamo in input...
« Last Edit: 30-08-2011, 22:00:37 by shiny » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #5 on: 30-08-2011, 22:23:46 »

Quote
quindi dall'unione di due insiemi uguali non puoi che avere lo stesso insieme ovvero non ha senso sprecare risorse per calcolare cio' che avevamo in input...

Peccato che i nostri grafi non siano uguali però. Quindi significa che il grafo G3 è dato dall' unione dei due grafi sostanzialmente, almeno così ho capito.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #6 on: 31-08-2011, 02:28:09 »

Peccato che i nostri grafi non siano uguali però. Quindi significa che il grafo G3 è dato dall' unione dei due grafi sostanzialmente, almeno così ho capito.

Stai cambiando le carte in tavola... Grazie che i due grafi G1=(V,E) e G2=(V,E^\prime) sono diversi (in quanto E\neq E^\prime) ma la tua tesi era quella di unire gli insiemi dei vertici i quali sono uguali (come puoi vedere dalla definizione) da cui, come scritto prima la tua tesi di unire i vertici rispetto agli archi e' insensata (spero di essermi spiegato) 
« Last Edit: 31-08-2011, 02:30:12 by shiny » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #7 on: 31-08-2011, 20:36:07 »

Io intendevo unire i vertici nel senso di collegarli mediante un arco....
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: