Ricerca di un cammino all'interno di un grafo orientato

[fede97d]

\( \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 " 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

[hydro1]

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?

[gugo82]

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…

[solaàl]

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-.

[gugo82]

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.

[hydro1]

"feded123":
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.

[vict85]

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.