Cammino hamiltoniano

Cammino hamiltoniano (Reindirizzato da teorema di Bondy-Hvátal) Vai alla navigazione Vai alla ricerca Questo articolo riguarda la natura dei percorsi hamiltoniani. Per la questione dell'esistenza di un percorso o ciclo Hamiltoniano in un dato grafo, vedi problema del cammino hamiltoniano. Un ciclo hamiltoniano attorno a una rete di sei vertici Nel campo matematico della teoria dei grafi, un percorso hamiltoniano (o percorso tracciabile) è un percorso in un grafo non orientato o diretto che visita ogni vertice esattamente una volta. Un ciclo Hamiltoniano (o circuito hamiltoniano) è un ciclo che visita ogni vertice esattamente una volta. Un percorso hamiltoniano che inizia e finisce in corrispondenza di vertici adiacenti può essere completato aggiungendo un altro arco per formare un ciclo hamiltoniano, e la rimozione di qualsiasi arco da un ciclo hamiltoniano produce un percorso hamiltoniano. Determinare se tali percorsi e cicli esistono nei grafici (il problema del cammino hamiltoniano e il problema del ciclo hamiltoniano) sono NP-completi.

I percorsi e i cicli hamiltoniani prendono il nome da William Rowan Hamilton che ha inventato il gioco icosiano, ora noto anche come il puzzle di Hamilton, che implica la ricerca di un ciclo Hamiltoniano nel grafico di bordo del dodecaedro. Hamilton ha risolto questo problema usando il calcolo icosiano, una struttura algebrica basata su radici di unità con molte somiglianze con i quaternioni (inventato anche da Hamilton). Questa soluzione non si generalizza ai grafi arbitrari.

Nonostante abbia preso il nome da Hamilton, Anche i cicli hamiltoniani nei poliedri erano stati studiati un anno prima da Thomas Kirkman, chi, in particolare, ha fornito un esempio di un poliedro senza cicli hamiltoniani.[1] Anche prima, Cicli e percorsi hamiltoniani nel grafico del cavaliere della scacchiera, il giro del cavaliere, era stato studiato nel IX secolo nella matematica indiana da Rudrata, e più o meno nello stesso periodo nella matematica islamica di al-Adli ar-Rumi. Nell'Europa del 18° secolo, i tour dei cavalieri furono pubblicati da Abraham de Moivre e Leonhard Euler.[2] Contenuti 1 Definizioni 2 Esempi 3 Proprietà 4 Bondy – Teorema afferrato 5 Esistenza di cicli Hamiltoniani nei grafi planari 6 Il polinomio del ciclo hamiltoniano 7 Guarda anche 8 Appunti 9 Riferimenti 10 Collegamenti esterni Definizioni Un percorso hamiltoniano o percorso tracciabile è un percorso che visita ogni vertice del grafico esattamente una volta. Un grafo che contiene un percorso hamiltoniano è chiamato grafo tracciabile. Un grafo è connesso hamiltoniano se per ogni coppia di vertici esiste un percorso hamiltoniano tra i due vertici.

Un ciclo Hamiltoniano, circuito hamiltoniano, Vertex tour o ciclo del grafico è un ciclo che visita ogni vertice esattamente una volta. Un grafo che contiene un ciclo hamiltoniano è chiamato grafo hamiltoniano.

Nozioni simili possono essere definite per i grafi diretti, dove ogni bordo (arco) di un sentiero o di una ciclabile possono essere tracciati solo in un'unica direzione (cioè., i vertici sono collegati con frecce e gli spigoli tracciati "coda a testa").

Una decomposizione hamiltoniana è una scomposizione degli archi di un grafo in circuiti hamiltoniani.

