Trovare un cammino in questo grafo

[elMakiko1]

Ciao a tutti sono nuovo in questo forum.
Un pò di giorni fa mi è capitato di trovarmi di fronte ad un problema del grenere:
è possibile trovare un cammino nel grafo sotto che attraversi tutti gli archi senza mai passare due volte per lo stesso (arco)???
Sfogliando un po di libri ho trovato vari problemi simili come quello dei cicli euleriani ecc. ma questo particolare problema non sono riuscito a trovarlo. Io il cammino non l'ho trovato [V]e penso che non ci sia tuttavia vorrei saper il motivo della sua inesistenza o eventualmente se esiste qual'è e perchè esiste.
Grazie per l'aiuto (non dormo più la notte[:D]) fatemi sapere!!

INFO:ho dovuto inserire le "a" perché altrimenti mi si deformava il grafo. Le "a" rappresentano spazi vuoti quindi ignoratele i caratteri sono i seguenti - \ / O |
Eventualmente posso inserire un'immagine se non lo capite ma solamante se mi dite come si fa[:D](a mettere l'immagine)

aaaaaaaaaaaaaaaa---
aaaaaaaaaaaaaaa/aaa\
aaaaaaaaaaaaaaO-----O
aaaaaaaaaaaaa/|\aaa/|\
aaaaaaaaaaaa/a|a\a/a|a\
aaaaaaaaaaa|aa|aaOa|aa|
aaaaaaaaaaaa\a|a/a\a|a/
aaaaaaaaaaaaa\|/aaa\|/
aaaaaaaaaaaaaaO-----O
aaaaaaaaaaaaaaa\aaa/
aaaaaaaaaaaaaaaa---


PS Se eventualmente il vertice centrale non ci fosse ma il numero degli archi rimanesse invariato cambierebbe qualcosa??

[WonderP1]

per vedere se è risolvibile devi contare il numero di linee che arrivano in ogni O. Per essere risolvibile devono esserci non più di 2 O con un numero dispari di linee che lo raggiungono.
Per "disegnare" bene sul forum cose come le hai messe tu devi metterle tra ['code] e ['/code], ovviamente senza apici, così prende anche i doppi spazi.
Scua la fretta ma devo tornare a lavoro. Spero tu abbia capito al massimo chiedi ancora e ti rispondo sta sera.
Buona giornata.

WonderP.

[elMakiko1]

Grazie per la partecipazione.
Ok, il mio grafo ha 5 nodi di cui:
4 con 5 archi ed 1 con 4 archi quindi non si può risolvere perchè il numero di nodi con grado dispari è maggiore di 2.

Domanda n.1
Da quale teorema posso dedurre ciò (se te lo ricordi)?

Domanda n.2
E se il mio grafo fosse questo...

 
    ---
   /   \
  O-----O
  |\   /|
  | \ / |
  |  O  |
  | / \ |
  |/   \|
  O-----O

come dici tu dovrebbe esistere il cammino ma io non l'ho trovato...

[elMakiko1]

...no, no ora l'ho trovato [:D] cmq vorrei sapere sempre se esiste un teorema o qlc di simile dal quale posso ricavare il discorso della risolvibilità del mio problema.

Grazie.

[MaMo2]

L'ultimo grafo è percorribile.
Bisogna partire e terminare con un nodo dispari.
Indicando con ABCD il rettangolo (in senso orario dal vertice A in basso a sinistra), con E il vertice in alto e con O il punto di incontro delle diagonali, uno dei possibili percorsi è:
ABECDACBD.

[vecchio1]

beh se non sbaglio esiste tutta una teoria dei grafi...uno dei quesiti più famosi è quello dei ponti di Koenigsberg... o come cavolo si scrive!
cercando con Google ho trovato questo link...

https://www.matematicamente.it/approfondimenti/grafi.htm

puoi facilmente trovare altri link cercando un po' coi motori i ricerca