1736, Königsberg. Il fiume Pregelya scorre attraverso la città. Ci sono sette ponti in città, posizionati come mostrato nella figura sopra. Sin dai tempi antichi gli abitanti di Königsberg si sono scontrati con un enigma: è possibile attraversare tutti i ponti camminando su ciascuno una sola volta? Questo problema è stato risolto sia teoricamente, sulla carta, sia in pratica, durante le passeggiate, passando lungo questi stessi ponti. Nessuno è stato in grado di dimostrare che ciò fosse impossibile, ma nessuno avrebbe potuto fare una passeggiata così “misteriosa” sui ponti.

Il famoso matematico Leonhard Euler riuscì a risolvere il problema. Inoltre, ha risolto non solo questo problema specifico, ma ha escogitato un metodo generale per risolvere problemi simili. Nel risolvere il problema dei ponti di Königsberg, Eulero procedette così: “compresse” il terreno in punti e “allungò” i ponti in linee. Viene chiamata una tale figura, composta da punti e linee che collegano questi punti CONTARE.

Un grafico è una raccolta di un insieme non vuoto di vertici e connessioni tra vertici. I cerchi sono chiamati vertici del grafico, le linee con frecce sono archi e le linee senza frecce sono bordi.

Tipi di grafici:

1. Grafico diretto(brevemente digramma) - ai cui bordi è assegnata una direzione.

2. Grafico non orientatoè un grafico in cui non esiste alcuna direzione delle linee.

3. Grafico ponderato– archi o bordi hanno un peso (informazioni aggiuntive).

Risoluzione dei problemi utilizzando i grafici:

Compito 1.

Soluzione: indichiamo gli scienziati come vertici del grafico e tracciamo linee da ciascun vertice ad altri quattro vertici. Otteniamo 10 righe, che saranno considerate strette di mano.

Compito 2.

Nel sito della scuola crescono 8 alberi: melo, pioppo, betulla, sorbo, quercia, acero, larice e pino. Il sorbo è più alto del larice, il melo è più alto dell'acero, la quercia è più bassa della betulla, ma più alta del pino, il pino è più alto del sorbo, la betulla è più bassa del pioppo e il larice è più alto del melo. Disporre gli alberi dal più basso al più alto.

Soluzione:

I vertici del grafico sono alberi, indicati dalla prima lettera del nome dell'albero. Ci sono due relazioni in questo compito: “essere più basso” ed “essere più alto”. Considera la relazione “essere più basso” e disegna le frecce da un albero più basso a uno più alto. Se il problema dice che il sorbo è più alto del larice, allora mettiamo una freccia dal larice al sorbo, ecc. Otteniamo un grafico che mostra che l'albero più basso è l'acero, seguito da melo, larice, sorbo, pino, quercia, betulla e pioppo.

Compito 3.

Natasha ha 2 buste: normale e aerea, e 3 francobolli: rettangolari, quadrati e triangolari. In quanti modi Natasha può scegliere una busta e un francobollo per spedire una lettera?

Soluzione:

Di seguito la suddivisione dei compiti.

ISTITUZIONE EDUCATIVA AUTONOMA COMUNALE SCUOLA SECONDARIA N. 2

Preparato

Legkokonets Vladislav, studente della classe 10A

Applicazione pratica della Teoria dei Grafi

Supervisore

L.I. Noskova, insegnante di matematica

Art. Bryukhovetskaya

2011

1.Introduzione……………..……….………….3

2. Storia dell'emergere della teoria dei grafi……………..………..4

3. Definizioni e teoremi fondamentali della teoria dei grafi…………….………6

4. Problemi risolti utilizzando i grafici……………..……………..8

4.1 Problemi famosi…………….………...8

4.2 Diversi problemi interessanti…………….……………..9

5. Applicazione dei grafici in vari ambiti della vita delle persone……………...11

6. Risoluzione dei problemi…………………..………..………..12

7. Conclusione………………….…………………….13

8. Elenco dei riferimenti………….……………………14

9.Appendice……………………….…………15

introduzione

Nata dalla risoluzione di enigmi e giochi divertenti, la teoria dei grafi è oggi diventata uno strumento semplice, accessibile e potente per risolvere domande relative a una vasta gamma di problemi. I grafici sono letteralmente onnipresenti. Sotto forma di grafici è possibile, ad esempio, interpretare mappe stradali e circuiti elettrici, mappe geografiche e molecole di composti chimici, connessioni tra persone e gruppi di persone. Negli ultimi quattro decenni, la teoria dei grafi è diventata una delle branche della matematica in più rapido sviluppo. Ciò è guidato dalle esigenze di un campo di applicazione in rapida espansione. Viene utilizzato nella progettazione di circuiti integrati e circuiti di controllo, nello studio di automi, circuiti logici, diagrammi a blocchi di programma, in economia e statistica, chimica e biologia, nella teoria della pianificazione. Ecco perché pertinenza L'argomento è determinato, da un lato, dalla popolarità dei grafici e dei relativi metodi di ricerca e, dall'altro, da un sistema olistico non sviluppato per la sua implementazione.

Risolvere molti problemi della vita richiede lunghi calcoli e talvolta anche questi calcoli non portano al successo. Questo è ciò problema di ricerca. La domanda sorge spontanea: è possibile trovare una soluzione semplice, razionale, breve ed elegante per risolverli. La risoluzione dei problemi è più semplice se si utilizzano i grafici? Ciò ha determinato argomento della mia ricerca: “Applicazione pratica della teoria dei grafi”

Scopo La ricerca consisteva nell'utilizzare i grafici per imparare a risolvere rapidamente problemi pratici.

Ipotesi di ricerca. Il metodo del grafico è molto importante e ampiamente utilizzato in vari campi della scienza e dell'attività umana.

Gli obiettivi della ricerca:

1. Studiare la letteratura e le risorse Internet su questo tema.

2.Verificare l'efficacia del metodo dei grafici nella risoluzione di problemi pratici.

3. Trarre una conclusione.

Significato pratico dello studioè che i risultati susciteranno senza dubbio l’interesse di molte persone. Nessuno di voi ha provato a costruire il proprio albero genealogico? Come farlo correttamente? Il capo di un'impresa di trasporti deve probabilmente risolvere il problema di un utilizzo più redditizio dei trasporti durante il trasporto di merci da una destinazione a diversi insediamenti. Ogni scolaretto ha riscontrato problemi logici trasfusionali. Si scopre che possono essere facilmente risolti utilizzando i grafici.

Nel lavoro vengono utilizzati i seguenti metodi: osservazione, ricerca, selezione, analisi.

Storia della teoria dei grafi

Il fondatore della teoria dei grafi è considerato il matematico Leonhard Euler (1707-1783). La storia di questa teoria può essere ripercorsa attraverso la corrispondenza del grande scienziato. Ecco una traduzione del testo latino, tratto dalla lettera di Eulero al matematico e ingegnere italiano Marinoni, inviata da San Pietroburgo il 13 marzo 1736.

“Una volta mi è stato posto un problema su un'isola situata nella città di Königsberg e circondata da un fiume attraversato da sette ponti.

[Appendice Fig.1] La questione è se qualcuno possa aggirarli continuamente, passando solo una volta su ciascun ponte. E poi mi è stato detto che nessuno era ancora riuscito a farlo, ma nessuno aveva dimostrato che fosse impossibile. Questa questione, per quanto banale, mi è sembrata tuttavia degna di attenzione in quanto né la geometria, né l'algebra, né l'arte combinatoria sono sufficienti a risolverla. Dopo aver riflettuto a lungo, ho trovato una regola semplice, basata su una dimostrazione del tutto convincente, con l'aiuto della quale in tutti i problemi di questo tipo è possibile determinare immediatamente se tale deviazione può essere effettuata attraverso un numero qualsiasi di ponti situati o no. I ponti di Koenigsberg sono disposti in modo tale da poter essere rappresentati nella figura seguente [Appendice Fig.2], in cui A denota un'isola e B, C e D - parti del continente separate l'una dall'altra da rami fluviali

Riguardo al metodo da lui scoperto per risolvere problemi di questo tipo, Eulero scrive:

“Questa soluzione, per sua natura, apparentemente ha poco a che fare con la matematica, e non capisco perché ci si dovrebbe aspettare questa soluzione da un matematico piuttosto che da qualunque altra persona, perché questa decisione è supportata dal solo ragionamento, e non esiste Per trovare questa soluzione è necessario coinvolgere qualsiasi legge inerente alla matematica. Quindi, non so come risulti che le questioni che hanno ben poco a che fare con la matematica hanno più probabilità di essere risolte dai matematici che da altri."

Quindi è possibile aggirare i ponti di Königsberg passando solo una volta su ciascuno di questi ponti? Per trovare la risposta, continuiamo la lettera di Eulero a Marinoni:

"La questione è determinare se è possibile aggirare tutti questi sette ponti, attraversandoli una sola volta, oppure no. La mia regola porta alla seguente soluzione a questa domanda. Prima di tutto, devi vedere quante aree ci sono sono, separati dall'acqua - tali che non hanno altro passaggio l'uno dall'altro, eccetto attraverso un ponte. In questo esempio, ci sono quattro di tali sezioni: A, B, C, D. Successivamente, è necessario distinguere se il numero di ponti che portano a queste singole sezioni è pari o dispari. Quindi, nel nostro caso, cinque ponti portano alla sezione A e tre ponti ciascuno al resto, cioè il numero di ponti che portano alle singole sezioni è dispari, e questo da solo è sufficiente per risolvere il problema. Una volta determinato questo, applichiamo la seguente regola: se il numero di ponti che portano a ciascuna tratta separata fosse pari, allora la deviazione in questione sarebbe possibile, e allo stesso tempo sarebbe possibile iniziarla deviazione da qualsiasi tratto. Se però due di questi numeri fossero dispari, perché uno solo non può essere dispari, allora anche allora la transizione potrebbe essere completata, come prescritto, ma certamente solo l'inizio della deviazione dovrà essere preso da uno di quei due tratti a cui conduce un numero dispari di ponti. Se, infine, ci fossero più di due sezioni alle quali conduce un numero dispari di ponti, allora un tale movimento è generalmente impossibile ... se qui si potessero portare altri problemi più seri, questo metodo potrebbe essere di beneficio ancora maggiore e dovrebbe da non trascurare."