Un labirinto Hamilton è un tipo di puzzle logico in cui l'obiettivo è trovare l'unico ciclo Hamiltoniano in un dato grafico.[3][4] Esempi Proiezioni ortografiche e diagrammi di Schlegel con cicli hamiltoniani dei vertici dei cinque solidi platonici - solo l'ottaedro ha un percorso o ciclo euleriano, estendendo il suo percorso con il punto vte Un grafo completo con più di due vertici è hamiltoniano Ogni grafo di ciclo è hamiltoniano Ogni torneo ha un numero dispari di cammini hamiltoniani (È tuo 1934) Ogni solido platonico, considerato come un grafico, è hamiltoniano[5] Il grafo di Cayley di un gruppo finito di Coxeter è hamiltoniano (Per ulteriori informazioni sui percorsi Hamiltoniani nei grafici di Cayley, vedi la congettura di Lovász.) I grafici di Cayley sui gruppi nilpotenti con sottogruppo del commutatore ciclico sono hamiltoniani.[6] Il grafico di capovolgimento di un poligono convesso o equivalente, il grafico di rotazione degli alberi binari, è hamiltoniano.[7][8] Proprietà Il grafo di Herschel è il più piccolo grafo poliedrico possibile che non ha un ciclo hamiltoniano. Viene mostrato un possibile percorso hamiltoniano.

Qualsiasi ciclo hamiltoniano può essere convertito in un percorso hamiltoniano rimuovendo uno dei suoi bordi, ma un percorso hamiltoniano può essere esteso al ciclo hamiltoniano solo se i suoi estremi sono adiacenti.

Tutti i grafi hamiltoniani sono biconnessi, ma un grafo biconnesso non deve necessariamente essere hamiltoniano (vedere, Per esempio, il grafico di Petersen).[9] Un grafico euleriano G (un grafo connesso in cui ogni vertice ha grado pari) ha necessariamente un tour di Eulero, una passeggiata chiusa che passa per ogni spigolo di G esattamente una volta. Questo giro corrisponde a un ciclo Hamiltoniano nel grafico a linee L(G), quindi il grafico a linee di ogni grafo euleriano è hamiltoniano. I grafici a linee possono avere altri cicli hamiltoniani che non corrispondono ai tour di Eulero, ed in particolare il grafico a linee L(G) di ogni grafo hamiltoniano G è esso stesso hamiltoniano, indipendentemente dal fatto che il grafo G sia euleriano.[10] Un torneo (con più di due vertici) è hamiltoniana se e solo se è fortemente connessa.

Il numero di diversi cicli Hamiltoniani in un grafo completo non orientato su n vertici è (n - 1)! / 2 e in un grafo completo diretto su n vertici è (n - 1)!. Questi conteggi presuppongono che i cicli che sono gli stessi a parte il loro punto di partenza non vengano contati separatamente.

Teorema di Bondy-Chvátal La migliore caratterizzazione del grado di vertice dei grafi hamiltoniani è stata fornita in 1972 dal Bondy-Grab il teorema, che generalizza i risultati precedenti di G. UN. Dirac (1952) e Øystein Ore. Sia il teorema di Dirac che quello di Ore possono essere derivati ​​dal teorema di Pósa (1962). L'Hamiltonicità è stata ampiamente studiata in relazione a vari parametri come la densità del grafico, durezza, sottografi proibiti e distanza tra gli altri parametri.[11] I teoremi di Dirac e Ore affermano sostanzialmente che un grafo è hamiltoniano se ha abbastanza archi.

Il teorema di Bondy-Chvátal opera sulla chiusura cl(G) di un grafo G con n vertici, ottenuto aggiungendo ripetutamente un nuovo arco uv che collega una coppia non adiacente di vertici u e v con deg(v) + gradi(tu) ≥ n finché non è possibile trovare più coppie con questa proprietà.

Bondy - Afferrato dal teorema (1976) — Un grafo è hamiltoniano se e solo se la sua chiusura è hamiltoniana.

Poiché i grafici completi sono hamiltoniani, tutti i grafi la cui chiusura è completa sono hamiltoniani, che è il contenuto dei seguenti teoremi precedenti di Dirac e Ore.

Il teorema di Dirac (1952) — Un grafo semplice con n vertici ( {stile di visualizzazione ngeq 3} ) è hamiltoniana se ogni vertice ha grado {stile di visualizzazione {tfrac {n}{2}}} o maggiore.

Teorema di Ore (1960) — Un grafo semplice con n vertici ( {stile di visualizzazione ngeq 3} ) è hamiltoniano se, per ogni coppia di vertici non adiacenti, la somma dei loro gradi è n o maggiore.

I seguenti teoremi possono essere considerati versioni dirette: Ghouila-Houiri (1960) — Un grafo orientato semplice fortemente connesso con n vertici è hamiltoniano se ogni vertice ha un grado intero maggiore o uguale a n.

