Parte 2 Parte 3 Parte 4 Mi è stato chiesto di scrivere questo articolo da un'attività dannosa della ricerca Java Multithreading, che, non senza qualche presa in giro da parte degli sviluppatori, è stata chiamata da loro un "attività StringBuilder". L'essenza della sua condizione era che una serie di parole (nella condizione in cui vengono dati i nomi delle città, che ricorda un gioco di parole per bambini) doveva essere disposta secondo il principio del domino, l'ultima lettera della parola n doveva essere uguale alla prima lettera della parola (n+1) go, ed era noto che tutte le parole date (individualmente) venivano sommate in tale catena. Se era possibile comporre più opzioni per la catena di parole desiderata, come soluzione veniva accettata una qualsiasi. Nonostante l'apparente semplicità e chiarezza della condizione, risolvere il problema è stato tutt'altro che facile e l'uso magistrale di StringBuilder non ha salvato la situazione. Si è scoperto che gli sviluppatori del problema erano isomorfi ordinati del pianeta Linear Chaos, che più di una volta hanno terrorizzato i cadetti di JavaRush. Come previsto, le soluzioni superficiali non erano adatte al validatore, poiché c'erano sempre catene che costringevano l'ingenuo algoritmo a saltare le parole. È stato necessario accumulare ulteriori “stampelle” che, pur complicando il problema, non avvicinavano la soluzione nel caso generale e rafforzavano sempre più la sensazione che una condizione semplice dovesse avere una soluzione altrettanto semplice. Ho dovuto cambiare tattica e immergermi un po’ in aree più fondamentali. Vorrei fare subito una riserva che in nessun caso mi considero un esperto di teoria dei grafi; gli argomenti che toccherò quasi non vanno oltre lo scopo di risolvere il problema delle parole del domino, con l'eccezione, forse, solo un paio di divagazioni di carattere teorico. Quindi, grafici. Cos'è un grafico: è una raccolta (insieme, insieme, lista - qualunque cosa) di vertici collegati tra loro . Le connessioni sono solitamente chiamate bordi , i vertici sono anche chiamati nodi o nodi. Questo è un grafico: Anche questo è un grafico: Se possiamo dire di un bordo che ha una direzione, allora il grafico si chiama orientato : I grafici nelle prime due immagini non sono orientati. Possiamo dire di loro che lo spigolo (u, v) è identico allo spigolo (v, u), cioè, ad esempio, gli spigoli (0, 4) e (4, 0) sono lo stesso spigolo. Le frecce sui bordi di un grafico orientato indicano che il bordo (u, v) è un percorso dal vertice u al vertice v e il bordo (v, u) non esiste. Nella terza immagine c'è un bordo (E, A). Non c'è alcun bordo (A, E). Diamo uno sguardo più da vicino all'ultimo disegno. Puoi notare che il vertice F non ha bordi, questo è del tutto possibile. Notiamo anche che vicino al vertice A è apparso un bordo - un anello, e tra i vertici B e D ci sono due bordi orientati diversamente. I grafici diretti consentono tali artefatti. Diciamo che il grafico descrive un gruppo di conoscenti che si scambiano regali. Vediamo che il goloso F non ha regalato nulla a nessuno, B e D si sono scambiati regali (a parte il fatto che ognuno di loro ha fatto un regalo a qualcun altro), e A ha fatto un regalo a se stesso, probabilmente in occasione della risoluzione con successo di un problema problema dal pianeta Caos lineare. A proposito, nota che i vertici del grafico non devono essere numeri o contenere numeri; sono piuttosto contenitori, cioè possono riporre qualsiasi oggetto. Un grafico è una descrizione delle connessioni. Un termine importante che ci sarà utile in seguito: il numero di spigoli attaccati a un vertice (o, come si dice, incidenti ad esso) è chiamato grado di un dato vertice. Ad esempio, nella prima immagine, il vertice 0 ha grado 2, 1 ha grado 4, 3 ha grado 3, il vertice 0 della seconda figura ha grado 1. In questo articolo non approfondiremo la varietà dei diversi tipi di grafici, menzioneremo solo che esistono anche i grafici ponderati, quelli. quelli in cui su ciascun bordo è attaccato un certo numero, che indica il “prezzo” del suo passaggio. I grafi connessi hanno una serie di sottotipi, distinti dalle loro proprietà. Ad esempio, i grafici i cui bordi non formano un ciclo da nessuna parte sono chiamati alberi (hanno famiglie interessanti con nomi fantastici come “alberi rosso-neri”, per esempio) e sono ampiamente utilizzati in una varietà di importanti algoritmi e strutture dati. Usare un grafico per risolvere un problema Tutto questo è molto interessante, dirai, ma cosa c'entra tutto questo con la costruzione di una catena di parole? Si scopre che la cosa più diretta è. Diamo un'occhiata al nostro esempio di prova dalla condizione: { Amsterdam Melbourne New York Kyiv Vienna }. Scriviamo in qualsiasi ordine le lettere "nodali" a cui si aggrappano le parole: {A, M, N, K, B} e colleghiamole con le parole. Come possiamo vedere, abbiamo un grafo orientato in cui i nodi sono lettere e i bordi sono parole che li collegano. Se troviamo un modo per attraversare tutti gli spigoli da vertice a vertice in modo da visitare ogni spigolo solo una volta, il nostro problema sarà risolto. Proviamo a distribuire i nodi nel diagramma in modo leggermente diverso: Ora possiamo vedere meglio che il nostro grafico è un anello chiuso. Possiamo iniziare la sequenza con qualsiasi parola e sarà la decisione giusta. Tuttavia, la condizione del problema ci dice che qualsiasi soluzione sarà sufficiente. Sostituiamo Vena con Vladimir: vediamo due conseguenze: in primo luogo, abbiamo dovuto aggiungere un nuovo vertice, la lettera P, e in secondo luogo, vediamo che non è più possibile eseguire il looping del nostro grafico. Riassumiamo tutto quanto sopra e introduciamo due nuovi termini: 1. Un grafo connesso i cui archi possono essere attraversati visitandoli ciascuno una sola volta è chiamato grafo contenente un “ cammino euleriano” . Una caratteristica di tale grafo (ad eccezione dell'assenza di vertici senza spigoli) è il grado pari di tutti i vertici tranne due (e solo due). 2. Se risulta possibile ritornare al nodo originale, diciamo che nel grafico è presente un “ciclo Euleriano” . Una caratteristica di tale grafo (ad eccezione dell'assenza di vertici senza spigoli) è il grado pari di tutti i vertici. Immaginiamo il nostro elenco di città in questo modo: {Mosca Anapa Adler Rostov-sul-Don Wuhan}. Costruiamo un grafico: Nel diagramma puoi vedere che questo grafico ha un percorso Euleriano. Ci sono solo due vertici di grado dispari: questi sono M e L, gli altri sono pari: A ha grado 4, perché il ciclo viene contato due volte e P e Y hanno grado 2. Se troviamo un algoritmo in grado di costruire un percorso euleriano basato su questo schema, diciamo sotto forma di una lista {M, A, A, P, Y , L}, allora risolveremo il problema, perché pronunciare le parole in un dato ordine sarà solo una questione di tecnica. Pertanto, la soluzione al nostro problema delle parole del domino si riduce all’implementazione di un algoritmo per trovare un percorso Euleriano (il ciclo è “libero”) in un grafo orientato. Avanti ->
Anche questo è un grafico: 
Se possiamo dire di un bordo che ha una direzione, allora il grafico si chiama orientato : 
I grafici nelle prime due immagini non sono orientati. Possiamo dire di loro che lo spigolo (u, v) è identico allo spigolo (v, u), cioè, ad esempio, gli spigoli (0, 4) e (4, 0) sono lo stesso spigolo. Le frecce sui bordi di un grafico orientato indicano che il bordo (u, v) è un percorso dal vertice u al vertice v e il bordo (v, u) non esiste. Nella terza immagine c'è un bordo (E, A). Non c'è alcun bordo (A, E). Diamo uno sguardo più da vicino all'ultimo disegno. Puoi notare che il vertice F non ha bordi, questo è del tutto possibile. Notiamo anche che vicino al vertice A è apparso un bordo - un anello, e tra i vertici B e D ci sono due bordi orientati diversamente. I grafici diretti consentono tali artefatti. Diciamo che il grafico descrive un gruppo di conoscenti che si scambiano regali. Vediamo che il goloso F non ha regalato nulla a nessuno, B e D si sono scambiati regali (a parte il fatto che ognuno di loro ha fatto un regalo a qualcun altro), e A ha fatto un regalo a se stesso, probabilmente in occasione della risoluzione con successo di un problema problema dal pianeta Caos lineare. A proposito, nota che i vertici del grafico non devono essere numeri o contenere numeri; sono piuttosto contenitori, cioè possono riporre qualsiasi oggetto. Un grafico è una descrizione delle connessioni. Un termine importante che ci sarà utile in seguito: il numero di spigoli attaccati a un vertice (o, come si dice, incidenti ad esso) è chiamato grado di un dato vertice. Ad esempio, nella prima immagine, il vertice 0 ha grado 2, 1 ha grado 4, 3 ha grado 3, il vertice 0 della seconda figura ha grado 1. In questo articolo non approfondiremo la varietà dei diversi tipi di grafici, menzioneremo solo che esistono anche i grafici ponderati, quelli. quelli in cui su ciascun bordo è attaccato un certo numero, che indica il “prezzo” del suo passaggio. I grafi connessi hanno una serie di sottotipi, distinti dalle loro proprietà. Ad esempio, i grafici i cui bordi non formano un ciclo da nessuna parte sono chiamati alberi (hanno famiglie interessanti con nomi fantastici come “alberi rosso-neri”, per esempio) e sono ampiamente utilizzati in una varietà di importanti algoritmi e strutture dati. Usare un grafico per risolvere un problema Tutto questo è molto interessante, dirai, ma cosa c'entra tutto questo con la costruzione di una catena di parole? Si scopre che la cosa più diretta è. Diamo un'occhiata al nostro esempio di prova dalla condizione: { Amsterdam Melbourne New York Kyiv Vienna }. Scriviamo in qualsiasi ordine le lettere "nodali" a cui si aggrappano le parole: {A, M, N, K, B} 
e colleghiamole con le parole. 
Come possiamo vedere, abbiamo un grafo orientato in cui i nodi sono lettere e i bordi sono parole che li collegano. Se troviamo un modo per attraversare tutti gli spigoli da vertice a vertice in modo da visitare ogni spigolo solo una volta, il nostro problema sarà risolto. Proviamo a distribuire i nodi nel diagramma in modo leggermente diverso: 
Ora possiamo vedere meglio che il nostro grafico è un anello chiuso. Possiamo iniziare la sequenza con qualsiasi parola e sarà la decisione giusta. Tuttavia, la condizione del problema ci dice che qualsiasi soluzione sarà sufficiente. Sostituiamo Vena con Vladimir: vediamo 
due conseguenze: in primo luogo, abbiamo dovuto aggiungere un nuovo vertice, la lettera P, e in secondo luogo, vediamo che non è più possibile eseguire il looping del nostro grafico. Riassumiamo tutto quanto sopra e introduciamo due nuovi termini: 1. Un grafo connesso i cui archi possono essere attraversati visitandoli ciascuno una sola volta è chiamato grafo contenente un “ cammino euleriano” . Una caratteristica di tale grafo (ad eccezione dell'assenza di vertici senza spigoli) è il grado pari di tutti i vertici tranne due (e solo due). 2. Se risulta possibile ritornare al nodo originale, diciamo che nel grafico è presente un “ciclo Euleriano” . Una caratteristica di tale grafo (ad eccezione dell'assenza di vertici senza spigoli) è il grado pari di tutti i vertici. Immaginiamo il nostro elenco di città in questo modo: {Mosca Anapa Adler Rostov-sul-Don Wuhan}. Costruiamo un grafico: 
Nel diagramma puoi vedere che questo grafico ha un percorso Euleriano. Ci sono solo due vertici di grado dispari: questi sono M e L, gli altri sono pari: A ha grado 4, perché il ciclo viene contato due volte e P e Y hanno grado 2. Se troviamo un algoritmo in grado di costruire un percorso euleriano basato su questo schema, diciamo sotto forma di una lista {M, A, A, P, Y , L}, allora risolveremo il problema, perché pronunciare le parole in un dato ordine sarà solo una questione di tecnica. Pertanto, la soluzione al nostro problema delle parole del domino si riduce all’implementazione di un algoritmo per trovare un percorso Euleriano (il ciclo è “libero”) in un grafo orientato. Avanti ->
GO TO FULL VERSION