Definizioni e teoremi fondamentali della teoria dei grafi

La teoria dei grafi è una disciplina matematica creata dagli sforzi dei matematici, pertanto la sua presentazione include le necessarie definizioni rigorose. Quindi, procediamo con un'introduzione organizzata dei concetti di base di questa teoria.

Definizione 1. Un grafico è una raccolta di un numero finito di punti, chiamati vertici del grafico, e di linee a coppie che collegano alcuni di questi vertici, chiamati bordi o archi del grafico.

Questa definizione può essere formulata diversamente: un grafico è un insieme non vuoto di punti (vertici) e segmenti (spigoli), entrambe le estremità dei quali appartengono a un dato insieme di punti

Di seguito indicheremo i vertici del grafico con le lettere latine A, B, C, D. A volte il grafico nel suo insieme sarà indicato con una lettera maiuscola.

Definizione 2. I vertici di un grafo che non appartengono ad alcun bordo si dicono isolati.

Definizione 3. Un grafo costituito solo da vertici isolati è detto nullo - contare .

Notazione: O "- un grafico con vertici che non ha bordi

Definizione 4. Un grafo in cui ciascuna coppia di vertici è collegata da un arco si dice completo.

Designazione: U" – un grafo costituito da n vertici e spigoli che collegano tutte le possibili coppie di questi vertici. Un grafico di questo tipo può essere rappresentato come un n-gono in cui sono disegnate tutte le diagonali

Definizione 5. Il grado di un vertice è il numero di spigoli a cui appartiene il vertice.

Definizione 6. Un grafo i cui gradi di tutti i k vertici sono uguali è detto grafo dei gradi omogeneo .

Definizione 7. Il complemento di un dato grafo è un grafo costituito da tutti gli spigoli e le loro estremità che devono essere aggiunti al grafo originale per ottenere un grafo completo.

Definizione 8. Un grafo che può essere rappresentato su un piano in modo tale che i suoi bordi si intersechino solo nei vertici è detto planare.

Definizione 9. Un poligono di un grafo planare che non contiene vertici o spigoli del grafo è chiamato faccia.

I concetti di grafico planare e di faccia del grafico vengono utilizzati per risolvere problemi sulla colorazione "corretta" di varie mappe.

Definizione 10. Un percorso da A a X è una sequenza di spigoli che conducono da A a X tale che ogni due spigoli adiacenti abbiano un vertice comune e nessun spigolo si presenti più di una volta.

Definizione 11. Un ciclo è un percorso in cui i punti iniziale e finale coincidono.

Definizione 12. Un ciclo semplice è un ciclo che non passa più di una volta per nessuno dei vertici del grafico.

Definizione 13. Lunghezza del percorso , adagiato su un anello , viene chiamato il numero di spigoli di questo percorso.

Definizione 14. Due vertici A e B in un grafo si dicono connessi (disconnessi) se esiste (non esiste) un percorso che porta da A a B.

Definizione 15. Un grafo si dice connesso se ogni due dei suoi vertici sono connessi; se il grafo contiene almeno una coppia di vertici disconnessi, allora il grafo si dice disconnesso.

Definizione 16. Un albero è un grafo connesso che non contiene cicli.

Un modello tridimensionale di un grafico ad albero è, ad esempio, un vero albero con la sua chioma ramificata in modo intricato; Anche il fiume e i suoi affluenti formano un albero, ma già piatto, sulla superficie della terra.

Definizione 17. Un grafo disconnesso costituito interamente da alberi è chiamato foresta.

Definizione 18. Un albero in cui tutti gli n vertici sono numerati da 1 a n è chiamato albero con vertici rinumerati.

Quindi, abbiamo esaminato le definizioni di base della teoria dei grafi, senza le quali sarebbe impossibile dimostrare teoremi e, di conseguenza, risolvere problemi.

Problemi risolti utilizzando i grafici

Problemi famosi

Problema del commesso viaggiatore

Il problema del commesso viaggiatore è uno dei problemi più famosi della teoria combinatoria. Fu proposta nel 1934 e i migliori matematici si ruppero i denti.

La dichiarazione del problema è la seguente.
Un venditore ambulante (commerciante errante) deve lasciare la prima città, visitare le città 2,1,3..n una volta in un ordine sconosciuto e tornare alla prima città. Le distanze tra le città sono note. In quale ordine si dovrebbe girare per le città affinché il percorso chiuso (tour) di un commesso viaggiatore sia il più breve?

Metodo per risolvere il problema del commesso viaggiatore

Algoritmo goloso “vai alla città più vicina (nella quale non sei ancora entrato)”.
Questo algoritmo è chiamato “avido” perché negli ultimi passaggi devi pagare pesantemente l’avidità.
Consideriamo ad esempio la rete in figura [Appendice Fig.3], che rappresenta uno stretto rombo. Facciamo partire un venditore ambulante dalla città 1. L'algoritmo “vai alla città più vicina” lo porterà alla città 2, poi 3, poi 4; all'ultimo passaggio dovrai pagare la tua avidità, ritornando lungo la lunga diagonale del diamante. Il risultato non sarà il tour più breve, ma il tour più lungo.

Problema sui ponti di Königsberg.

Il problema è formulato come segue.
La città di Koenigsberg si trova sulle rive del fiume Pregel e su due isole. Le diverse parti della città erano collegate da sette ponti. La domenica i cittadini facevano passeggiate per la città. Domanda: è possibile fare una passeggiata in modo tale che, uscendo di casa, si ritorni indietro camminando esattamente una volta su ciascun ponte?
I ponti sul fiume Pregel si trovano come nella foto[Appendice Fig.1].

Considera il grafico corrispondente al diagramma del ponte [Appendice Fig. 2].

Per rispondere alla domanda del problema è sufficiente scoprire se il grafico è euleriano. (Un numero pari di ponti deve estendersi da almeno un vertice). Non puoi passeggiare per la città e attraversare tutti i ponti una volta e tornare indietro.

Diversi compiti interessanti

1. "Percorsi".

Problema 1

Come ricorderete, il cacciatore di anime morte Chichikov visitò una volta ciascuno i famosi proprietari terrieri. Li ha visitati nel seguente ordine: Manilov, Korobochka, Nozdryov, Sobakevich, Plyushkin, Tentetnikov, il generale Betrishchev, Petukh, Konstanzholgo, il colonnello Koshkarev. È stato trovato un diagramma sul quale Chichikov ha abbozzato le posizioni relative delle tenute e delle strade di campagna che le collegano. Determina quale tenuta appartiene a chi, se Chichikov non ha guidato nessuna delle strade più di una volta [Appendice Fig. 4].

Soluzione:

La mappa stradale mostra che Chichikov ha iniziato il suo viaggio dalla tenuta E e si è concluso con la tenuta O. Notiamo che solo due strade portano alle tenute B e C, quindi Chichikov ha dovuto percorrere queste strade. Contrassegniamoli con una linea in grassetto. Sono stati individuati tratti del percorso passanti per A: AC e AB. Chichikov non ha viaggiato sulle strade AE, AK e AM. Cancelliamoli. Segnaliamo con una linea in grassetto ED; Cancelliamo DK. Cancelliamo MO e MN; Segniamo con una linea in grassetto MF; cancellare FO; Contrassegniamo FH, NK e KO con una linea in grassetto. Troviamo l'unico percorso possibile in queste condizioni. E otteniamo: tenuta E - appartiene a Manilov, D - Korobochka, C - Nozdryov, A - Sobakevich, B - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [Appendice Fig.5].

Problema 2

La figura mostra una mappa della zona [Appendice Fig. 6].

Puoi muoverti solo nella direzione delle frecce. Puoi visitare ciascun punto non più di una volta. In quanti modi puoi andare dal punto 1 al punto 9? Quale percorso è il più breve e quale è il più lungo.

Soluzione:

“Stratfichiamo” sequenzialmente il circuito in un albero, a partire dal vertice 1 [Appendice Fig.7]. Prendiamo un albero. Il numero di modi possibili per arrivare da 1 a 9 è uguale al numero di vertici “pendenti” dell'albero (ce ne sono 14). Ovviamente il percorso più breve è 1-5-9; il più lungo è 1-2-3-6-5-7-8-9.

2 "Gruppi, incontri"

Problema 1

I partecipanti al festival musicale, dopo essersi incontrati, si sono scambiati buste con indirizzi. Prova che:

a) siano state consegnate un numero pari di buste;

b) il numero dei partecipanti che si sono scambiati le buste un numero dispari di volte è pari.

Soluzione: lascia che i partecipanti al festival siano A 1, A 2, A 3. . . , E n sono i vertici del grafico, e gli archi collegano coppie di vertici che rappresentano i ragazzi che si scambiano gli inviluppi [Appendice Fig.8]

Soluzione:

a) il grado di ciascun vertice A i indica il numero di buste che il partecipante A i ha consegnato ai suoi amici. Il numero totale di inviluppi trasmessi N è pari alla somma dei gradi di tutti i vertici del grafo N = grado. Un passo 1+. A2 + + . . . + passo. A n -1 + grado. E n, N =2p, dove p è il numero di archi del grafico, cioè N – pari. Di conseguenza è stato consegnato un numero pari di buste;

b) nell'uguaglianza N = grado. Un passo 1+. A2 + + . . . + passo. A n -1 + grado. E n la somma dei termini dispari deve essere pari, e questo può avvenire solo se il numero dei termini dispari è pari. Ciò significa che il numero di partecipanti che si sono scambiati le buste un numero dispari di volte è pari.

Problema 2

Un giorno Andrei, Boris, Volodya, Dasha e Galya decisero di andare al cinema la sera. Hanno deciso di coordinare telefonicamente la scelta del cinema e dello spettacolo. È stato inoltre deciso che se non fosse stato possibile contattare qualcuno telefonicamente, la gita al cinema sarebbe stata annullata. La sera non tutti si sono riuniti al cinema e quindi la visita al cinema è stata annullata. Il giorno dopo iniziarono a scoprire chi aveva chiamato chi. Si è scoperto che Andrey chiamava Boris e Volodya, Volodya chiamava Boris e Dasha, Boris chiamava Andrey e Dasha, Dasha chiamava Andrey e Volodya e Galya chiamava Andrey, Volodya e Boris. Chi non ha potuto telefonare e quindi non è venuto all'incontro?

Soluzione:

Disegniamo cinque punti ed etichettiamoli con le lettere A, B, C, D, D. Queste sono le prime lettere dei nomi. Uniamo i punti che corrispondono ai nomi dei ragazzi che hanno chiamato.

[Appendice Fig.9]

Dalla foto è chiaro che ciascuno dei ragazzi - Andrey, Boris e Volodya - ha telefonato a tutti gli altri. Ecco perché questi ragazzi sono venuti al cinema. Ma Galya e Dasha non sono riuscite a mettersi in contatto al telefono (i punti G ed E non sono collegati da un segmento di linea) e quindi, secondo l'accordo, non sono venute al cinema.

Applicazione dei grafici in vari ambiti della vita delle persone

Oltre agli esempi forniti, i grafici sono ampiamente utilizzati nell'edilizia, nell'ingegneria elettrica, nella gestione, nella logistica, nella geografia, nell'ingegneria meccanica, nella sociologia, nella programmazione, nell'automazione dei processi tecnologici e della produzione, nella psicologia e nella pubblicità. Quindi, da tutto quanto sopra, segue inconfutabilmente il valore pratico della teoria dei grafi, la cui dimostrazione era l'obiettivo di questo studio.

In qualsiasi campo della scienza e della tecnologia si incontrano grafici. I grafici sono meravigliosi oggetti matematici con cui puoi risolvere problemi matematici, economici e logici, vari enigmi e semplificare le condizioni di problemi di fisica, chimica, elettronica e automazione. Molti fatti matematici possono essere convenientemente formulati nel linguaggio dei grafici. La teoria dei grafi fa parte di molte scienze. La teoria dei grafi è una delle teorie matematiche più belle e visive. Recentemente, la teoria dei grafi sta trovando sempre più applicazioni nelle questioni applicate. È emersa anche la chimica computazionale, un campo della chimica relativamente giovane basato sull'applicazione della teoria dei grafi.

Grafici molecolari, utilizzati nella stereochimica e nella topologia strutturale, nella chimica dei cluster, dei polimeri, ecc., sono grafici non orientati che mostrano la struttura delle molecole [Appendice Fig. 10]. I vertici e i bordi di questi grafici corrispondono ai corrispondenti atomi e ai legami chimici tra loro.

Grafici e alberi molecolari: [Appendice Fig. 10] a, b - multigrafi, rispettivamente. etilene e formaldeide; dicono isomeri del pentano (gli alberi 4, 5 sono isomorfi all'albero 2).

Nella stereochimica degli organismi soprattutto. Vengono spesso utilizzati alberi molecolari: gli alberi principali dei grafi molecolari, che contengono solo tutti i vertici corrispondenti agli atomi di C. Compilazione di insiemi di mol. gli alberi e la determinazione del loro isomorfismo permettono di determinare ciò che dicono. strutture e trovare il numero totale di isomeri di alcani, alcheni e alchini

Reti proteiche

Le reti proteiche sono gruppi di proteine ​​che interagiscono fisicamente e funzionano insieme e in modo coordinato in una cellula, controllando i processi interconnessi che si verificano nel corpo [allegato fig. undici].

Grafico del sistema gerarchico chiamato albero. Una caratteristica distintiva di un albero è che esiste un solo percorso tra due qualsiasi dei suoi vertici. L'albero non contiene cicli o loop.

Tipicamente, un albero che rappresenta un sistema gerarchico ha un vertice principale, chiamato radice dell'albero. Ogni vertice dell'albero (eccetto la radice) ha un solo antenato: l'oggetto da esso designato è incluso in una classe di livello superiore. Qualsiasi vertice di un albero può generare diversi discendenti: vertici corrispondenti a classi del livello inferiore.

Per ogni coppia di vertici dell'albero esiste un percorso unico che li collega. Questa proprietà viene utilizzata quando si trovano tutti gli antenati, ad esempio, in linea maschile, di qualsiasi persona il cui pedigree è rappresentato sotto forma di un albero genealogico, che è un “albero” nel senso della teoria dei grafi.

Esempio del mio albero genealogico [Appendice Fig. 12].

Un altro esempio. L'immagine mostra l'albero genealogico biblico [Appendice Fig. 13].

Risoluzione dei problemi

1. Compito di trasporto. Lascia che ci sia una base nella città di Krasnodar con materie prime che devono essere distribuite alle città di Krymsk, Temryuk, Slavyansk-on-Kuban e Timashevsk in un viaggio, spendendo meno tempo e carburante possibile e tornando a Krasnodar .

Soluzione:

Innanzitutto, creiamo un grafico di tutti i possibili percorsi di viaggio [Appendice Fig.14], tenendo conto delle strade reali tra questi insediamenti e della distanza tra loro. Per risolvere questo problema, dobbiamo creare un altro grafico, ad albero [Appendice Fig.15].

Per comodità della soluzione, designiamo le città con numeri: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

Il risultato sono 24 soluzioni, ma abbiamo bisogno solo dei percorsi più brevi. Di tutte le soluzioni solo due sono soddisfacenti, si tratta di 350 km.

Allo stesso modo è possibile e, credo, necessario calcolare il trasporto reale da una località all'altra.

Problema logico che coinvolge la trasfusione. Il secchio contiene 8 litri d'acqua e ci sono due pentole con una capacità di 5 e 3 litri. devi versare 4 litri di acqua in una padella da cinque litri e lasciare 4 litri nel secchio, ad es. versare l'acqua equamente nel secchio e in una padella grande.

Soluzione:

La situazione in qualsiasi momento può essere descritta da tre numeri [Appendice Fig. 16].

Di conseguenza, otteniamo due soluzioni: una in 7 mosse, l'altra in 8 mosse.

Conclusione

Quindi, per imparare a risolvere i problemi, è necessario capire cosa sono, come sono strutturati, da quali componenti sono costituiti, quali sono gli strumenti con cui si risolvono i problemi.

Risolvendo problemi pratici utilizzando la teoria dei grafi, è diventato chiaro che in ogni passaggio, in ogni fase della loro soluzione, è necessario applicare la creatività.

Fin dall'inizio, nella prima fase, sta nel fatto che è necessario essere in grado di analizzare e codificare la condizione del problema. La seconda fase è una notazione schematica, che consiste in una rappresentazione geometrica dei grafici, e in questa fase l'elemento della creatività è molto importante perché non è facile trovare corrispondenze tra gli elementi della condizione e i corrispondenti elementi della grafico.

Mentre risolvevo un problema di trasporto o il compito di redigere un albero genealogico, sono giunto alla conclusione che il metodo del grafico è sicuramente interessante, bello e visivo.

Mi sono convinto che i grafici siano ampiamente utilizzati in economia, management e tecnologia. La teoria dei grafi viene utilizzata anche nella programmazione, ma questo non è stato discusso in questo lavoro, ma penso che sia solo questione di tempo.

Questo lavoro scientifico esamina i grafici matematici, le loro aree di applicazione e risolve diversi problemi utilizzando i grafici. La conoscenza delle basi della teoria dei grafi è necessaria in vari ambiti legati alla produzione e alla gestione aziendale (ad esempio, pianificazione della costruzione della rete, pianificazione della consegna della posta). Inoltre, mentre lavoravo a un articolo scientifico, ho imparato a lavorare su un computer utilizzando l'editor di testo WORD. Gli obiettivi del lavoro scientifico sono quindi stati completati.

Quindi, da tutto quanto sopra, segue inconfutabilmente il valore pratico della teoria dei grafi, la cui dimostrazione era l'obiettivo di questo lavoro.

Letteratura

Berge K. Teoria dei grafi e sue applicazioni. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J. Introduzione alla matematica finita. -M.: IIL, 1963.

Ore O. Grafici e loro applicazione. -M.: Mir, 1965.

Harari F. Teoria dei grafi. -M.: Mir, 1973.

Zykov A.A. Teoria dei grafi finiti. -Novosibirsk: Scienza, 1969.

Beresina L.Yu. Grafici e loro applicazione. -M.: Educazione, 1979. -144 p.

"Soros Educational Journal" n. 11 1996 (articolo "Grafici piatti");

Gardner M. "Mathematical leisure", M. "World", 1972 (capitolo 35);

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. “Vecchi problemi di intrattenimento”, M. “Science”, 1988 (parte 2, sezione 8; appendice 4);

Applicazione

Applicazione

P

Riso. 6

Riso. 7

Riso. 8

applicazione

Applicazione

Applicazione

Applicazione

P

Riso. 14

applicazione

Applicazione

Tra i problemi associati alla risoluzione dei problemi logici, l'attenzione dei ricercatori negli ultimi anni è stata attratta dalla questione dell'applicazione della teoria dei grafi a questo tipo di problemi.

La teoria dei grafi è attualmente una branca della matematica discreta in intenso sviluppo. Ciò è spiegato dal fatto che molti oggetti e situazioni sono descritti sotto forma di modelli grafici: reti di comunicazione, circuiti di dispositivi elettrici ed elettronici, molecole chimiche, relazioni tra persone e molto altro.

Le attività grafiche presentano una serie di vantaggi che consentono di utilizzarle per sviluppare l'immaginazione e migliorare il pensiero logico. I problemi con i grafici possono essere presentati in una forma divertente e giocosa.

Oggetto della ricerca in questo lavoro c'è la soluzione di problemi logici utilizzando i grafici.

Scopo dello studio: applicare l'apparato grafico per risolvere problemi logici.

Ipotesi: A nostro avviso, risolvere molti problemi logici richiederà meno lavoro, per questo utilizzeremo la teoria dei grafi.

Gli obiettivi della ricerca:

considerare la risoluzione dei problemi utilizzando i grafici;

imparare a tradurre i problemi nel linguaggio dei grafici;

confrontare i metodi tradizionali di risoluzione dei problemi con i metodi della teoria dei grafi.

Nel 1736, il grande matematico Leonhard Euler trovò la soluzione a un enigma chiamato Problema del ponte di Königsberg. Il fiume Pregel, che scorre attraverso Kaliningrad (in passato la città si chiamava Königsberg) bagna due isole (Fig. Figura 1 Figura 1). Ai tempi di Eulero, le rive del fiume e le isole erano collegate da ponti, come mostrato in figura. Il puzzle richiedeva di trovare un percorso che attraversasse tutte e quattro le masse continentali una volta, e la fine e l'inizio del percorso dovevano coincidere.

Immagine 1

L. Euler ha dimostrato che non esiste un percorso che soddisfi le condizioni del puzzle e ha sviluppato una teoria per risolvere questo tipo di puzzle. Conoscendo il materiale della parte introduttiva del corso "Introduzione ai grafici", non è difficile riprodurre l'idea del ragionamento di L. Euler. Per fare ciò, devi prima sostituire la Figura 1 con il diagramma mostrato in Figura 2, dove le isole e le coste sono rappresentate da punti.

figura 2

Il diagramma mostrato nella Figura 2 non è, in senso stretto, un grafico: ha più bordi. Tuttavia, l’anno 1736, quando questo enigma fu risolto, è generalmente considerato l’anno in cui è nata la teoria dei grafi.

Più di cento anni dopo, nel 1874, lo scienziato tedesco G. Kirchhoff sviluppò un metodo efficace per determinare il valore della corrente in un circuito elettrico, utilizzando metodi e concetti che in seguito ricevettero diritti di cittadinanza nella teoria dei grafi. Altri 10 anni dopo, il matematico inglese A. Keli (sua madre era russa, parlava russo e seguiva la letteratura matematica russa; era tra quei pochi matematici che fin dall'inizio compresero e sostenevano le idee di N.I. Lobachevskij) sviluppò la teoria di alberi per contare il numero di isomeri di idrocarburi saturi con un dato numero N atomi di carbonio.

In matematica, un grafico è un insieme finito di punti chiamati vertici; quali di essi sono collegati tra loro da linee chiamate bordi del grafico.

Un grafico è un insieme di punti raffigurati su un piano (foglio di carta, tavola), alcune coppie dei quali sono collegate da linee. I punti sono chiamati vertici del grafico, le linee sono chiamate bordi. Il grado di un vertice è il numero di spigoli che emergono dal vertice.

Quando guardi una carta geografica, la rete ferroviaria attira immediatamente la tua attenzione. Questo è un tipico grafo: i cerchi rappresentano le stazioni che sono i vertici del grafico, e i percorsi che li collegano rappresentano i bordi.

Figura 3

Il grafico in Fig. Figura 3 mostra un diagramma delle strade tra i villaggi M, A, B, C e D. Qui, ogni due vertici sono collegati da un bordo. Un grafico di questo tipo si dice completo. I numeri nella figura indicano le distanze tra i villaggi lungo queste strade. Supponiamo che ci sia un ufficio postale nel villaggio M e il postino debba consegnare le lettere agli altri quattro villaggi. Esistono molti percorsi di viaggio diversi. Come scegliere quello più corto? Il modo più semplice è analizzare tutte le opzioni. Un nuovo grafico ti aiuterà a farlo, rendendo più facile vedere i possibili percorsi. La vetta M in alto è l'inizio delle vie. Da lì puoi iniziare il viaggio in quattro modi diversi: verso A, verso B, verso C o verso D. Dopo aver visitato uno dei villaggi, ci sono tre opzioni per continuare il percorso, poi due, poi la strada fino all'ultimo villaggio e ancora a M. Totale 43 21  24 modi.

Problemi simili sorgono spesso quando si trovano le migliori opzioni per la distribuzione delle merci ai negozi e dei materiali ai cantieri.

Consideriamo uno dei problemi più semplici: “Le matite rosse, blu, gialle e verdi sono in quattro scatole, una alla volta. Il colore della matita è diverso dal colore della scatola. È noto che la matita verde si trova nella scatola blu, ma la matita rossa non è nella scatola gialla. In quale scatola arriva ogni matita?"

Indichiamo matite e scatole con punti. Una linea continua indicherà che la matita si trova nella casella corrispondente, mentre una linea tratteggiata indicherà che non lo è. Quindi, tenendo conto del problema, abbiamo G 1 (Fig. Figura 4).

Figura 4

Successivamente, completiamo il grafico secondo la seguente regola: poiché nella scatola può trovarsi esattamente una matita, da ciascun punto dovrebbero uscire una linea continua e tre tratteggiate. Il risultato è un grafico G 2 , che dà una soluzione al problema.

Quando risolvono problemi che di solito vengono chiamati logici nella scienza popolare e nella letteratura metodologica, di regola, non fanno affidamento in modo significativo sulle conoscenze e abilità scolastiche. A questo proposito, sono tradizionalmente considerati una misura dell'ingegno, un indicatore del livello di abilità matematiche, acutezza di pensiero, capacità di usare la memoria e sono spesso discussi nei club di matematica scolastica.

Risolvere molti problemi logici utilizzando i grafici è abbastanza accessibile agli studenti più giovani. Per fare ciò è sufficiente che abbiano solo una comprensione intuitiva dei grafici e delle loro proprietà più evidenti.

Diamo un'occhiata ad esempi di utilizzo dei grafici per risolvere alcuni problemi ben noti. In questo caso, rappresenteremo gli oggetti tramite punti e le relazioni tra loro tramite segmenti (le posizioni dei punti e le lunghezze dei segmenti sono arbitrarie).

Il chiarimento delle strutture dei problemi logici dal punto di vista dei metodi di soluzione applicati consente di isolare alcune classi di tali problemi.

Compito 1. Tre amici stanno parlando: Belokurov, Chernov e Ryzhov. La bruna ha detto a Belokurov: "È curioso che uno di noi sia biondo, un altro sia bruno, il terzo sia rosso, ma il colore dei capelli di nessuno corrisponde al loro cognome". Che colore di capelli ha ciascuno dei tuoi amici?

Diamo una soluzione dettagliata. Costruiamo un grafico della relazione specificata nella dichiarazione del problema. Per fare questo, innanzitutto, evidenziamo molti cognomi M e molti colori di capelli A, i cui elementi saranno indicati da punti. Punti prefissati M chiamiamoli le lettere B, Ch, R (Belokurov, Chernov e Ryzhov); punti del secondo set - b, br, p (biondo, bruno, rosso). Se un punto di un insieme corrisponde a un punto di un altro, li collegheremo con una linea continua e, se non corrisponde, li collegheremo con una linea tratteggiata. La condizione del problema indica solo incongruenze, quindi dovrebbe apparire prima il grafico mostrato nella Figura 5.

Figura 5

Dalle condizioni del problema ne consegue che per ogni punto dell'insieme M c'è uno e solo un tonka tra i tanti A, che corrisponde al primo e, viceversa, a ciascun punto dell'insieme A corrisponde ad uno ed un solo punto dell'insieme M. Il compito si riduce a trovare questa unica possibile corrispondenza tra gli elementi degli insiemi M E A, cioè trovare tre linee continue che collegano i punti corrispondenti degli insiemi.

Il principio per risolvere il problema è semplice. Se un punto è collegato a due punti di un altro insieme tramite linee tratteggiate, allora deve essere collegato al suo terzo punto tramite una linea continua. Pertanto, il grafico in Figura 5 è integrato con linee continue che collegano i punti B e p, P e b (Figura 6).

Figura 7

Pertanto, nel grafico di questa figura leggiamo automaticamente la risposta: Belokurov ha i capelli rossi, Chernov è biondo, Ryzhov è bruna. La stessa tecnica può essere utilizzata per risolvere, ad esempio, i problemi 2 e 3.

Compito 2. Per Vanya, Kolya e Misha venivano cotte torte: una con cavolo, un'altra con riso, la terza con mele. A Misha non piace la torta di mele e non la mangia con il cavolo. A Vanja non piace la torta di cavoli. Chi mangia quale torta?

Compito 3. Tre amici lavorano nella stessa fabbrica: un meccanico, un tornitore e un saldatore. I loro cognomi sono Borisov, Ivanov e Semenov. Il fabbro non ha fratelli né sorelle, è il più giovane dei suoi amici. Semenov, sposato con la sorella di Borisov, è più vecchio del tornitore. Come si chiamano il meccanico, il tornitore e il saldatore?

I problemi di cui sopra possono essere risolti con successo utilizzando le tabelle. Questo metodo o le sue modifiche sono raccomandati e discussi in molti libri scientifici e sussidi didattici popolari. È possibile, tuttavia, indicare classi di problemi in cui l'uso di grafici rappresentati da punti e segmenti risulta più conveniente e giustificato. L'utilizzo del metodo delle tabelle come quelle dei tornei o delle loro generalizzazioni nelle decisioni costringe una parte importante del ragionamento a essere svolta “oralmente”. Allo stesso tempo, devi tornare ripetutamente alle condizioni del problema, ai risultati intermedi, ricordare molto e utilizzare le informazioni ricevute al momento giusto. Questo tipo di problema include problemi con tre o più insiemi di oggetti in esame.

Compito 4. Tre compagni - Ivan, Dmitry e Stepan - insegna varie materie (chimica, biologia, fisica) nelle scuole di Mosca, Leningrado e Kiev. Conosciuto:

1. Ivan non lavora a Mosca e Dmitry non lavora a Leningrado;

2. Moskvich non insegna fisica;

3. Quello che lavora a Leningrado insegna chimica;

4. Dmitry non insegna biologia.

Quale materia e in quale città insegna ciascuno dei compagni?

Soluzione. Distinguiamo tre insiemi: un insieme di nomi, un insieme di oggetti e un insieme di città. Un elemento di ciascuno degli insiemi della Figura 4 è dato dal proprio punto (le lettere in questa figura sono le prime lettere delle parole corrispondenti). Se due punti di insiemi diversi caratterizzano le caratteristiche di persone diverse, collegheremo tali punti con una linea tratteggiata. Se due punti di insiemi diversi corrispondono alle caratteristiche di una persona, collegheremo tali punti a coppie con linee continue. È importante che, a seconda delle condizioni del problema, per ogni punto di qualsiasi insieme in ciascuno degli altri insiemi ci sia uno e un solo punto ad esso corrispondente.

Figura 8

Pertanto, il grafico in Figura 8 contiene tutti gli elementi degli insiemi specificati nella condizione e le relazioni tra loro. Nel linguaggio dei grafici il problema si riduce a trovare tre triangoli “solidi” con vertici in insiemi diversi.

Consideriamo il grafico di Figura 8. Il segmento tratteggiato XD viene da sé, infatti A corrisponde a X e, allo stesso tempo, A non corrisponde a D, cioè X non può corrispondere a D. Quindi, una tipica operazione sul grafico per questo viene utilizzato un tipo di problema: se il triangolo con vertici in tre insiemi diversi, un lato è solido, il secondo è tratteggiato, quindi il terzo deve essere tratteggiato. Dalle condizioni del problema ne consegue che un'altra operazione sul grafico è uniforme: se un punto è collegato da segmenti tratteggiati a due punti del secondo insieme, allora dovrebbe essere collegato al terzo punto di questo insieme da un segmento solido. Ecco come viene disegnato un segmento continuo del DF. Successivamente, disegna il segmento tratteggiato DM (nel triangolo DFM il lato DF è solido e FM è tratteggiato), DK è solido (DM e DL sono tratteggiati), ora colleghiamo i punti F e K con un segmento solido. Se in un triangolo con vertici in insiemi diversi due lati sono solidi, anche il terzo sarà solido. È stato trovato il primo triangolo “solido” DFK. Quindi, senza tornare al testo del problema, guidati solo dalle naturali operazioni sul grafico sopra descritte, troviamo una soluzione (Fig. 9).

Figura 9

Notiamo la sequenza in cui sono stati effettuati i segmenti: HD, DF, DM, DK, FC, MS, IL, CI, BM, BS. I vertici di ciascuno dei tre triangoli “solidi” risultanti determinano la risposta al problema: Ivan insegna chimica a Leningrado, Dmitrij insegna fisica a Kiev e Stepan insegna biologia a Mosca.

Nel seguente problema l'uso dei grafici aiuta a rilevare la presenza di due soluzioni.

Compito 5. Masha, Lida, Zhenya e Katya sanno suonare diversi strumenti (violoncello, pianoforte, chitarra e violino), ma ciascuna solo su uno e parlano anche diverse lingue straniere (inglese, francese, tedesco e spagnolo), ma ciascuna solo su uno . E 'noto :

1. la ragazza che suona la chitarra parla spagnolo;

2. Lida non suona né il violino né il violoncello e non conosce l'inglese;

3. Masha non suona né il violino né il violoncello e non conosce l'inglese;

4. una ragazza che parla tedesco non suona il violoncello;

5. Zhenya conosce il francese, ma non suona il violino.

Chi suona quale strumento e quale lingua straniera conosce?

Le condizioni problematiche corrispondono al grafico mostrato nella Figura 10.

Figura 10

La notazione e il principio della soluzione qui sono gli stessi del problema 4. Disegniamo in sequenza i seguenti segmenti solidi: KS, VZH, VF, AK (Fig. 11).

Figura 11

Si formano così due triangoli “solidi” ZHVF e KSA. Eseguiamo un altro segmento continuo del veicolo di lancio. Ora siamo convinti che le condizioni del problema non assicurano la scelta univoca del terzo punto per ciascuna delle coppie di RN e GI. Sono possibili le seguenti opzioni per i triangoli “solidi”: MGI e OSR oppure LGI e MRN. Pertanto, il problema ha due soluzioni.

Presentiamo un problema in cui il grafico consente di rilevare abbastanza facilmente la ridondanza di una condizione.

Compito 6. Al torneo di scacchi hanno preso parte sei soci di diverse professioni: un tornitore, un meccanico, un ingegnere, un insegnante, un medico e un autista. Conosciuto:

1. nel primo turno Andreev ha giocato con il dottore, l'insegnante con Borisov e Grigoriev con Evdokimov;

2. nel secondo turno Dmitriev ha giocato con il Turner e il dottore con Borisov;

3. nel terzo turno Evdokimov ha giocato con un ingegnere;

4. alla fine del torneo i posti sono stati distribuiti così: BorisovIOposto, Grigoriev e l'ingegnere condiviseroIIEIIIposti, Dmitriev ha presoIVposto, e Zolotarev e il meccanico si sono divisi il quinto e il sesto posto.

Quali professioni avevano Grigoriev, Dmitriev ed Evdokimov?

Il testo dell'opera è pubblicato senza immagini e formule.
La versione completa dell'opera è disponibile nella scheda "File di lavoro" in formato PDF

INTRODUZIONE

“In matematica non sono le formule che vanno ricordate, ma il processo di pensare...”

E. I. Ignatiev

La teoria dei grafi è attualmente una branca della matematica in intenso sviluppo. Ciò è spiegato dal fatto che molti oggetti e situazioni sono descritti sotto forma di modelli grafici, il che è molto importante per il normale funzionamento della vita sociale. È questo fattore che determina la rilevanza del loro studio più dettagliato. Pertanto, l'argomento di questo lavoro è abbastanza rilevante.

Bersaglio lavoro di ricerca: scoprire le caratteristiche dell'applicazione della teoria dei grafi in vari campi della conoscenza e nella risoluzione di problemi logici.

L'obiettivo ha individuato quanto segue compiti:

conoscere la storia della teoria dei grafi;

studiare i concetti base della teoria dei grafi e le principali caratteristiche dei grafi;

mostrare l'applicazione pratica della teoria dei grafi in vari campi della conoscenza;

Considera i modi per risolvere i problemi utilizzando i grafici e crea i tuoi problemi.

Un oggetto ricerca: la sfera dell'attività umana per l'applicazione del metodo dei grafici.

Articolo Ricerca: sezione di matematica “Teoria dei grafi”.

Ipotesi. Ipotizziamo che l'apprendimento della teoria dei grafi possa aiutare gli studenti a risolvere problemi logici in matematica, che daranno forma ai loro interessi futuri.

Metodi lavoro di ricerca:

Durante la nostra ricerca sono stati utilizzati i seguenti metodi:

1) Lavorare con varie fonti di informazione.

2) Descrizione, raccolta, sistematizzazione del materiale.

3) Osservazione, analisi e confronto.

4) Preparazione dei compiti.

Significato teorico e pratico Questo lavoro è determinato dal fatto che i risultati possono essere utilizzati in informatica, matematica, geometria, disegno e insegnamento in classe, nonché per un'ampia gamma di lettori interessati a questo argomento. Il lavoro di ricerca ha un chiaro orientamento pratico, poiché nel lavoro l'autore presenta numerosi esempi di utilizzo dei grafici in molti campi della conoscenza e ha elaborato i propri compiti. Questo materiale può essere utilizzato nelle lezioni facoltative di matematica.

CAPITOLO I. REVISIONE TEORICA DEL MATERIALE SUL TEMA DELLA RICERCA

1. Teoria dei grafi. Concetti basilari

In matematica, un “grafico” può essere rappresentato come un’immagine, che rappresenta un numero di punti collegati da linee. "Conte" deriva dalla parola latina "graphio" - scrivo, come un noto titolo nobiliare.

In matematica, la definizione di grafico è data come segue:

Il termine "grafico" in matematica è definito come segue:

Grafico - questo è un insieme finito di punti - picchi, che possono essere collegati tramite linee - costolette .

Esempi di grafici includono disegni di poligoni, circuiti elettrici, rappresentazioni schematiche di compagnie aeree, metropolitane, strade, ecc. Un albero genealogico è anche un grafico, in cui i vertici sono i membri del clan e i legami familiari fungono da bordi del grafico.

Riso. 1 Esempi di grafici

Viene chiamato il numero di spigoli che appartengono a un vertice grado del vertice del grafico . Se il grado di un vertice è un numero dispari, il vertice si chiama - strano . Se il grado di un vertice è un numero pari, allora viene chiamato vertice Anche.

Riso. 2 vertice del grafico

Grafico nullo è un grafo costituito solo da vertici isolati che non sono collegati da bordi.

Grafico completo è un grafo in cui ogni coppia di vertici è collegata da un bordo. Un N-gon, in cui sono disegnate tutte le diagonali, può servire come esempio di grafico completo.

Se si sceglie un percorso in un grafico in cui i punti iniziale e finale coincidono, viene chiamato tale percorso ciclo del grafico . Se ogni vertice del grafico viene attraversato al massimo una volta, allora ciclo chiamato semplice .

Se ogni due vertici in un grafico sono collegati da un bordo, allora questo collegato grafico. Il grafico si chiama non correlato , se contiene almeno una coppia di vertici non collegati.

Se un grafo è connesso ma non contiene cicli, viene chiamato tale grafo albero .

1. Caratteristiche dei grafici

Il Sentiero del Conte è una sequenza in cui ogni due bordi adiacenti che condividono un vertice comune si verificano solo una volta.

Lunghezza della catena più corta di vertici UN e b viene chiamato distanza tra le cime UN e B.

Vertice UN chiamato centro grafico, se la distanza tra i vertici UN e ogni altro vertice è il più piccolo possibile. C'è una tale distanza raggio grafico.

Viene chiamata la massima distanza possibile tra due vertici qualsiasi di un grafico diametro grafico.

Colorazione e applicazione del grafico.

Se guardi attentamente una mappa geografica, puoi vedere ferrovie o autostrade, che sono grafici. Inoltre, sulla mappa è presente un grafico che comprende i confini tra i paesi (distretti, regioni).

Nel 1852, allo studente inglese Francis Guthrie fu affidato il compito di colorare una mappa della Gran Bretagna, evidenziando ciascuna contea con un colore separato. A causa della piccola selezione di colori, Guthrie li ha riutilizzati. Ha selezionato i colori in modo che le contee che condividevano una sezione comune del confine fossero necessariamente dipinte in colori diversi. È sorta la domanda su quale sia la quantità minima di vernice necessaria per colorare varie mappe. Francis Guthrie suggerì, sebbene non potesse dimostrarlo, che quattro colori sarebbero stati sufficienti. Questo problema è stato oggetto di accese discussioni negli ambienti studenteschi, ma in seguito è stato dimenticato.

Il "problema dei quattro colori" suscitò crescente interesse, ma non fu mai risolto, nemmeno da eminenti matematici. Nel 1890, il matematico inglese Percy Heawood dimostrò che cinque colori sarebbero sufficienti per colorare qualsiasi mappa. Solo nel 1968 si riuscì a dimostrare che 4 colori sarebbero sufficienti per colorare una mappa che raffigura meno di quaranta paesi.

Nel 1976, questo problema fu risolto utilizzando un computer da due matematici americani Kenneth Appel e Wolfgangt Haken. Per risolverlo, tutte le carte sono state divise in 2000 tipi. È stato creato un programma per computer che esaminava tutti i tipi per identificare le carte per le quali quattro colori non sarebbero sufficienti per colorare. Il computer non poteva studiare solo tre tipi di mappe, quindi i matematici le studiarono da soli. Di conseguenza, si è scoperto che 4 colori sarebbero sufficienti per colorare tutti i 2000 tipi di carte. Hanno annunciato una soluzione al problema dei quattro colori. In questo giorno, l’ufficio postale dell’università dove lavoravano Appel e Haken ha apposto su tutti i francobolli un francobollo con la scritta: “Quattro colori sono sufficienti”.

Puoi immaginare il problema dei quattro colori in modo leggermente diverso.

Per fare ciò, considera una mappa arbitraria, presentandola sotto forma di un grafico: le capitali degli stati sono i vertici del grafico, e i bordi del grafico collegano quei vertici (capitali) i cui stati hanno un confine comune. Per ottenere un grafo del genere si formula il seguente problema: è necessario colorare il grafo utilizzando quattro colori in modo che i vertici che hanno uno spigolo comune siano colorati con colori diversi.

Grafici di Eulero e Hamiltoniani

Nel 1859, il matematico inglese William Hamilton pubblicò un puzzle: un dodecaedro di legno (dodecaedro), i cui venti vertici erano contrassegnati da borchie. Ogni picco aveva il nome di una delle città più grandi del mondo: Canton, Delhi, Bruxelles, ecc. Il compito era trovare un percorso chiuso che corresse lungo i bordi del poliedro, visitando ogni vertice una sola volta. Per delimitare il percorso veniva utilizzata una corda che veniva agganciata ai chiodi.

Un ciclo di Hamilton è un grafo il cui percorso è un ciclo semplice che passa attraverso tutti i vertici del grafo una volta.

La città di Kaliningrad (ex Koenigsberg) si trova sul fiume Pregel. Il fiume bagnava due isole, collegate tra loro e alle rive da ponti. I vecchi ponti non ci sono più. Il loro ricordo rimane solo sulla mappa della città.

Un giorno, un residente della città chiese al suo amico se fosse possibile attraversare tutti i ponti, visitarli tutti una volta sola e tornare al luogo in cui era iniziata la passeggiata. Questo problema interessava molti cittadini, ma nessuno poteva risolverlo. Questo problema ha suscitato l'interesse di scienziati di molti paesi. La soluzione al problema è stata ottenuta dal matematico Leonhard Euler. Inoltre, ha formulato un approccio generale per risolvere tali problemi. Per fare ciò, ha trasformato la mappa in un grafico. I vertici di questo grafico erano la terra e i bordi erano i ponti che la collegavano.

Risolvendo il problema del ponte di Königsberg, Eulero riuscì a formulare le proprietà dei grafi.

È possibile disegnare un grafico partendo da un vertice e terminando allo stesso vertice con un tratto (senza disegnare due volte lungo la stessa linea e senza staccare la matita dal foglio) se tutti i vertici del grafico sono pari.

Se c'è un grafico con due vertici dispari, anche i suoi vertici possono essere collegati con un tratto. Per fare questo, devi iniziare da uno e finire sull'altro, qualsiasi vertice dispari.

Se c'è un grafico con più di due vertici dispari, il grafico non può essere disegnato con un solo tratto.

Se applichiamo queste proprietà al problema dei ponti, possiamo vedere che tutti i vertici del grafo in esame sono dispari, il che significa che questo grafo non può essere collegato con un tratto, cioè È impossibile attraversare tutti i ponti una volta e terminare il viaggio nel luogo in cui è iniziato.

Se un grafico ha un ciclo (non necessariamente semplice) contenente tutti gli spigoli del grafico una volta, allora viene chiamato tale ciclo Ciclo di Eulero . La catena di Eulero (percorso, ciclo, contorno) è una catena (percorso, ciclo, contorno) contenente tutti gli spigoli (archi) del grafico una volta.

CAPITOLO II. DESCRIZIONE DELLO STUDIO E DEI SUOI ​​RISULTATI

2.1. Fasi dello studio

Per verificare l’ipotesi, lo studio ha previsto tre fasi (Tabella 1):

Fasi della ricerca

Tabella 1.

		Metodi utilizzati
Studio teorico del problema	Studiare e analizzare la letteratura educativa e scientifica.	- pensiero indipendente;  studio delle fonti informative; - ricerca della letteratura necessaria.
Ricerca pratica del problema	Considerare e analizzare le aree di applicazione pratica dei grafici;	- osservazione; - analisi; - confronto; - sondaggio.
Fase 3. Utilizzo pratico dei risultati	Riassumere le informazioni studiate;	- sistematizzazione;  relazione (orale, scritta, con dimostrazione dei materiali)	Settembre 2017

2.2. Aree di applicazione pratica dei grafici

Grafici e informazioni

La teoria dell'informazione fa ampio uso delle proprietà degli alberi binari.

Ad esempio, se è necessario codificare un certo numero di messaggi sotto forma di determinate sequenze di zeri e di diverse lunghezze. Un codice è considerato migliore per una determinata probabilità di parole in codice se la lunghezza media delle parole è minima rispetto ad altre distribuzioni di probabilità. Per risolvere questo problema, Huffman ha proposto un algoritmo in cui il codice è rappresentato come un grafico ad albero nell'ambito della teoria della ricerca. Per ogni vertice viene proposta una domanda, la cui risposta può essere "sì" o "no", che corrisponde ai due bordi che escono dal vertice. La costruzione di tale albero viene completata dopo aver stabilito ciò che era necessario. Questo può essere utilizzato nell'intervista a più persone, quando la risposta alla domanda precedente non è nota in anticipo, il piano dell'intervista è rappresentato come un albero binario.

Grafici e chimica

A. Cayley considerò anche il problema delle possibili strutture degli idrocarburi saturi (o saturi), le cui molecole sono date dalla formula:

CnH 2n+2

Tutti gli atomi di idrocarburi sono quadrivalenti, tutti gli atomi di idrogeno sono 1valenti. Le formule strutturali degli idrocarburi più semplici sono mostrate in figura.

Ogni molecola di idrocarburo saturo può essere rappresentata come un albero. Quando tutti gli atomi di idrogeno vengono rimossi, gli atomi di idrocarburi che rimangono formano un albero con vertici il cui grado non è superiore a quattro. Ciò significa che il numero di possibili strutture desiderate (omologhi di una data sostanza) è uguale al numero di alberi i cui gradi di vertice non sono superiori a 4. Questo problema si riduce al problema di enumerare alberi di un tipo particolare. D. Polya ha considerato questo problema e le sue generalizzazioni.

Grafici e biologia

Il processo di riproduzione batterica è uno dei tipi di processi di ramificazione riscontrati nella teoria biologica. Lascia che ogni batterio, dopo un certo tempo, muoia o si divida in due. Pertanto, per un batterio otteniamo un albero binario della riproduzione della sua prole. La domanda del problema è la seguente: quanti casi contiene? K discendenti nell'ennesima generazione di un batterio? Questa relazione in biologia è chiamata processo Galton-Watson, che denota il numero richiesto di casi richiesti.

Grafici e Fisica

Un compito difficile e noioso per qualsiasi radioamatore è creare circuiti stampati (una piastra di materiale dielettrico-isolante e tracce incise sotto forma di strisce metalliche). L'intersezione delle tracce avviene solo in determinati punti (posizioni di triodi, resistori, diodi, ecc.) secondo determinate regole. Di conseguenza, lo scienziato deve affrontare il compito di disegnare un grafico piatto con i vertici all'interno

Quindi, tutto quanto sopra conferma il valore pratico dei grafici.

Matematica su Internet

Internet è un sistema mondiale di reti di computer interconnesse per archiviare e trasmettere informazioni.

Internet può essere rappresentato come un grafico, dove i vertici del grafico sono i siti Internet e i bordi sono i collegamenti (collegamenti ipertestuali) che vanno da un sito all'altro.

Il grafico web (Internet), che ha miliardi di vertici e bordi, è in continua evoluzione: i siti vengono aggiunti e scomparsi spontaneamente, i collegamenti scompaiono e vengono aggiunti. Tuttavia, Internet ha una struttura matematica, obbedisce alla teoria dei grafi e ha diverse proprietà “stabili”.

Il grafico web è scarso. Contiene solo poche volte più bordi che vertici.

Nonostante la sua scarsità, Internet è molto affollata. Puoi passare da un sito all'altro utilizzando i link in 5 - 6 clic (la famosa teoria delle “sei strette di mano”).

Come sappiamo, il grado di un grafico è il numero di archi a cui appartiene un vertice. I gradi dei vertici di un grafo web sono distribuiti secondo una certa legge: la proporzione di siti (vertici) con un gran numero di collegamenti (bordi) è piccola e la quota di siti con un piccolo numero di collegamenti è grande. Matematicamente si può scrivere così:

dove è la proporzione dei vertici di un certo grado, è il grado di un vertice, è una costante indipendente dal numero di vertici del grafo web, cioè non cambia durante il processo di aggiunta o rimozione di siti (vertici).

Questa legge di potere è universale per le reti complesse, da quelle biologiche a quelle interbancarie.

Internet nel suo complesso è resistente agli attacchi casuali ai siti.

Poiché la distruzione e la creazione dei siti avviene in modo indipendente e con la stessa probabilità, il grafico web, con probabilità prossima a 1, mantiene la sua integrità e non viene distrutto.

Per studiare Internet è necessario costruire un modello grafico casuale. Questo modello dovrebbe avere le proprietà della vera Internet e non dovrebbe essere troppo complesso.

Questo problema non è stato ancora completamente risolto! Risolvere questo problema, costruendo un modello di Internet di alta qualità, ci consentirà di sviluppare nuovi strumenti per migliorare la ricerca di informazioni, identificare lo spam e diffondere informazioni.

La costruzione di modelli biologici ed economici è iniziata molto prima che sorgesse il compito di costruire un modello matematico di Internet. Tuttavia, i progressi nello sviluppo e nello studio di Internet hanno permesso di rispondere a molte domande riguardanti tutti questi modelli.

La matematica di Internet è richiesta da molti specialisti: biologi (previsione della crescita delle popolazioni batteriche), finanzieri (rischi di crisi), ecc. Lo studio di tali sistemi è uno dei rami centrali della matematica applicata e dell'informatica.

Murmansk utilizzando il grafico.

Quando una persona arriva in una nuova città, di regola, il primo desiderio è visitare le principali attrazioni. Allo stesso tempo, però, il tempo a disposizione è spesso limitato e, nel caso di un viaggio d'affari, molto ridotto. Pertanto, è necessario pianificare in anticipo la visita. E i grafici ti saranno di grande aiuto nella costruzione del tuo percorso!

Ad esempio, considera il caso tipico di arrivare a Murmansk dall'aeroporto per la prima volta. Abbiamo in programma di visitare le seguenti attrazioni:

1. Chiesa Ortodossa Marina del Salvatore sull'Acqua;

2. Cattedrale di San Nicola;

3. Oceanario;

4. Monumento al gatto Semyon;

5. Rompighiaccio nucleare Lenin;

6. Luci del parco di Murmansk;

7. Parco Valle del Conforto;

8. Ponte di Kola;

9. Museo di storia della compagnia di navigazione di Murmansk;

10. Quadrato dei Cinque Angoli;

11. Porto commerciale marittimo

Per prima cosa localizziamo questi luoghi sulla mappa e otteniamo una rappresentazione visiva della posizione e della distanza tra le attrazioni. La rete stradale è abbastanza sviluppata e viaggiare in macchina non sarà difficile.

Le attrazioni sulla mappa (a sinistra) e il grafico risultante (a destra) sono mostrati nella figura corrispondente nell'APPENDICE N. 1. Pertanto, il nuovo arrivato passerà prima vicino al ponte di Kola (e, se lo desidera, potrà attraversarlo avanti e indietro); poi si rilasserà nel Parco delle Luci di Murmansk e nella Valle del Conforto e andrà avanti. Di conseguenza, il percorso ottimale sarà:

Utilizzando il grafico è inoltre possibile visualizzare lo schema per lo svolgimento dei sondaggi d'opinione. Gli esempi sono presentati nell'APPENDICE N. 2. A seconda delle risposte fornite, all’intervistato vengono poste domande diverse. Ad esempio, se nell'indagine sociologica n. 1 l'intervistato considera la matematica la più importante delle scienze, gli verrà chiesto se si sente sicuro nelle lezioni di fisica; se la pensa diversamente, la seconda questione riguarderà la domanda di discipline umanistiche. I vertici di tale grafico sono domande e i bordi sono opzioni di risposta.

2.3. Applicazione della teoria dei grafi alla risoluzione dei problemi

La teoria dei grafi viene utilizzata per risolvere problemi di molte aree tematiche: matematica, biologia, informatica. Abbiamo studiato il principio della risoluzione dei problemi utilizzando la teoria dei grafi e creato i nostri problemi sul tema della ricerca.

Compito n. 1.

Cinque compagni di classe si sono stretti la mano durante una riunione del liceo. Quante strette di mano sono state fatte?

Soluzione: denotiamo i compagni di classe con i vertici del grafico. Colleghiamo ciascun vertice con linee ad altri quattro vertici. Otteniamo 10 righe, queste sono strette di mano.

Risposta: 10 strette di mano (ogni riga significa una stretta di mano).

Compito n. 2.

Nel villaggio di mia nonna, vicino a casa sua, crescono 8 alberi: pioppo, quercia, acero, melo, larice, betulla, sorbo e pino. Il sorbo è più alto del larice, il melo è più alto dell'acero, la quercia è più bassa della betulla, ma più alta del pino, il pino è più alto del sorbo, la betulla è più bassa del pioppo e il larice è più alto del melo. In che ordine saranno disposti gli alberi in altezza dal più alto al più basso?

Soluzione:

Gli alberi sono i vertici del grafico. Indichiamoli con la prima lettera nel cerchio. Disegniamo le frecce da un albero basso a uno più alto. Si dice che il sorbo sia più alto del larice, quindi mettiamo la freccia dal larice al sorbo, la betulla è più bassa del pioppo, quindi mettiamo la freccia dal pioppo alla betulla, ecc. Otteniamo un grafico in cui possiamo vedere che l'albero più basso è l'acero, poi il melo, il larice, il sorbo, il pino, la quercia, la betulla e il pioppo.

Risposta: acero, melo, larice, sorbo, pino, quercia, betulla e pioppo.

Compito n.3.

La mamma ha 2 buste: normale e aerea, e 3 francobolli: quadrati, rettangolari e triangolari. In quanti modi la mamma può scegliere una busta e un francobollo per inviare una lettera a papà?

Risposta: 6 modi

Compito n. 4.

Sono state costruite strade tra gli insediamenti A, B, C, D, E. Devi determinare la lunghezza del percorso più breve tra i punti A ed E. Puoi muoverti solo lungo strade la cui lunghezza è indicata in figura.

Compito n.5.

Tre compagni di classe: Maxim, Kirill e Vova hanno deciso di dedicarsi allo sport e hanno superato la selezione delle sezioni sportive. È noto che 1 ragazzo ha fatto domanda per la sezione di basket e tre volevano giocare a hockey. Maxim ha fatto l'audizione solo per la sezione 1, Kirill è stato selezionato per tutte e tre le sezioni e Vova è stato selezionato per la sezione 2. Quale dei ragazzi è stato selezionato per quale sezione sportiva?

Soluzione: Per risolvere il problema utilizzeremo i grafici

Massimo del basket

Calcio Kirill

Hockey Vova

Dal a pallacanestro va solo una freccia, quindi Kirill è stato selezionato nella sezione pallacanestro. Quindi Kirill non giocherà hockey, che significa dentro hockey la sezione è stata selezionata da Maxim, che ha fatto l'audizione solo per questa sezione, quindi lo sarà Vova calciatore.

Compito n. 6.

A causa della malattia di alcuni insegnanti, il preside della scuola deve redigere un frammento dell'orario scolastico per almeno un giorno, tenendo conto delle seguenti circostanze:

1. L'insegnante di sicurezza si impegna a tenere solo l'ultima lezione;

2. L'insegnante di geografia può impartire indifferentemente la seconda o la terza lezione;

3. Il matematico è pronto a dare o solo la prima oppure solo la seconda lezione;

4. Un insegnante di fisica può tenere la prima, la seconda o la terza lezione, ma solo in una classe.

Che tipo di programma può creare il preside di una scuola in modo da soddisfare tutti gli insegnanti?

Soluzione: questo problema può essere risolto esaminando tutte le opzioni possibili, ma è più semplice se si disegna un grafico.

1. 1) fisica 2. 1) matematica 3. 1) matematica

2) matematica 2) fisica 2) geografia

3) geografia 3) geografia 3) fisica

4) OBZH 4) OBZH 4) OBZH

Conclusione

In questo lavoro di ricerca, la teoria dei grafi è stata studiata in dettaglio, è stata dimostrata l'ipotesi che lo studio dei grafici può aiutare a risolvere problemi logici, inoltre è stata considerata la teoria dei grafi in diversi campi della scienza e sono stati compilati 7 problemi.

L'uso dei grafici quando si insegna agli studenti come trovare soluzioni ai problemi consente agli studenti di migliorare le proprie capacità grafiche e comunicare il ragionamento in un linguaggio speciale su un insieme finito di punti, alcuni dei quali sono collegati da linee. Tutto ciò contribuisce al lavoro di insegnare agli studenti a pensare.

L'efficacia delle attività educative nello sviluppo del pensiero dipende in gran parte dal grado di attività creativa degli studenti nella risoluzione dei problemi matematici. Pertanto, sono necessari compiti ed esercizi matematici che attivino l'attività mentale degli scolari.

L'applicazione dei compiti e l'uso di elementi di teoria dei grafi nelle classi facoltative a scuola persegue proprio l'obiettivo di attivare l'attività mentale degli studenti. Crediamo che il materiale pratico sulla nostra ricerca possa essere utile nelle lezioni facoltative di matematica.

Pertanto, l'obiettivo del lavoro di ricerca è stato raggiunto, i problemi sono stati risolti. In futuro, prevediamo di continuare a studiare la teoria dei grafi e sviluppare i nostri percorsi, ad esempio, utilizzando un grafico per creare un percorso di escursione per uno scuolabus nella ZATO Aleksandrovsk verso musei e luoghi memorabili a Murmansk.

ELENCO REFERENZE UTILIZZATE

Berezina L. Yu. “I grafici e la loro applicazione” - M.: “Illuminismo”, 1979

Gardner M. “Svago matematico”, M. “Mir”, 1972

Gardner M. “Enigmi matematici e intrattenimento”, M. “Mir”, 1971

Gorbachev A. "Raccolta di problemi delle Olimpiadi" - M. MTsNMO, 2005

Zykov A. A. Fondamenti di teoria dei grafi. - M.: “Libro dell'Università”, 2004. - P. 664

Kasatkin V. N. “Problemi insoliti di matematica”, Kiev, “Radianska School”, 1987

Componente matematica / Editori e compilatori N.N. Andreev, S.P. Konovalov, N.M. Panjuškin. - M.: Fondazione "Studi Matematici" 2015 - 151 p.

Melnikov O. I. "Problemi divertenti nella teoria dei grafi", Mn. "TetraSystems", 2001

Melnikov O.I. Non so nella terra dei conti: un manuale per gli studenti. Ed. 3°, stereotipato. M.: KomKniga, 2007. - 160 p.

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. “Vecchi problemi divertenti”, M. “Scienza”, 1988

Ore O. “I grafici e le loro applicazioni”, M. “Mir”, 1965

Harari F. Teoria dei grafici / Traduzione dall'inglese. e prefazione V. P. Kozyreva. Ed. G. P. Gavrilova. Ed. 2°. - M.: Editoriale URSS, 2003. - 296 p.

APPENDICE N. 1

Elaborazione del percorso ottimale per visitare le principali attrazioni

Murmansk utilizzando il grafico.

Il percorso ottimale sarà:

8. Ponte di Kola6. Luci del parco di Murmansk7. Parco Valle del Comfort2. Cattedrale di San Nicola10. Quadrato dei cinque angoli5. Rompighiaccio nucleare Lenin9. Museo di storia della compagnia di navigazione di Murmansk11. Porto commerciale marittimo1. Chiesa ortodossa marina del Salvatore sull'acqua4. Monumento al gatto Semyon3. Oceanario.

GUIDA ALLE ATTRAZIONI DI MURMANSK

APPENDICE N. 2

Indagini sociologiche n. 1, 2

Edizione didattica

Yuyukin Nikolay Alekseevich

LR n. Firmato per sigillo

Uh. Ed. io.. , .

Università tecnica statale di Voronezh

394026 Voronezh, viale Moskovsky. 14

DIRECTORY DEL DISCO MAGNETICO

Dipartimento di Matematica Superiore e Modellistica Fisica e Matematica

SUL. Yuyukin

MATEMATICA DISCRETA Parte 1. Elementi di teoria dei grafi

Esercitazione

SUL. Yuyukin

MATEMATICA DISCRETA Parte 1. Elementi di teoria dei grafi

Esercitazione

Voronež 2004

INTRODUZIONE

Questo manuale può essere utilizzato nel corso "Matematica Discreta" dagli studenti VSTU che studiano nelle seguenti specialità:

090102 – Sicurezza informatica;

090105 – Fornitura completa di sicurezza informatica dei sistemi automatizzati;

090106 - Sicurezza informatica dei sistemi di telecomunicazioni.

La disciplina "Matematica Discreta" garantisce l'acquisizione di conoscenze e competenze in conformità con lo standard statale e generale di istruzione e allo stesso tempo promuove l'acquisizione dell'istruzione fondamentale, la formazione di una visione del mondo e lo sviluppo del pensiero logico.

La teoria dei grafi è uno strumento efficace per formalizzare i moderni problemi di ingegneria associati agli oggetti discreti. Viene utilizzato nella progettazione di circuiti integrati e circuiti di controllo, nello studio di automi e circuiti logici, nell'analisi di sistema, nel controllo automatizzato della produzione, nello sviluppo di reti di computer e informazioni, nella progettazione di circuiti e progettazione topologica, ecc.

Il tutorial delinea i fondamenti, i metodi di base e gli algoritmi della teoria dei grafi. Qui presentiamo n-grafi e digrafi; isomorfismi; alberi; Grafici di Eulero; grafici planari; coperture e set indipendenti; forte connettività

V digrafi; Analisi del grafico della catena di Markov; algoritmi per trovare i cammini minimi nei grafici; Problema di ricerca del ciclo hamiltoniano

V grafico; problema del commesso viaggiatore; enumerazione di grafici e mappature; compiti estremi; problemi di ottimizzazione; compiti universali; metodo branch and bound; e sviluppare anche abilità pratiche nell'utilizzo dei concetti di cui sopra.

Lo scopo del corso è quello di sviluppare le conoscenze teoriche, le abilità pratiche e le abilità degli studenti nel campo della modellazione di processi e fenomeni nelle scienze e tecnologie naturali.

ke, con la capacità di utilizzare simboli matematici per esprimere le relazioni quantitative e qualitative degli oggetti necessari per svolgere attività ufficiali nel campo della sicurezza informatica ad alto livello professionale.

Per raggiungere questo obiettivo servono i seguenti compiti:

studiare la più ampia gamma possibile di concetti di teoria dei grafi;

acquisire competenze nella risoluzione di problemi educativi e pratici;

metodi di ottimizzazione principali;

sviluppare competenze nell'impostazione e risoluzione di problemi informativi, modellazione e analisi delle informazioni utilizzando grafici.

La disciplina “Matematica Discreta” è una delle discipline matematiche applicate. Si basa sulle conoscenze acquisite dagli studenti durante lo studio delle discipline “Algebra” e “Logica Matematica e Teoria degli Algoritmi”. Nello studio vengono utilizzate le conoscenze e le competenze acquisite nello studio della disciplina “Matematica Discreta”. professionale generale e discipline speciali.

1. CONCETTI FONDAMENTALI DELLA TEORIA DEI GRAFI.

1.1. Problemi di teoria dei grafi.

La teoria dei grafi è una branca della matematica che studia i sistemi di connessioni tra diversi oggetti, proprio come si fa con il concetto di relazione. Tuttavia, una definizione indipendente del grafico semplifica la presentazione della teoria e la rende più comprensibile e visiva.

I primi problemi della teoria dei grafi riguardavano la risoluzione di problemi di intrattenimento ed enigmi.

Primo compito. Il problema dei ponti di Königsberg fu posto e risolto da Eulero nel 1786. La città si trovava sulle rive e su due isole del fiume Pregolya. Le isole erano collegate tra loro e alle coste da sette ponti, come mostrato in figura.

Sorge la domanda: è possibile uscire di casa e tornare indietro, attraversando ogni ponte esattamente una volta?

Secondo compito. Il problema delle tre case e dei tre pozzi. Ci sono tre case e tre pozzi.

È necessario tracciare un percorso da ogni casa a ciascun pozzo in modo che i percorsi non si intersechino. Il compito era

risolto da Pontryagin e indipendentemente da lui da Kuratovsky in

Terzo compito. Circa quattro colori. Colora qualsiasi mappa su un piano con quattro colori in modo che non vi siano due aree adiacenti dipinte con lo stesso colore.

Molti risultati della teoria dei grafi vengono utilizzati per risolvere problemi pratici nella scienza e nella tecnologia. Così, a metà del XIX secolo, Kirchhoff utilizzò la teoria dei grafi per calcolare circuiti elettrici complessi. Tuttavia, come disciplina matematica, la teoria dei grafi si è formata solo negli anni '30 del XX secolo. In questo caso, i grafici sono considerati come oggetti matematici astratti. Sono utilizzati nell'analisi e nella sintesi di circuiti e sistemi, nella pianificazione e gestione della rete, nella ricerca operativa, nella programmazione, nella modellazione della vita di un organismo e in altri settori.

1.2. Definizioni di base.

Un grafo G= (V,E) è una raccolta di due insiemi: un insieme non vuoto di vertici V e un insieme di coppie di vertici non ordinate e ordinate E. Nel seguito considereremo grafi finiti, cioè grafi con un insieme finito di vertici e una famiglia finita di coppie. Una coppia di vertici non ordinati è chiamata bordo, mentre una coppia ordinata è chiamata arco.

Tipicamente, un grafico è rappresentato da un diagramma: i vertici sono punti (o cerchi), i bordi sono linee di configurazione arbitraria. Una freccia indica inoltre la sua direzione sull'arco. Si noti che quando si descrive un grafico, il vettore

Le proprietà geometriche dei bordi (lunghezza, curvatura), nonché la posizione relativa dei vertici sul piano, sono essenziali.

I vertici che non appartengono ad alcun bordo (arco) sono detti isolati. I vertici collegati da uno spigolo o da un arco si dicono adiacenti. Un bordo (arco) e uno qualsiasi dei suoi due vertici sono detti incidenti.

Dicono che un bordo (u,v) collega i vertici u e v, e un arco (u,v) inizia nel vertice u e termina nel vertice v, con u chiamato inizio e v fine di questo arco.

Una coppia di vertici può essere collegata da due o più bordi (archi nella stessa direzione). Tali bordi (archi) sono detti multipli. Un arco (o bordo) può iniziare o terminare nello stesso vertice. Un tale arco (bordo) è chiamato anello. Un grafo contenente cicli è chiamato pseudografo. Un grafico che ha più bordi (archi) è chiamato multigrafo.

Un grafico senza cicli o bordi multipli è chiamato semplice. Un grafo semplice si dice completo se per ogni coppia dei suoi vertici esiste un arco (arco) che li collega. Un grafo completo con n vertici è indicato con K n. Ad esempio, questi sono grafici

Un grafo costituito da un vertice isolato (K 1) è detto banale.

Il complemento di un grafo G è un grafo G che ha gli stessi vertici del grafo G e contiene quegli archi che devono essere aggiunti al grafo G per ottenere un grafo completo.

A ogni non digrafo corrisponde canonicamente un grafo diretto con lo stesso insieme di vertici, in cui ciascun bordo è sostituito da due archi incidenti agli stessi vertici e aventi direzioni opposte.

1.3. Gradi dei vertici del grafico.

Il grado (valenza) (notazione d (v) o deg (v)) di un vertice v di un grafo semplice G è il numero di archi o archi incidenti a un dato vertice v. Quando si calcola la valenza dei vertici di uno pseudografo, ogni ciclo dovrebbe essere contato due volte.

Se i gradi di tutti i vertici di un n-grafo sono uguali a k, allora il grafo viene chiamato regolare (uniforme) grado k. Se il grado di un vertice è 0 allora è isolato. Se il grado di un vertice è 1, allora il vertice è chiamato vertice terminale (sospeso, vicolo cieco).

Per un digrafo si chiama il numero di archi uscenti dal vertice v

varia semi-grado di risultato										(v), e quelli entranti – semi-step-
nuovo bando d							(v), In questo caso la relazione d (v)=
		(v)+			(v).

Teorema di Eulero: La somma dei gradi dei vertici di un grafico è

raddoppiare il numero di costole, cioè

d(vi)

			(v)

Dove n è il numero di vertici; m – numero

costole (archi). Questa affermazione è dimostrata dal fatto che quando si calcola la somma dei gradi dei vertici, ciascun bordo viene preso in considerazione due volte: per un'estremità del bordo e per l'altra.

1.4. Isomorfismo del grafico.

Un grafo viene detto etichettato (o rinumerato) se i suoi vertici differiscono in qualche modo tra loro.

etichette (numeri). Si considera il conteggio completamente dato in senso stretto, se la numerazione dei suoi vertici e dei bordi è fissa. In questo caso, i grafici G 1 e G 2 sono detti uguali (designazione G 1 = G 2), se i loro insiemi di vertici e archi coincidono. Due grafi o pseudografi G 1 = (V 1 ,E 1 ) e G 2 = (V 2 ,E 2 ) si chiamano

	isomorfo (notazione G				se esistono
	mappature uno a uno: 1)				: V1V2
: E 1 E 2 tale che per due vertici qualsiasi u, v nel grafico
	la relazione ((u, v)) ((u), (v)) è valida.
	Due grafici semplici (senza cicli e archi multipli) G 1					e G2

risultano isomorfi se sono reciprocamente identici

mappatura dei valori

: V1V2

E allora?

(u, v) ((u), (v)) .

Pertanto, i grafi che differiscono solo nella numerazione dei vertici e degli spigoli sono isomorfi. L’isomorfismo del grafico è una relazione di equivalenza perché ha le proprietà:

Riflessività -

G1,

e la biiezione

è una funzione identica.

Simmetria.

con biiezione

con biiezione

Transitività.

SOL1 SOL2

biiezione

1,a

con biiezione

poi G G

con biiezione

2 (1 ) .