Strano problema
Ciao a tutti, mi presento: Andrea di Novi Ligure.
Per una materia tecnica (SEO) che sto studiando necessito di un aiuto per la soluzione ad uno strano (per me?) problema matematico.
Spero di trovarmi nella sezione corretta.
Abbiamo quattro punti: A B C
I punti devono essere interconnessi tra loro ma unicamente e in modo unidirezionale, solo una volta.
Quindi, A --> B ma B non può tornare ad A
Verso A ci andrà C.
Per cui:
A--> B--> C---> A
C non può tornare su B perchè già connesso.
Ci siamo?
Bene.
Semplicissimo perchè solo con tre punti.
Il vero problema è che ho a disposizione 20 punti che devono essere interconnessi tra loro e il numero è in aumento.
Esiste un algoritmo che mi risolva punto per punto dove va connesso?
Ricordate: ogni punto deve essere collegato ad un altro solo una volta.
Come posso procedere?
Ho provato con un diagramma di flusso manualmente ma c'è da uscire di testa.
Grazie in anticipo.
WebSites Directory
http://www.cercametalli.org
Musicoterapia
Per una materia tecnica (SEO) che sto studiando necessito di un aiuto per la soluzione ad uno strano (per me?) problema matematico.
Spero di trovarmi nella sezione corretta.
Abbiamo quattro punti: A B C
I punti devono essere interconnessi tra loro ma unicamente e in modo unidirezionale, solo una volta.
Quindi, A --> B ma B non può tornare ad A
Verso A ci andrà C.
Per cui:
A--> B--> C---> A
C non può tornare su B perchè già connesso.
Ci siamo?
Bene.
Semplicissimo perchè solo con tre punti.
Il vero problema è che ho a disposizione 20 punti che devono essere interconnessi tra loro e il numero è in aumento.
Esiste un algoritmo che mi risolva punto per punto dove va connesso?
Ricordate: ogni punto deve essere collegato ad un altro solo una volta.
Come posso procedere?
Ho provato con un diagramma di flusso manualmente ma c'è da uscire di testa.
Grazie in anticipo.
WebSites Directory
http://www.cercametalli.org
Musicoterapia
Risposte
va bene anche qualcosa di semplice come questo?
\(A\to B\to C\to D\to E\to ... \to S\to T\to A\)
l'unica cosa che devi fare è decidere verso quale andare.
ti conviene numerarli da \(1\) a \(n\) e fare semplicemente questo
se vuoi puoi fare anche un percorso più caotico:
- segnati in un vettore quali hai già usato
- tieni traccia di qual è l'ultimo che hai utilizzato
- collegalo con uno a caso tra i restanti
ricorda che l'ultimo dovrà di nuovo collegarsi al primo.
\(A\to B\to C\to D\to E\to ... \to S\to T\to A\)
l'unica cosa che devi fare è decidere verso quale andare.
ti conviene numerarli da \(1\) a \(n\) e fare semplicemente questo
ripeti per i da 1 fino a n
i -> i+1
n -> 1
se vuoi puoi fare anche un percorso più caotico:
- segnati in un vettore quali hai già usato
- tieni traccia di qual è l'ultimo che hai utilizzato
- collegalo con uno a caso tra i restanti
ricorda che l'ultimo dovrà di nuovo collegarsi al primo.
"PrincipioAttivo":Che materia è? E questo problema da dove spunta fuori?
Per una materia tecnica (SEO) che sto studiando necessito di un aiuto per la soluzione ad uno strano (per me?) problema matematico.
Spero di trovarmi nella sezione corretta.
Direi che la sezione giusta potrebbe essere quella di ricerca operativa, casomai il thread sarà spostato.
"PrincipioAttivo":Ne vedo tre...
Abbiamo quattro punti: A B C
"PrincipioAttivo":Ne hai un numero fisso o il tuo problema vero è come connettere di volta in volta punti nuovi che si vanno ad aggiungere a quelli esistenti?
Il vero problema è che ho a disposizione 20 punti che devono essere interconnessi tra loro e il numero è in aumento.
"albertobosia":
va bene anche qualcosa di semplice come questo?
\(A\to B\to C\to D\to E\to ... \to S\to T\to A\)
l'unica cosa che devi fare è decidere verso quale andare.
Tutti devono andare verso tutti ma in una sola direzione e tutti devono avere lo stesso numero di entrate / uscite.
ricorda che l'ultimo dovrà di nuovo collegarsi al primo.
Temo che la cosa sia molto più complessa.
Qui uno schizzo veloce (che il forum mi taglia).
Considerate che non è completo, probabilmente.
"Fioravante Patrone":
Ne vedo tre...
ulp!! HAHA!!
Pardon.
Ne hai un numero fisso o il tuo problema vero è come connettere di volta in volta punti nuovi che si vanno ad aggiungere a quelli esistenti?[/quote][/quote]
Esatto, proprio l'ultima.
Grazie delle risposte, ragazzi.
"PrincipioAttivo":
Tutti devono andare verso tutti ma in una sola direzione e tutti devono avere lo stesso numero di entrate / uscite.
non mi era proprio chiaro dal primo post
intanto, notiamo che si può fare solo con \(n\) dispari, altrimenti non tutti potranno avere lo stesso numero di entrate / uscite.
quindi di volta in volta vai ad aggiungere 2 vertici.
una soluzione semplice potrebbe essere questa:
(clicca sull'immagine per ingrandirla)
- parti dal tuo grafo con \(n\) vertici e aggiungi gli altri due.
- scegline uno e collegalo in uscita con \(\frac{n+1}2\) vertici del grafo iniziale. (frecce arancioni)
- collega in entrata quel vertice con i restanti \(\frac{n-1}2\) del grafo iniziale. (freccia blu)
- collega in entrata l'altro vertice da aggiungere con quelli che avevano le frecce arancioni. (frecce verdi)
- collega quest'ultimo vertice in uscita con tutti i vertici cui non è collegato. (frecce rosse)
[OT]
Questo tipo di grafo a me sembra avesse un nome o mi ricorda il funzionamento di un algoritmo...
Tipo mi ricorda il tipico grafo utilizzato per mostrare il funzionamento dell'algortimo di Dijkstra con il problema dei cammini minimi o la proprietà è molto simile.
[/OT]
Questo tipo di grafo a me sembra avesse un nome o mi ricorda il funzionamento di un algoritmo...
Tipo mi ricorda il tipico grafo utilizzato per mostrare il funzionamento dell'algortimo di Dijkstra con il problema dei cammini minimi o la proprietà è molto simile.
[/OT]
"albertobosia":
non mi era proprio chiaro dal primo post
Colpa mia.
intanto, notiamo che si può fare solo con \(n\) dispari, altrimenti non tutti potranno avere lo stesso numero di entrate / uscite.
quindi di volta in volta vai ad aggiungere 2 vertici.
Perfetto. Ottima informazione: solo dispari.
una soluzione semplice potrebbe essere questa:
Spiego esattamente la motivazione della richiesta.
Come anticipato sto studiando SEO: l'ottimizzazione dell'indicizzazione motori di ricerca.
Una problematica comune in rete è lo scambio di link tra i siti perchè penalizza fortemente il rank.
Se però un link viene aggiunto ad un sito e sul corrispettivo portale si aggiunge un terzo sito comune tra i primi due, il rank aumenta invece che diminuire.
Gestisco 19 siti Internet ai quali è necessario fare salire il rank.
Se su ognuno procedo con uno scambio di link mirato, raggiungo l'obiettivo e l'unico modo per farlo è studiare una metodologia logica.
Quindi, Albertobosia, necessito un qualcosa che mi dica "al volo" come interconnettere i siti tra loro tutte le volte che aggiungo un nuovo sito.
Ovviamente, l'ideale sarebbe un software che mi suggerisse le nuove configurazioni ad ogni nuova immissione di "n".
Chissà se esiste un programmino del genere.
Non so neanche cosa cercare.
Magari una foglio di calcolo?
"Fioravante Patrone":
Che materia è? E questo problema da dove spunta fuori?
SEO = Search Engine Optimization. Il problema è un classico, legato al pagerank di zio Gùgl.
"PrincipioAttivo":
Quindi, Albertobosia, necessito un qualcosa che mi dica "al volo" come interconnettere i siti tra loro tutte le volte che aggiungo un nuovo sito.
Il metodo che ti ha indicato risponde perfettamente alla richiesta.
che sia hamiltoniano puoi dimostrarlo per induzione.
chiaramente, quello con 3 vertici è hamiltoniano.
supposto che quello con n vertici sia hamiltoniano, guardiamo quello con n+2 vertici.
un ciclo è questo: nuovo vertice A -> ciclo del grafo con n vertici -> nuovo vertice B -> nuovo vertice A
chiaramente, quello con 3 vertici è hamiltoniano.
supposto che quello con n vertici sia hamiltoniano, guardiamo quello con n+2 vertici.
un ciclo è questo: nuovo vertice A -> ciclo del grafo con n vertici -> nuovo vertice B -> nuovo vertice A
Ciao Alberto.
Hamiltoniano o meno, come soluzione pratica mi rimane solo da scrivere un piccolo script in php che mi dica cosa fare ad ogni vertice aggiunto.
Vi tengo informati (sempre che vi interessi).
GRAZIE a tutti!!
Hamiltoniano o meno, come soluzione pratica mi rimane solo da scrivere un piccolo script in php che mi dica cosa fare ad ogni vertice aggiunto.
Vi tengo informati (sempre che vi interessi).
GRAZIE a tutti!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo