Pages: [1] 2   Go Down
Print
Author Topic: Domanda su grafi  (Read 1855 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« on: 24-09-2011, 16:11:07 »

Sia G un grafo orientato e connesso. Supponiamo che esista un arco che se rimosso disconnette il grafo. Sia il grafo con matrice di adiacenza. Qual è la complessita del migliore algoritmo possib ile per trovare tale arco?

Io ho fatto il seguente ragionamento:  trovo un arco che abbia degree out = 1 e degree in = 0. In tal modo eliminando l'unico arco di quel nodo ho disconnesso il grafo.
Ma per trovare un nodo che abbia degree out =0 e degree in =1 devo scorrere la mia matrice e tale operazione mi costa O(|V|^2). Quindi secondo me la risposta è O(|V|^2).

(Mentre se avessi avuto il grafo con liste di adiacenza potevo trovare il nodo con degree in = 0 e degree out=1 in tempo O(V+E).)

Voi che cosa avreste risposto? E se il grafo fosse non orientato?
« Last Edit: 24-09-2011, 16:33:32 by flashato90 » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #1 on: 24-09-2011, 19:23:14 »

Il grafo può essere anche con cicli? Secondo me....se non contiene cicli si perde la connessione rimuovendo un qualunque arco, ma potrei sbagliarmi...
« Last Edit: 24-09-2011, 19:28:02 by Daréios89 » Logged

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

Posts: 57



« Reply #2 on: 24-09-2011, 22:31:28 »

Come fa un grafo orientato e connesso (quindi fortemente connesso?) a non contenere cicli?
Un grafo e' connesso se presi due vertici qualsiasi esiste un cammino che li unisce.
Se il grafo e' orientato e presi due vertici qualsiasi esiste un cammino che li unisce allora si dice fortemente connesso.

flashato90, secondo me non esiste un VERTICE che abbia IN-degree 0 oppure OUT-degree 0 in un grafo fortemente connesso, altrimenti non potresti giungere in quel vertice da nessun altro, oppure uscire per raggiungerne un'altro.

A quel punto la mia personale idea sull'algoritmo sarebbe quella di TROVARE il vertice che abbia IN-degree OPPURE OUT-degree = 1. E l'arco associato a tale vertice, che sia entrante o uscente, e' quello da rimuovere per disconnettere il grafo. Temo sia necessario esaminare tutta la matrice.

Se il grafo fosse stato non orientato non credo che il problema sarebbe cambiato molto. Invece di IN-degree o OUT-degree si sarebbe parlato semplicemente di degree.

Spero (tanto) di non sbagliarmi Smiley
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #3 on: 24-09-2011, 23:44:25 »

Quote
Come fa un grafo orientato e connesso (quindi fortemente connesso?) a non contenere cicli?

Avevo pensato a questo:


                                   V_1---->v_2
                                                 |
                                                 |
                                                \ /
                                   V_4<---V_3

Solo che in questo caso non dovrebbe essere connesso perchè deve esistere un cammino che permetta di andare da w a v e da v a w visto che è orientato, e qui non succede.
Anche io credo che a questo punto bisogna esplorare l' intera matrice.
Logged

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

Posts: 57



« Reply #4 on: 25-09-2011, 02:13:20 »

Ecco la mia soluzione.
Sia A la matrice di adiacenza di G con vertici a, b, c.

   a b c
a 0 1 1
b 1 0 0
c 0 1 0

Si puo' rendere il grafo disconnesso rimuovendo qualsiasi arco che non sia (a,b).
Cerco un vertice con OUT-degree = 1 oppure con IN-degree = 1, ottenendo cosi' l'arco cercato.
Nel caso peggiore dobbiamo esaminare tutte le righe e tutte le colonne, per una complessita' |V|x|V|
Logged
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« Reply #5 on: 25-09-2011, 02:47:41 »

In ogni caso quando si ha il grafo con matrice di adiacenza quasi tutte le operazioni vengono fatte in tempo  O(V^2)...(tranne vedere se esiste un arco di vertici a b , che impiega O(1)..)... oppure no? Perche nel peggiore dei casi devi vedere tutta la matrice!! (almeno credo) XD
Logged
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #6 on: 25-09-2011, 03:07:41 »

In ogni caso quando si ha il grafo con matrice di adiacenza quasi tutte le operazioni vengono fatte in tempo  O(V^2)...(tranne vedere se esiste un arco di vertici a b , che impiega O(1)..)... oppure no? Perche nel peggiore dei casi devi vedere tutta la matrice!! (almeno credo) XD

quasi tutte.

come controesempio, servirebbe solo tempo O(|V|) se dovessi calcolare il grado di un vertice, o di un numero costante di vertici.
« Last Edit: 25-09-2011, 03:12:16 by Misa » Logged
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« Reply #7 on: 25-09-2011, 12:11:27 »

E se invece:

Sia G un grafo orientato con V=n vertici ed un solo ciclo che coinvolgre tutti i vertici tranne uno. Sia il grafo con liste di adiacenza. Qual è la complessita del miglior algotritmo per trovare tale vertice?

Io direi O(V) perchè basta scorrere la lista e vedere il vertice che ha degree out=0.

Voi cosa rispondereste?
Logged
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #8 on: 25-09-2011, 14:03:29 »

E se invece:

Sia G un grafo orientato con V=n vertici ed un solo ciclo che coinvolgre tutti i vertici tranne uno. Sia il grafo con liste di adiacenza. Qual è la complessita del miglior algotritmo per trovare tale vertice?

Io direi O(V) perchè basta scorrere la lista e vedere il vertice che ha degree out=0.

Voi cosa rispondereste?

Il ragionamento e' giusto, ma la complessita' e' O(|V| + |E|), per controllare tutti i degree (si devono controllare tutti gli archi E di tutti i vertici V)
Inoltre, esiste la possibilita' che l'OUT-degree di tutti i vertici sia >=1. Bisogna cercare il vertice che ha OUT-degree = 0, OPPURE IN-degree = 0.

Ne convieni?
Logged
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« Reply #9 on: 25-09-2011, 14:36:05 »

mmm...credo proprio di che hai ragione...

In ogni caso in generale per trovare il degree out si impiega (V+E) ... ma per trovare il degree in quanto si impiega? Non credo basti scorrere la lista una sola volta! oppure no?!
Logged
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #10 on: 25-09-2011, 15:23:04 »

mmm...credo proprio di che hai ragione...

In ogni caso in generale per trovare il degree out si impiega (V+E) ... ma per trovare il degree in quanto si impiega? Non credo basti scorrere la lista una sola volta! oppure no?!

Sono stato impreciso.
Per trovare l'IN-degree di un vertice bisogna scorrere tutte le liste.

A -> B -> C
B -> C
C -> A

Per trovare l'in-degree di A, ad esempio, devi scorrere tutte le liste e contare le occorrenze di A (complessita' |V|+|E|).
Per trovare l'out-degree di A, invece basta scorrere solo la lista di A (complessita' |E|).
Logged
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« Reply #11 on: 25-09-2011, 15:34:35 »

Quindi quando in un esercizio chiede di trovare il in / out degree max?
la risposta è: O(V+E) ..Giusto?
Logged
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #12 on: 25-09-2011, 15:43:03 »

Quindi quando in un esercizio chiede di trovare il in / out degree max?
la risposta è: O(V+E) ..Giusto?

si
Logged
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« Reply #13 on: 25-09-2011, 15:50:38 »

grazie mille 
Logged
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #14 on: 25-09-2011, 19:54:56 »

---- NUOVA DOMANDA ----

Le visite sui grafi BFS e DFS, nel caso avessimo implementato i grafi con matrici di adiacenza, richiedono complessita' O(|V|x|V|)?

Quindi l'ordinamento topologico, o la scoperta delle componenti fortemente connesse di un grafo implementato con matrici di adiacenza richiede pure tempo O(|V|x|V|)?

Credo che sia cosi', voi che ne pensate?
« Last Edit: 26-09-2011, 02:31:33 by Misa » Logged
Pages: [1] 2   Go Up
Print
Jump to: