Ricerca di un cammino all'interno di un grafo orientato

Messaggioda feded123 » 03/07/2020, 15:27

\( \displaystyle A = { (1,2);(2,3),(2,4),(3,1),(5,4).} \)\( \displaystyle A = { (1,2);(2,3),(2,4),(3,1),(5,4).} \)Salve a tutti,
Volevo chiedervi se un'affermazione del genere è corretta :

Preso un elemento qualsiasi di un grafo orientato \(\displaystyle G \) composto da\(\displaystyle N \) elementi, si supponga di cercare un cammino da un elemento \(\displaystyle A \) a \(\displaystyle B \).

Possiamo affermare che se, nella ricerca del cammino, la lunghezza del percorso da \(\displaystyle A \) a \(\displaystyle B \) supera \(\displaystyle N \) allora quel cammino è ciclico e non raggiungerà mai \(\displaystyle B \).


Diamo per scontato che se un elemento può andare in \(\displaystyle C \) o in \(\displaystyle D \) allora noi sceglieremo una delle due strade. In caso quella scelta non fosse valida passeremmo allora al controllo dell'altro percorso.

Ho cercato un po' su internet ma non ho trovato un teorema che affermi una cosa simile.

Io immagino che sia così, non saprei come dimostrarlo correttamente in "matematichese :lol: " quindi chiedo a voi se esiste qualche teorema su questo argomento.