Meiniel (1973) — Un grafo orientato semplice fortemente connesso con n vertici è hamiltoniano se la somma dei gradi interi di ogni coppia di vertici distinti non adiacenti è maggiore o uguale a {stile di visualizzazione 2n-1} Il numero di vertici deve essere raddoppiato perché ogni spigolo non orientato corrisponde a due archi diretti e quindi il grado di un vertice nel grafo orientato è il doppio del grado nel grafo non orientato.

Rahman Kaykobad (2005) — Un grafo semplice con n vertici ha un cammino hamiltoniano if, per ogni coppia di vertici non adiacenti la somma dei loro gradi e la loro lunghezza del cammino minimo è maggiore di n.[12] Il teorema sopra può riconoscere solo l'esistenza di un percorso hamiltoniano in un grafo e non un ciclo hamiltoniano.

Molti di questi risultati hanno analoghi per i grafici bipartiti bilanciati, in cui i gradi dei vertici vengono confrontati con il numero di vertici su un singolo lato della bipartizione piuttosto che con il numero di vertici nell'intero grafo.[13] Esistenza di cicli hamiltoniani nei grafi planari Teorema — Una triangolazione planare 4-connessa ha un ciclo hamiltoniano.[14] Teorema — Un grafo planare 4 connesso ha un ciclo hamiltoniano.[15] Il polinomio del ciclo hamiltoniano Una rappresentazione algebrica dei cicli hamiltoniani di un dato digrafo pesato (ai cui archi sono assegnati pesi da un determinato campo di terra) è il polinomio del ciclo hamiltoniano della sua matrice di adiacenza ponderata definita come la somma dei prodotti dei pesi dell'arco dei cicli hamiltoniani del digrafo. Questo polinomio non è identicamente zero come funzione nei pesi dell'arco se e solo se il digrafo è hamiltoniano. La relazione tra le complessità computazionali del suo calcolo e il calcolo del permanente è stata mostrata da Grigoriy Kogan.[16] Vedi anche la congettura di Barnette, un problema aperto sull'Hamiltonicità di grafi poliedrici bipartiti cubici Cammino euleriano, un percorso attraverso tutti gli archi in un grafo teorema di Fleischner, sui quadrati Hamiltoniani dei grafi Codice Gray Teorema di Grinberg che fornisce una condizione necessaria affinché i grafi planari abbiano un ciclo Hamiltoniano problema del cammino Hamiltoniano, il problema computazionale di trovare cammini Hamiltoniani Grafico ipohamiltoniano, un grafo non hamiltoniano in cui ogni sottografo eliminato dal vertice è il tour di Hamiltonian Knight, un ciclo hamiltoniano nella notazione LCF del grafo del cavaliere per i grafi cubici hamiltoniani. Lovász congettura che i grafi transitivi ai vertici siano grafi panciclici hamiltoniani, grafici con cicli di tutte le lunghezze incluso un ciclo hamiltoniano Sette ponti di Königsberg Esponente di brevità, una misura numerica di quanto lontano dall'hamiltoniano i grafici in una famiglia possono essere Snake-in-the-box, il percorso indotto più lungo in un algoritmo di ipercubo Steinhaus–Johnson–Trotter per trovare un percorso hamiltoniano in un grafo subhamiltoniano permutoedro, un sottografo di un grafo hamiltoniano planare congettura di Tait (ora noto falso) che i grafi poliedrici a 3 regolari sono un problema del venditore ambulante Hamiltoniano Note ^ Biggs, N. l. (1981), "T. P. Kirkman, matematico", Il Bollettino della London Mathematical Society, 13 (2): 97–120, doi:10.1112/blms/13.2.97, SIG 0608093. ^ Watkins, John J. (2004), "Capitolo 2: Tour dei Cavalieri", Su tutta la linea: La matematica dei problemi della scacchiera, Stampa dell'Università di Princeton, pp. 25–38, ISBN 978-0-691-15498-5. ^ il Cavaliere, Giovanni (2017). Hamilton Labirinti - La guida per principianti. ^ Friedman, Erich (2009). "Labirinti Hamiltoniani". Il palazzo dei puzzle di Erich. Archiviato dall'originale in poi 16 aprile 2016. Recuperato 27 Maggio 2017. ^ Gardner, M. "Giochi matematici: Sulla notevole somiglianza tra il gioco icosiano e le torri di Hanoi." Sci. Amer. 196, 150–156, Maggio 1957 ^ Gaderpour, e.; Morris, D. w. (2014). "I grafici di Cayley sui gruppi nilpotenti con sottogruppo del commutatore ciclico sono hamiltoniani". Ars Mathematica Contemporanea. 7 (1): 55–72. arXiv:1111.6216. doi:10.26493/1855-3974.280.8d3. ^ Luca, Giovanna M. (1987), "Il grafico di rotazione degli alberi binari è hamiltoniano", Diario di algoritmi, 8 (4): 503–535, doi:10.1016/0196-6774(87)90048-4 ^ Hurtado, Ferran; No, marc (1999), "Grafico delle triangolazioni di un poligono convesso e albero delle triangolazioni", Geometria computazionale, 13 (3): 179–188, doi:10.1016/S0925-7721(99)00016-4 ^ Eric Weinstein. "Grafico biconnesso". Wolfram MathWorld. ^ Balakrishnan, R.; Ranganathan, K. (2012), "Corollario 6.5.5", Un libro di testo di teoria dei grafi, Springer, p. 134, ISBN 9781461445296. ^ Gould, Ronald J. (Luglio 8, 2002). "Avanzamenti sul problema hamiltoniano: un'indagine" (PDF). Emory University. Recuperato 2012-12-10. ^ Rahman, M. S.; Kaykobad, M. (aprile 2005). "Su cicli hamiltoniani e cammini hamiltoniani". Lettere di elaborazione delle informazioni. 94: 37–41. doi:10.1016/j.ipl.2004.12.002. ^ Luna, J.; Moser, l. (1963), "Su grafi bipartiti hamiltoniani", Israel Journal of Mathematics, 1 (3): 163–165, doi:10.1007/BF02759704, SIG 0161332 ^ Whitney, Hassler (1931), "Un teorema sui grafici", Annali di matematica, Seconda serie, 32 (2): 378–390, doi:10.2307/1968197, JSTOR 1968197, SIG 1503003 ^ Tutte, w. T. (1956), "Un teorema sui grafi planari", Trans. Amer. Matematica. soc., 82: 99–116, doi:10.1090/s0002-9947-1956-0081471-8 ^ Kogan, Gregorio (1996), "Calcolare permanenti su campi caratteristici 3: dove e perché diventa difficile", 37th Simposio annuale sui fondamenti dell'informatica (FUOCO '96): 108–114, doi:10.1109/SFCS.1996.548469, ISBN 0-8186-7594-2 Riferimenti Berge, Claudio; Ghouila-Houiri, UN. (1962), Programmazione, giochi e reti di trasporto, New York: Figli maschi, Inc. De Leon, Melissa (2000), "Uno studio di condizioni sufficienti per i cicli Hamiltoniani" (PDF), Diario di matematica per studenti universitari Rose-Hulman, 1 (1), archiviato dall'originale (PDF) Su 2012-12-22, recuperato 2005-11-28. Dirac, G. UN. (1952), "Alcuni teoremi sui grafi astratti", Atti della London Mathematical Society, 3rd Ser., 2: 69–81, doi:10.1112/plms/s3-2.1.69, SIG 0047308. Hamilton, William Rowan (1856), "Memorandum che rispetta un nuovo sistema di radici di unità", Rivista filosofica, 12: 446. Hamilton, William Rowan (1858), "Resoconto del calcolo icosiano", Atti della Royal Irish Academy, 6: 415–416. Meiniel, M. (1973), "Condizione sufficiente per l'esistenza di un circuito hamiltoniano in un grafo orientato", Rivista di teoria combinatoria, Serie B, 14 (2): 137–147, doi:10.1016/0095-8956(73)90057-9, SIG 0317997. Minerale, Øystein (1960), "Nota sui circuiti di Hamilton", Il mensile matematico americano, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928, SIG 0118683. Elegante, l. (1962), "Un teorema sulle linee di Hamilton", Tud ungherese. Ritardo. Stuoia. Ricerca Int. comm., 7: 225–226, SIG 0184876. Weissstein esterno sinistro, Eric W. "Ciclo Hamiltoniano". Math World. Categorie del tour di Eulero e dei cicli di Hamilton: Problemi di calcolo nella teoria dei grafiProblemi NP-completiOggetti di teoria dei grafiPercorsi e cicli hamiltonianiWilliam Rowan Hamilton