La teoria dei grafi è una branca della matematica discreta che studia gli oggetti rappresentati come elementi separati (vertici) e le connessioni tra di essi (archi, spigoli).
La teoria dei grafi ha origine dalla soluzione del problema del ponte di Königsberg nel 1736 dal famoso matematico Leonardo Eulero(1707-1783: nato in Svizzera, vissuto e lavorato in Russia).
Il problema dei ponti di Königsberg.
Ci sono sette ponti nella città prussiana di Königsberg sul fiume Pregal. È possibile trovare un percorso a piedi che passa esattamente 1 volta su ciascuno dei ponti e inizia e finisce nello stesso punto?
Un grafo in cui c'è un percorso che inizia e termina nello stesso vertice, e passa attraverso tutti gli spigoli del grafo esattamente una volta, è chiamatoGrafico di Eulero.
Viene chiamata la sequenza di vertici (che possono essere ripetuti) attraverso i quali passa il percorso desiderato, nonché il percorso stessoCiclo di Eulero .
Il problema delle tre case e dei tre pozzi.
Ci sono tre case e tre pozzi, in qualche modo situati sull'aereo. Disegna un percorso da ogni casa a ogni pozzo in modo che i percorsi non si intersechino. Questo problema è stato risolto (è dimostrato che non c'è soluzione) Kuratovsky (1896 - 1979) nel 1930.
Il problema dei quattro colori. Viene chiamata la divisione di un piano in regioni non intersecanti carta. Le aree della mappa sono chiamate vicini se lo hanno confine comune. Il problema è colorare la mappa in modo tale che due aree vicine non siano riempite con lo stesso colore. Dalla fine dell'Ottocento si sapeva l'ipotesi che per questo fossero sufficienti quattro colori. L'ipotesi non è stata finora dimostrata.
L'essenza della soluzione pubblicata è enumerare un numero grande ma finito (circa 2000) di tipi di potenziali controesempi al teorema dei quattro colori e mostrare che nessun caso è un controesempio. Questa enumerazione è stata eseguita dal programma in circa mille ore di funzionamento del supercomputer.
È impossibile controllare "manualmente" la soluzione ottenuta: la quantità di enumerazione va oltre l'ambito delle capacità umane. Molti matematici sollevano la domanda: una tale "prova software" può essere considerata una prova valida? Dopotutto, potrebbero esserci errori nel programma ...
Pertanto, resta da fare affidamento sulle qualifiche del programmatore degli autori e credere che abbiano fatto tutto bene.
Definizione 7.1. Contare G= G(v, E) è la raccolta di due insiemi finiti: V - chiamato molti picchi e insiemi E di coppie di elementi da V, cioè EÍV´V, chiamato molti spigoli, se le coppie non sono ordinate, o molti archi se le coppie sono ordinate.
Nel primo caso il grafico G(v, E) chiamato difficile, nel secondo orientata.
ESEMPIO. Un grafo con un insieme di vertici V = (a, b, c) e un insieme di archi E = ((a, b), (b, c))
ESEMPIO. Un grafico con V = (a, b, c, d, e) ed E = ((a, b), (a, e), (b, e), (b, d), (b, c) , (CD)),
Se e=(v 1 ,v 2), eнE, allora diciamo che l'arco e collega vertici v 1 e v 2 .
Vengono chiamati due vertici v 1 ,v 2 imparentato se c'è un bordo che li collega. In questa situazione, viene chiamato ciascuno dei vertici incidentale bordo corrispondente .
Due coste diverse adiacente se hanno un vertice comune. In questa situazione, viene chiamato ciascuno dei bordi incidentale vertice corrispondente .
Numero di vertici del grafico G denota v, e il numero di spigoli - e:
.
La rappresentazione geometrica dei grafici è la seguente:
1) il vertice del grafico è un punto nello spazio (sul piano);
2) un arco di un grafo non orientato è un segmento;
3) l'arco di un grafo orientato è un segmento orientato.
Definizione 7.2. Se nell'arco e=(v 1 ,v 2) v 1 =v 2 ha luogo, allora l'arco e è chiamato ciclo continuo. Se un grafico può avere loop, allora viene chiamato grafico con loop O pseudografo .
Se un grafico può avere più di un bordo tra due vertici, allora viene chiamato multigrafo .
Se ogni vertice del grafico e (o) spigolo è etichettato, viene chiamato tale grafico etichettato (O caricato ). Lettere o numeri interi sono solitamente usati come segni.
Definizione 7.3. Grafico G (v , E ) chiamato sottografo (O parte ) contare G(v,E), Se v v, E E. Se v = v, Quello G chiamato sottografo di copertura G.
Esempio 7 . 1 . Viene fornito un grafico non orientato.
Definizione 7.4. Il conteggio è chiamato completare , Se Qualunque due dei suoi vertici sono collegati da un bordo. Grafico completo con N vertici è indicato da K N .
Conti K 2 , A 3, A 4 e k 5 .
Definizione 7.5. Grafico G=G(v, E) è chiamato dicotiledone , Se v può essere pensato come l'unione di insiemi disgiunti, diciamo v=UNB, in modo che ogni spigolo abbia la forma ( v io , v J), Dove v io UN E v J B.
Ogni bordo collega un vertice da A a un vertice da B, ma non sono collegati due vertici da A o due vertici da B.
Il grafico bipartito è chiamato pieno dicotico contare K M , N, Se UN contiene M picchi, B contiene N vertici e per ciascuno v io UN, v J B abbiamo ( v io , v J)E.
Così, per ciascuno v io UN, E v J B c'è un bordo che li collega.
K 12 K 23 K 22 K 33
Esempio 7 . 2 . Costruire un grafo bipartito completo K 2.4 e grafico completo K 4 .
Grafico unitarioNcubo dimensionaleIN N .
I vertici del grafico sono insiemi binari n-dimensionali. I bordi collegano i vertici che differiscono per la stessa coordinata.
Esempio: 
Tra gli abitanti di Koenigsberg era comune un enigma così pratico: è possibile attraversare tutti i ponti sul fiume Pregolya senza attraversarne nessuno due volte? Nel 1736 l'eminente matematico Leonhard Euler si interessò al problema e in una lettera ad un amico diede una prova rigorosa che era impossibile farlo. Nello stesso anno dimostrò una straordinaria formula che mette in relazione il numero di vertici, facce e spigoli di un poliedro nello spazio tridimensionale. La formula è anche misteriosamente vera per i grafici che vengono chiamati "planari". Questi due risultati hanno gettato le basi per la teoria dei grafi e sono una buona illustrazione della direzione del suo sviluppo fino ad oggi.
A proposito del corso
Questo corso serve come introduzione a teoria moderna grafici. Un grafico come oggetto matematico si rivela utile in molti problemi teorici e pratici. Il punto, forse, è che la complessità della sua struttura ben si adatta alle capacità del nostro cervello: questa struttura è visiva e comprensibile, ma, d'altra parte, abbastanza ricca da catturare molti fenomeni non banali. Se parliamo di applicazioni, allora, ovviamente, mi vengono subito in mente grandi reti: Internet, cartina stradale, copertura comunicazioni mobili e così via. I motori di ricerca come Yandex e Google si basano su algoritmi grafici. Oltre all'informatica, i grafici vengono utilizzati attivamente in bioinformatica, chimica e sociologia. Nel nostro corso discuteremo certamente di problemi classici, ma parleremo anche di risultati e tendenze più recenti, ad esempio della teoria dei grafi estremali.
Formato
Il corso consiste in 7 settimane di studio e un esame. Per risolvere con successo la maggior parte dei compiti dei test, è sufficiente padroneggiare il materiale raccontato nelle lezioni. I seminari trattano problemi più complessi che possono interessare un ascoltatore che abbia già familiarità con le basi della teoria dei grafi.
Risorse informative
- V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. Lezioni sulla teoria dei grafi. Mosca: Librocom Book House, 2009.
- A. A. Zykov. Teoria dei Grafi Finiti. Novosibirsk: Nauka, 1969.
- M. Swami, K. Thulasiraman. Grafi, reti e algoritmi. M.: Mir, 1984.
- M. Aigner, G. M. Ziegler. Prove Dal LIBRO. Quarta edizione. Primavera, 2009.
- B. Bollobás. Teoria moderna dei grafi. Springer, 1998.
- J. A. Bondy, U. S. R. Murty. teoria dei grafi. Primavera, 2008.
Requisiti
Il materiale è presentato dalle basi e in un linguaggio accessibile. Lo scopo di questo corso non è solo quello di introdurti ai problemi e ai metodi della teoria dei grafi, ma anche di sviluppare una cultura del pensiero matematico in studenti impreparati. Pertanto, il corso è accessibile a una vasta gamma di studenti. Per padroneggiare il materiale sarà sufficiente la conoscenza della matematica a un buon livello scolastico e la conoscenza di base della combinatoria.
Programma del corso
- Il concetto di grafico e tipi di grafici.
- Varie applicazioni dei grafi: dai ponti Königsber a Internet.
- Connettività del grafico, sottografi e grado del vertice.
- Definizioni equivalenti di alberi.
- Planarità e criterio di Kuratovsky
- Formula di Eulero.
- Numero cromatico di un grafo planare.
- Enumerazione degli alberi: codice di Prufer e formula di Cayley.
- Formula per il numero di grafi uniciclici.
- Cicli di Eulero e criterio di Eulero.
- Cicli di Hamilton. Criterio di Dirac e criterio di Khvatal.
- Corrispondenza. Teorema di Hall e Koenig.
- Teoria dei grafi estremali. Il teorema di Turan.
- Un analogo del teorema di Turan per i grafici nel piano.
- Teoria di Ramsey. Incontri tra sei persone.
- Definizione del numero di Ramsey.
- Limiti inferiore e superiore per i numeri di Ramsey.
Risultati di apprendimento
A seguito del completamento con successo del corso, lo studente acquisirà familiarità con il concetto di grafico, con tipi e caratteristiche diverse e proprietà del grafico. L'ascoltatore apprenderà il problema delle colorazioni regolari e la possibilità di tracciare un dato grafico su un piano senza incrociare spigoli, e imparerà anche a diversi modi identificare gli alberi ed enumerarli. Infine, l'ascoltatore acquisirà familiarità con i concetti di Eulero e cicli Hamiltoniani, corrispondenze e toccherà persino i problemi della teoria dei grafi estremali.
Informalmente, un grafico può essere visto come un insieme di punti e linee che collegano questi punti con o senza frecce.
Il primo lavoro di teoria dei grafi come disciplina matematica è considerato l'articolo di Eulero (1736), che considerava il problema del ponte di Köningsberg. Eulero ha dimostrato che è impossibile aggirare sette ponti cittadini e tornare al punto di partenza passando su ogni ponte esattamente una volta. La teoria dei grafi ha ricevuto il suo prossimo impulso quasi 100 anni dopo con lo sviluppo della ricerca nelle reti elettriche, cristallografia, chimica organica e altre scienze.
Con i grafici, senza accorgercene, ci confrontiamo costantemente. Ad esempio, il grafico è lo schema delle linee della metropolitana. I punti su di esso rappresentano le stazioni e le linee rappresentano i percorsi dei treni. Esplorando la nostra genealogia ed elevandola a un lontano antenato, costruiamo il cosiddetto albero genealogico. E questo albero è un grafico.
I grafici servono come mezzo conveniente per descrivere le relazioni tra oggetti. In precedenza abbiamo utilizzato i grafici come un modo per visualizzare relazioni binarie finite.
Ma il grafico non è usato in alcun modo solo come illustrazione. Ad esempio, considerando un grafico che rappresenta una rete di strade tra insediamenti, possiamo determinare il percorso di viaggio dal punto A al punto B. Se esistono diversi percorsi di questo tipo, vorremmo scegliere quello ottimale in un certo senso, ad esempio il più breve o il più sicuro. Per risolvere il problema di selezione, è necessario eseguire determinati calcoli sui grafici. Quando si risolvono tali problemi, è conveniente utilizzare tecniche algebriche e il concetto stesso di grafico deve essere formalizzato.
I metodi della teoria dei grafi sono ampiamente utilizzati nella matematica discreta. È impossibile farne a meno nell'analisi e nella sintesi di vari convertitori discreti: blocchi funzionali di computer, complessi software, ecc.
Attualmente, la teoria dei grafi copre molto materiale ed è in fase di sviluppo attivo. Nel presentarlo, ci limitiamo solo a una parte dei risultati e ci concentriamo sulla descrizione e sulla giustificazione di alcuni algoritmi di analisi dei grafi ampiamente utilizzati nella teoria dei linguaggi formali.
Definizioni di base
I grafici, come già notato negli esempi, sono un modo per "visualizzare" i legami tra determinati oggetti, che possono essere "direzionali", come ad esempio in un albero genealogico, oppure "non direzionali" (una rete di strade a doppio senso). In accordo con ciò, nella teoria dei grafi si distinguono due tipi principali di grafi: diretto (o diretto) e non orientato.
Metodi di presentazione
Finora abbiamo definito grafi orientati e non orientati disegnandoli. È possibile definire un grafico come una coppia di insiemi, seguendo la definizione, ma questo metodo è piuttosto macchinoso ed è piuttosto di interesse teorico. Lo sviluppo di approcci algoritmici all'analisi delle proprietà dei grafi richiede altri modi di descrivere i grafi che sono più adatti per calcoli pratici, compresi quelli che utilizzano i computer. Considera i tre modi più comuni per rappresentare i grafici.
Alberi
Definizione 5.5. Un albero non orientato è un grafo non orientato connesso e aciclico. Definizione 5.6. Un albero orientato è chiamato grafo orientato senza contorno in cui l'ingrado di qualsiasi vertice è al massimo 1 e c'è esattamente un vertice, chiamato radice dell'albero orientato, il cui ingrado è 0.
Albero ricoprente di minor peso
Il seguente problema è noto nella teoria dei grafi come problema di Steiner: n punti sono dati sul piano; devi collegarli con segmenti di linea in modo tale che la lunghezza totale dei segmenti sia la più piccola.
Metodi per l'attraversamento sistematico dei vertici del grafo
Problemi importanti della teoria dei grafi sono i problemi dell'analisi globale di grafi orientati e non orientati. Questi compiti includono, ad esempio, i compiti di trovare cicli o contorni, calcolare le lunghezze dei percorsi tra coppie di vertici, elencare percorsi con determinate proprietà, ecc. L'analisi globale di un grafo va distinta da quella locale, un esempio del quale è il problema della determinazione degli insiemi di predecessori e successori di un vertice fisso di un grafo orientato.
Problema di cammino in grafi orientati pesati
Isomorfismo del grafico
Per un grafo orientato (V, E), l'insieme E di archi può essere visto come un grafo di una relazione binaria di raggiungibilità diretta definita sull'insieme dei vertici. In un grafo non orientato (V, E), l'insieme E degli spigoli è l'insieme delle coppie non ordinate. Per ogni coppia non ordinata (u, v) ∈ E, possiamo assumere che i vertici u e v siano connessi da una relazione binaria simmetrica p, cioè, (u, v) ∈ p e (v, u) ∈ p.
Ordinamento topologico
Definizione 5.17. Una rete orientata (o semplicemente una rete) è un grafo orientato senza contorno*. Poiché la rete è un grafico senza contorno, si può dimostrare che ci sono vertici (nodi) della rete con zero fuori grado, così come vertici (nodi) con zero dentro. I primi sono chiamati sink o uscite di rete, mentre i secondi sono chiamati sorgenti o ingressi di rete.
Elementi di ciclomatica
Quando si è discusso dell'algoritmo di ricerca in profondità in un grafo non orientato, è stata considerata la questione di trovare i cosiddetti cicli fondamentali di un grafo. Allo stesso tempo, un ciclo fondamentale è stato inteso come un ciclo contenente esattamente un bordo posteriore, ed è stata stabilita una corrispondenza biunivoca tra i cicli fondamentali e i bordi posteriori, i cicli fondamentali sorgono ogni volta non appena una partizione arbitraria di tutti i bordi di un grafo non orientato in quelli ad albero (che formano una foresta a punto singolo massimo del grafo originale) è fisso. grafico) e quelli inversi, e nel caso generale questa partizione può essere specificata in modo completamente indipendente dall'algoritmo di ricerca in profondità. Depth-First Search è solo uno dei modi per implementare tale partizione.
Il libro di K. Berzh è il primo sulla teoria dei grafici in russo. nel frattempo a l'anno scorso l'interesse per la teoria è notevolmente aumentato sia da parte dei matematici che dei rappresentanti di varie discipline. Ciò è spiegato dal fatto che i metodi della teoria dei grafi risolvono con successo numerosi problemi della teoria circuiti elettrici, teoria della catena di trasporto, teoria dell'informazione, cibernetica, ecc.
Nel libro di Berge, la teoria dei grafi è presentata in sequenza, a partire dalle fondamenta. Si presume che il lettore abbia una conoscenza matematica molto modesta, sebbene abbia una certa cultura matematica. Numerosi esempi, spesso divertenti, sono inclusi nel testo. Il libro può essere utilizzato per lo studio iniziale della teoria dei grafi. Anche i matematici-professionisti troveranno molte cose interessanti.
Algoritmo per l'identificazione diretta del ciclo di Eulero.
[Fleuri]. Considera un multigrafo connesso G, i cui vertici hanno tutti un grado pari, e prova a disegnarlo con un tratto, senza ricorrere a correzioni della parte già disegnata della traiettoria durante il processo di costruzione. È sufficiente attenersi alla seguente regola:
1 Lasciamo un vertice arbitrario a; Cancelliamo ogni bordo passato.
2 Non si percorre mai un tale spigolo u, che al momento in esame è un istmo (ovvero, alla rimozione del quale il grafo formato da spigoli non incrociati si sdoppia in due componenti connesse aventi almeno un spigolo ciascuna),
Osservando questa regola, saremo sempre in una posizione favorevole, perché quando siamo in x = a, il grafico (di spigoli non incrociati) ha due vertici di grado dispari: x e a; se scartiamo i vertici isolati, allora ci ritroviamo con un grafo connesso che, in virtù del Teorema 1, ha un cammino di Eulero che parte da x.
Contenuto
introduzione
Capitolo 1. Definizioni di base
Insiemi e mappature multivalore
Grafico. Percorsi e contorni
Catene e anelli
capitolo 2
Quasi-ordine definito da un grafo
Grafo induttivo e basi
capitolo 3
Grundy per il grafico infinito
Considerazioni generali per grafi infiniti
Funzione ordinale
Le funzioni di Grandi
Operazioni sui grafici
capitolo 4
Numero ciclomatico
Numero cromatico
Numero di stabilità interna
Numero di stabilità esterna
Capitolo 5
Teoremi di esistenza e unicità
Applicazione alle funzioni di Grandi
Capitolo 6
Gioco Nim
Definizione generale del gioco (con tutti i dettagli)
Strategie
Capitolo 7
Processi per stadi Alcune generalizzazioni
Capitolo 8. Reti di trasporto
Il problema della portata massima Il problema della portata minima
Il problema di un flusso multivalore compatibile
Reti di trasporto infinite
Capitolo 9
Grado di uscita e di entrata
Capitolo 10
Il problema del massimo abbinamento
Carenza di grafo semplice
algoritmo ungherese
Generalizzazione al caso infinito
Applicazione alla teoria delle matrici
Capitolo 11. Fattori
Cammini hamiltoniani e contorni hamiltoniani
Trovare un fattore
Trovare un grafico parziale con dati semigradi
Capitolo 12
Centri
Raggio
Capitolo 13
Proprietà generali di grafi fortemente connessi senza loop
Diametro
Capitolo 14
Applicazione di operazioni matriciali convenzionali
Compiti di conteggio
Problema capo
Applicazione di operazioni booleane
Capitolo 15
Matrici completamente unimodulari
Sistemi completamente unimodulari
Matrici ciclomatiche
Capitolo 16
Alberi
Studio analitico
greattrees
Capitolo 17
Cicli di Eulero Contorni di Eulero
Capitolo 18
Teoria dei circuiti alternati
Trovare un grafo parziale con determinati gradi di vertici
Corrispondenza perfetta
Applicazione al numero di stabilità interna
Capitolo 19
Cicli hamiltoniani e fattoreidi
Condizione necessaria e sufficiente per l'esistenza di un fattoreide
Capitolo 20
punti di articolazione
Grafici senza giunti
grafi h-connessi
Capitolo 21
Proprietà fondamentali
Generalizzazione
Aggiunte
I. Teoria generale, giochi
II. Informazioni sulle attività di trasporto
III. Sull'uso, concetti di potenzialità nelle reti di trasporto
IV. Problemi irrisolti e ipotesi non dimostrate
V. Su alcuni principi di base del conteggio (J. Riga)
VI. Aggiunte alla traduzione russa (A.A. Zykov e G.I. Kozhukhin)
Letteratura
Teoria dei grafi e libro di K. Berzh (postfazione alla traduzione russa)
Indice dei simboli
indice dei nomi
Indice per soggetto.
Download gratuito e-book in un formato conveniente, guarda e leggi:
Scarica il libro Teoria dei grafi e sue applicazioni, Berge K. - fileskachat.com, download veloce e gratuito.
UNIVERSITÀ PEDAGOGICA STATALE DI VLADIMIR
ASTRATTO
"TEORIA DEI GRAFICI"
Eseguita:
Zudina TV
Vladimir 2001
1. Introduzione
2. La storia dell'emergere della teoria dei grafi
3. Definizioni di base della teoria dei grafi
4. Teoremi fondamentali della teoria dei grafi
5. Compiti per l'applicazione della teoria dei grafi
6. Applicazione della teoria dei grafi nel corso scolastico di matematica
7. Applicazione della teoria dei grafi in vari campi della scienza e della tecnologia
8. Recenti progressi nella teoria dei grafi
§1. STORIA DELLA TEORIA DEI GRAFI.
Il matematico Leonhard Euler (1707-1783) è considerato il fondatore della teoria dei grafi. La storia dell'emergere di questa teoria può essere tracciata attraverso la corrispondenza del grande scienziato. Ecco una traduzione del testo latino, che è tratta dalla lettera di Eulero al matematico e ingegnere italiano Marinoni, inviata da San Pietroburgo il 13 marzo 1736 [cfr. pp. 41-42]:
"Una volta mi è stato proposto il problema di un'isola situata nella città di Konigsberg e circondata da un fiume attraverso il quale vengono gettati sette ponti. La domanda è se qualcuno possa aggirarli continuamente, passando solo una volta attraverso ogni ponte. fino ad ora non l'ha fatto stato in grado di farlo, ma nessuno ha dimostrato che sia impossibile. Questa questione, per quanto banale, mi è parsa però degna di attenzione perché né la geometria, né l'algebra, né l'arte combinatoria sono sufficienti per la sua soluzione... Dopo Dopo molte deliberazioni, ho trovato una regola facile, basata su una dimostrazione del tutto convincente, con l'aiuto della quale, in tutti i problemi di questo tipo, si può immediatamente determinare se un tale circuito può essere realizzato attraverso un numero qualsiasi e ponti arbitrariamente posizionati oppure no. in modo che possano essere rappresentati nella figura seguente[Fig. 1] , in cui UN sta per un'isola e B , C e D sono parti del continente separate l'una dall'altra dai rami del fiume. I sette ponti sono contrassegnati da lettere UN , B , C , D , e , F , G ".
(FIGURA 1.1)
Riguardo al metodo da lui scoperto per risolvere problemi di questo genere, Eulero scrive [vedi. pp. 102-104]:
"Questa soluzione, per sua natura, sembra avere poco a che fare con la matematica, e non mi è chiaro perché questa soluzione dovrebbe essere attesa da un matematico piuttosto che da qualsiasi altra persona, poiché questa soluzione è supportata solo dalla ragione, e non è necessario coinvolgere per trovare questa soluzione, alcuna legge inerente alla matematica, quindi non so come risulti che le domande che hanno ben poco a che fare con la matematica hanno maggiori probabilità di essere risolte dai matematici che da altri ".
Quindi è possibile aggirare i ponti di Königsberg passando una sola volta per ciascuno di questi ponti? Per trovare la risposta, continuiamo la lettera di Eulero a Marinoni:
"La domanda è determinare se è possibile aggirare tutti questi sette ponti, passandoci una sola volta, oppure no. La mia regola porta alla seguente soluzione a questa domanda. Prima di tutto, devi vedere quante sezioni sono separati dall'acqua - tali , che non hanno altra transizione dall'una all'altra, se non attraverso il ponte.In questo esempio, ci sono quattro di queste sezioni - UN , B , C , D . Successivamente, bisogna distinguere se il numero di ponti che conducono a queste singole sezioni è pari o dispari. Quindi, nel nostro caso, cinque ponti portano alla sezione A e tre ponti al resto, cioè il numero di ponti che portano alle singole sezioni è dispari, e questo è già sufficiente per risolvere il problema. Determinato questo, applichiamo la seguente regola: se il numero di ponti che portano ad ogni singola sezione fosse pari, allora il bypass in questione sarebbe possibile, e allo stesso tempo sarebbe possibile iniziare questo bypass da qualsiasi sezione. Se però due di questi numeri fossero dispari, giacché uno solo non può essere dispari, allora anche allora il passaggio potrebbe avvenire, come prescritto, ma solo l'inizio della circonvallazione deve necessariamente essere preso da uno di quei due tratti a cui il cavi numero dispari ponti. Se, infine, ci fossero più di due sezioni a cui conduce un numero dispari di ponti, allora un tale movimento è generalmente impossibile ... se qui si potessero citare altri problemi più seri, questo metodo potrebbe essere ancora più utile e non dovrebbe essere trascurato».
La motivazione della regola di cui sopra può essere trovata in una lettera di L. Euler al suo amico Eler datata 3 aprile dello stesso anno. Di seguito racconteremo un estratto di questa lettera.
Il matematico ha scritto che la transizione è possibile se non ci sono più di due aree nel tratto biforcuto del fiume, a cui conduce un numero dispari di ponti. Per rendere più facile immaginarlo, cancelleremo i ponti già passati nella figura. È facile verificare che se iniziamo a muoverci secondo le regole di Eulero, attraversiamo un ponte e lo cancelliamo, allora la figura mostrerà una sezione in cui ancora una volta non ci sono più di due aree a cui conduce un numero dispari di ponti, e in la presenza di zone con un numero dispari di ponti ci troveremo in una di esse. Continuando a muoverci così avanti, attraverseremo tutti i ponti una volta.
La storia dei ponti della città di Koenigsberg ha una continuazione moderna. Apriamo, ad esempio, un libro di testo scolastico sulla matematica curato da N.Ya. Vilenkin per la prima media. In esso, a pagina 98, sotto il titolo dello sviluppo della consapevolezza e dell'ingegno, troveremo un problema che è direttamente correlato a quello che Eulero risolse una volta.
Problema #569. Ci sono sette isole sul lago, che sono interconnesse come mostrato nella Figura 1.2. Su quale isola dovrebbe portare la barca i viaggiatori in modo che possano attraversare ogni ponte e solo una volta? Perché i viaggiatori non possono essere consegnati sull'isola UN ?
(FIGURA 1.2)
Soluzione. Poiché questo problema è simile al problema del ponte di Königsberg, useremo anche la regola di Eulero per risolverlo. Di conseguenza, otteniamo la seguente risposta: la barca deve portare i viaggiatori sull'isola E O F in modo che possano attraversare ogni ponte una volta. Dalla stessa regola di Eulero segue l'impossibilità della deviazione richiesta se parte dall'isola UN .
In conclusione, notiamo che il problema del ponte di Königsberg e problemi simili, insieme a un insieme di metodi per studiarli, costituiscono una branca della matematica molto importante in termini pratici, chiamata teoria dei grafi. Il primo lavoro sui grafici apparteneva a L. Euler e apparve nel 1736. Successivamente, Koenig (1774-1833), Hamilton (1805-1865) ha lavorato sui grafici, tra matematici moderni - K. Berzh, O. Ore, A. Zykov.
§2. PRINCIPALI TEOREMI DELLA TEORIA DEI GRAFI
La teoria dei grafi, come accennato in precedenza, è una disciplina matematica creata dagli sforzi dei matematici, quindi la sua presentazione include le necessarie definizioni rigorose. Quindi, procediamo all'introduzione organizzata dei concetti di base di questa teoria.
Definizione 2.01. Contareè una collezione di un numero finito di punti, chiamato picchi grafico e collegando a coppie alcuni di questi vertici di linee, chiamati costolette O archi grafico.
Questa definizione può essere formulata diversamente: contareè detto insieme di punti non vuoto ( picchi) e segmenti ( costolette), le cui due estremità appartengono a un dato insieme di punti (vedi Fig. 2.1).
(FIGURA 2.1)
Nel seguito verranno indicati i vertici del grafo con lettere latine UN , B ,C ,D. A volte il grafico nel suo insieme sarà indicato da una singola lettera maiuscola.
Definizione 2.02. Vengono chiamati i vertici di un grafo che non appartengono ad alcun arco isolato .
Definizione 2.03. Viene chiamato un grafo costituito solo da vertici isolati zero - contare .
Designazione: O " - un grafo con vertici che non ha spigoli (Fig. 2.2).
(FIGURA 2.2)
Definizione 2.04. Viene chiamato un grafo in cui ogni coppia di vertici è collegata da un arco completare .
Designazione: U " – grafico costituito da N vertici e bordi che collegano tutte le possibili coppie di questi vertici. Tale grafico può essere rappresentato come N- un quadrato in cui sono disegnate tutte le diagonali (Fig. 2.3).
(FIGURA 2.3)
Definizione 2.05. Grado picchiè il numero di spigoli a cui appartiene il vertice.
Designazione: P (UN) – grado di vertice UN . Ad esempio, nella Figura 2.1: P (UN)=2, P (B)=2, P (C)=2, P (D)=1, P (E)=1.
Definizione 2.06. Conteggio, grado di tutti K i cui vertici sono gli stessi è chiamato omogeneo contare gradi K .
Le figure 2.4 e 2.5 mostrano grafici omogenei di secondo e terzo grado.
(FIGURA 2.4 e 2.5)
Definizione 2.07. Supplemento dato contareè chiamato un grafo costituito da tutti gli spigoli e le loro estremità, che devono essere aggiunti al grafo originale per ottenere un grafo completo.
La Figura 2.6 mostra il grafico originale G , costituito da quattro vertici e tre segmenti, e nella Figura 2.7 - il complemento di questo grafico - il grafico G " .
(FIGURA 2.6 e 2.7)
Vediamo che in figura 2.5 le nervature AC E BD si intersecano in un punto che non è un vertice del grafico. Ma ci sono casi in cui un dato grafo deve essere rappresentato su un piano in modo tale che i suoi bordi si intersechino solo ai vertici (questo problema sarà considerato in dettaglio più avanti, nel paragrafo 5).
Definizione 2.08. Viene chiamato un grafo che può essere rappresentato in un piano in modo tale che i suoi bordi si intersechino solo ai vertici Piatto .
Ad esempio, la Figura 2.8 mostra un grafico planare che è isomorfo (uguale al) grafico della Figura 2.5. Tuttavia, si noti che non tutti i grafi sono planari, sebbene sia vero il contrario, cioè ogni grafo planare può essere rappresentato nel solito modo.
(FIGURA 2.8)
Definizione 2.09. Viene chiamato un poligono di un grafo planare che non contiene vertici o spigoli del grafo al suo interno bordo .