Edit :
Ho letto i commenti e provo ad essere più specifico. Scusate le inesattezze :( .

Io per grafo intendo una coppia di elementi :
Uno è un collegamento ad un altro elemento dello stesso tipo mentre l'altro è proprio il valore di quel "nodo".
Per esempio il grafo \(\displaystyle (3,4) \) indica che noi ci troviamo nell'elemento \(\displaystyle 3 \) e il nodo successivo a \(\displaystyle 3 \) è \(\displaystyle 4 \).

Quello che noi abbiamo è un insieme di questi elementi :
\(\displaystyle A = { (1,2);(2,3),(2,4),(3,1),(5,4).} \)
Dove \(\displaystyle 3 \) e \(\displaystyle 4 \), per esempio, sono i successori di \(\displaystyle 2 \) il quale è successore di \(\displaystyle 1 \).
Per "cammino" intendo, preso l'esempio sopra :
Cerco il cammino da \(\displaystyle 1 \) a \(\displaystyle 3 \) quindi vedo i successori di \(\displaystyle 1 \), e noto che ha solo \(\displaystyle 2 \), questo ha \(\displaystyle 3 \) e \(\displaystyle 4 \) quindi siccome \(\displaystyle 3 \) è successore di \(\displaystyle 2 \) che è successore di \(\displaystyle 1 \) allora posso affermare che esiste un cammino da \(\displaystyle 1 \) a \(\displaystyle 3 \).
Se, per esempio, avessi cercato il cammino da \(\displaystyle 1 \) a \(\displaystyle 5 \) l'esito sarebbe stato negativo perché nessun successore di \(\displaystyle 1 \) raggiunge l'elemento 5.
Quindi possiamo spostarci solo sui successori di un elemento, non possiamo andare dove vogliamo e no, non possiamo muoverci "all'indietro" in quanto le uniche informazioni che abbiamo sono sugli elementi successivi a quello in cui ci troviamo, non sui precedenti.

Spero di essere stato chiaro al 100%, questa cosa mi incuriosisce molto :lol:
Ultima modifica di feded123 il 05/07/2020, 11:03, modificato 1 volta in totale.
feded123
New Member
New Member
 
Messaggio: 28 di 56
Iscritto il: 21/04/2017, 13:52

Re: Ricerca di un cammino all'interno di un grafo orientato

Messaggioda hydro » 03/07/2020, 16:14

E' difficile rispondere perchè non si capisce la domanda. Che cos'è un elemento di un grafo? Immagino che sia un vertice. Ma cosa c'entra con $A$ e $B$? E cosa vuol dire "si supponga di cercare un cammino"? Poi non ho capito, il cammino va da $A$ a $B$ ma può non raggiungere $B$? Cosa significa?
hydro
Senior Member
Senior Member
 
Messaggio: 45 di 1456
Iscritto il: 01/10/2005, 18:22
Località: Italy

Re: Ricerca di un cammino all'interno di un grafo orientato

Messaggioda gugo82 » 03/07/2020, 18:10

Poi, gli archi come sono?
Orientati? Percorribili in una sola direzione o in entrambe?

Se io posso andare da $A$ a $B$ e da $B$ ad $A$ (su un unico arco o su due archi distinti) è chiaro che ho formato un ciclo che posso ripetere ad libitum
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Cannot live without
Cannot live without
 
Messaggio: 24260 di 44916
Iscritto il: 12/10/2007, 23:58
Località: Napoli

Re: Ricerca di un cammino all'interno di un grafo orientato

Messaggioda solaàl » 04/07/2020, 10:45

Formalmente un grafo è una coppia \((V, E)\) dove \(V\) è un insieme, e \(E\subseteq \binom{V}{2}\) è un sottoinsieme dell'insieme di tutti i sottoinsiemi di 2 elementi di \(V\); quindi un "elemento" di un grafo, con lieve abuso di notazione, è un suo vertice.

Poi, non so se il messaggio è stato editato dopo che è stato chiesto se gli edge sono orientati, ma al momento c'è scritto grafo orientato, quindi si possono percorrere in un verso solo; e probabilmente se c'è un edge \(A \to B\), non si può percorrere un edge \(B\to A\), -sempre che non ci sia-.
"In verità le cose che nella vita sono tenute in gran conto si riducono a vanità, o putredine di nessun valore; botoli che si addentano, bambocci litigiosi che ora ridono, poi tosto piangono." (Lotario conte di Segni)
Avatar utente
solaàl
Senior Member
Senior Member
 
Messaggio: 449 di 1672
Iscritto il: 31/10/2019, 01:45

Re: Ricerca di un cammino all'interno di un grafo orientato

Messaggioda gugo82 » 04/07/2020, 10:53

Bene, ma potrebbero esserci entrambi gli archi $A->B$ e $B->A$ ed il ciclo lo firmi comunque.

Tendo a credere che la domanda si riferisca a qualche metodo di ricerca di cammini minimi... Ma OP dovrebbe chiarire.
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Cannot live without
Cannot live without
 
Messaggio: 24274 di 44916
Iscritto il: 12/10/2007, 23:58
Località: Napoli

Re: Ricerca di un cammino all'interno di un grafo orientato

Messaggioda hydro » 05/07/2020, 22:36

feded123 ha scritto:Io per grafo intendo una coppia di elementi :
Uno è un collegamento ad un altro elemento dello stesso tipo mentre l'altro è proprio il valore di quel "nodo".
Per esempio il grafo \( \displaystyle (3,4) \) indica che noi ci troviamo nell'elemento \( \displaystyle 3 \) e il nodo successivo a \( \displaystyle 3 \) è \( \displaystyle 4 \).


Questo non si può fare, non puoi dire "io per grafo intendo..." e poi decidere tu la definizione. Il termine grafo ha un significato specifico in matematica, che è quello che ti ha ricordato solaàl.

Detto questo, continua a non capirsi quale sia la domanda. Forse, ma non ne sono troppo sicuro, tu stai chiedendo se è vero che in un grafo diretto con $N$ vertici, dati due vertici $A$ e $B$ il cammino minimo da $A$ a $B$ (se esiste) ha lunghezza al più $N$. Questo è certamente vero, si prova rapidamente per induzione.
hydro
Senior Member
Senior Member
 
Messaggio: 46 di 1456
Iscritto il: 01/10/2005, 18:22
Località: Italy

Re: Ricerca di un cammino all'interno di un grafo orientato

Messaggioda vict85 » 06/07/2020, 08:44

Questa sembra una domanda di algoritmi informatici e usa il loro linguaggio. In ogni caso, un cammino di lunghezza maggiore \(N\) in un grado orientato, o meno, con \(N\) vertici visita banalmente un qualche vertice più di una volta e deve quindi contenere cicli.
vict85
Moderatore
Moderatore
 
Messaggio: 10151 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite