Anvendelse av grafteori i ulike aktivitetsfelt. Anvendelse av grafer

Begynnelsen av grafteorien tilskrives enstemmig 1736, da L. Euler løste problemet med Königsberg-broer, som var populært på den tiden. Imidlertid forble dette resultatet det eneste resultatet av grafteori i mer enn hundre år. Først på midten av 1800-tallet utviklet elektroingeniøren G. Kirchhoff teorien om trær for studiet av elektriske kretsløp, og matematikeren A. Cayley løste i forbindelse med beskrivelsen av hydrokarbonene opptellingsproblemer for tre. typer trær.

Født fra å løse gåter og underholdende spill (problemer om en sjakkridder, om dronninger, "reise rundt i verden", problemer om bryllup og harem, etc.), har grafteori nå blitt et enkelt, tilgjengelig og kraftig middel for å løse problemer relatert til et bredt spekter av problemer. Grafer er bokstavelig talt allestedsnærværende. I form av grafer kan du for eksempel tolke veikart og elektriske kretser, geografiske kart og molekyler kjemiske forbindelser, forbindelser mellom mennesker og grupper av mennesker. I løpet av de siste fire tiårene har grafteori blitt en av de raskest utviklende grenene innen matematikk. Dette er drevet av kravene til et raskt voksende applikasjonsfelt. Det brukes i design av integrerte kretser og kontrollkretser, i studiet av automater, logiske kretser, programblokkdiagrammer, i økonomi og statistikk, kjemi og biologi, i planleggingsteori. I stor grad trenger matematiske metoder nå gjennom vitenskap og teknologi gjennom grafteori.

Denne artikkelen undersøker ikke de riktige problemene med grafteori, men hvordan den brukes i et skolegeometrikurs.

Derfor skyldes forskningstemaets relevans på den ene siden populariteten til grafer og relaterte forskningsmetoder, som organisk gjennomsyrer ulike nivåer nesten all moderne matematikk, og på den annen side er det ikke utviklet et helhetlig system for dens implementering i geometrikurset.

Hensikten med studien er å studere bruken av grafer i et skolegeometrikurs.

Målet er prosessen med å undervise i geometri.

Fag – klasse og utenomfaglig arbeid

Mål: 1) bestemme essensen og innholdet i bruken av grafer i et skolegeometrikurs;

2) utvikle en PMC for gjennomføring av geometritimer i klasse 7-9.

Det ledende emnet er konstruksjonen av en grafmodell for å bevise geometriske teoremer.

Teoretisk grunnlag:

1. Grafteori, som oppsto i 1736 (Leonard Euler (1708-1783), fikk en rask utvikling og er fortsatt relevant i dag, fordi i Hverdagen Grafiske illustrasjoner, geometriske representasjoner og andre teknikker og metoder for visualisering brukes i økende grad.

1. Grafteori brukes i ulike områder av moderne matematikk og dens mange anvendelser (Lipatov E. P.)

2. Grafteori brukes i slike områder av matematikken som matematisk logikk, kombinatorikk osv.

Den teoretiske betydningen av arbeidet ligger i:

Identifisering av bruksområder for grafteori;

Bruke grafteori for å studere geometriske teoremer og problemer;

Den praktiske betydningen av arbeidet ligger i bruken av grafer for å bevise geometriske teoremer og løse problemer.

Som et resultat av dette arbeidet ble følgende opprettet:

Programvare og metodisk kompleks for gjennomføring av geometritimer i 7.-9.

Det vanskeligste med å finne en løsning på et problem er å etablere en kjede av logiske konsekvenser som fører til et bevist utsagn. For å resonnere logisk kompetent, er det nødvendig å utvikle ferdighetene til slik tenkning som vil bidra til å bygge ulike geometriske fakta inn i logiske forhold.

For å utvikle ferdighetene til en tenkekultur, spiller former for skriftlig tale til elever en spesiell rolle. Skriftlige arbeidsformer er den viktigste aktivitetstypen som utvikler stabile ferdigheter i logisk resonnement når man skal bevise teoremer og løse problemer. Formen for å registrere forholdene til problemet, rimelige forkortelser og notasjoner i beregninger og bevis på problemer disiplinerer tenkning og fremmer geometrisk syn. Som du vet, gir syn fødsel til tenkning. Et problem oppstår: hvordan etablere logiske sammenhenger mellom ulike geometriske fakta og hvordan man danner dem til en enkelt helhet. Metoden med grafdiagrammer lar deg se fremdriften med å bevise teoremer og løse problemer, noe som gjør beviset mer visuelt og lar deg kort og nøyaktig presentere bevisene for teoremer og løse problemer.

En tregraf brukes til dette.

Toppene til "treet" (betingelsene til teoremet eller problemet og sekvensen av logiske koblinger) er avbildet av rektangler med informasjon plassert i dem, som deretter er forbundet med piler. Slutten av grafdiagrammet inneholder utsagnet som skal bevises. Den beskrevne formen for å bevise teoremer og løse problemer er nyttig og praktisk for studenter, siden den gjør det mulig å enkelt identifisere hovedstadiene for å bevise teoremene og løse problemet.

Forskningsdel.

Del 1. Studie av historien om fremveksten av grafteori.

Grunnleggeren av grafteori regnes for å være matematikeren Leonhard Euler (1707-1783). Historien til denne teorien kan spores gjennom korrespondansen til den store vitenskapsmannen. Her er en oversettelse av den latinske teksten, som er hentet fra Eulers brev til den italienske matematikeren og ingeniøren Marinoni, sendt fra St. Petersburg 13. mars 1736.

"Jeg ble en gang spurt om et problem om en øy som ligger i byen Königsberg og omgitt av en elv som syv broer blir kastet over. Spørsmålet er om noen kan gå rundt dem kontinuerlig og bare passere én gang gjennom hver bro. Og så ble jeg informert om at ingen fortsatt ikke kunne gjøre dette, men ingen har bevist at det er umulig. Dette spørsmålet, selv om det var trivielt, virket for meg imidlertid verdig oppmerksomhet ved at verken geometri, algebra eller kombinatorisk kunst er tilstrekkelig til å løse Etter mye omtanke fant jeg en enkel regel, basert på et fullstendig overbevisende bevis, ved hjelp av hvilken det er mulig umiddelbart å fastslå i alle problemer av denne typen om en slik omvei kan gjøres gjennom et hvilket som helst antall broer som ligger i hvilken som helst måte eller ikke, slik at de kan representeres i følgende figur, der A betegner øya, og B, C og D delene av kontinentet som er adskilt fra hverandre av elvegrener. De syv broene er betegnet med bokstavene a, b, c, d, e, f, g ".

Angående metoden han oppdaget for å løse problemer av denne typen, skrev Euler

"Denne løsningen, i sin natur, har tilsynelatende lite med matematikk å gjøre, og jeg forstår ikke hvorfor man skal forvente denne løsningen fra en matematiker i stedet for fra noen annen person, for denne avgjørelsen støttes av resonnement alene, og det er ingen må involvere for å finne denne løsningen, eventuelle lover som er iboende i matematikk. Så jeg vet ikke hvordan det viser seg at spørsmål som har veldig lite med matematikk å gjøre, er mer sannsynlig å bli løst av matematikere enn av andre."

Så er det mulig å komme seg rundt Königsberg-broene ved å passere én gang over hver av disse broene? For å finne svaret, la oss fortsette Eulers brev til Marinoni:

"Spørsmålet er å finne ut om det er mulig å omgå alle disse syv broene, passere gjennom hver enkelt én gang eller ikke. Min regel fører til følgende løsning på dette spørsmålet. Først av alt må du se på hvor mange områder det er er, atskilt med vann - slike , som ikke har noen annen passasje fra en til en annen, bortsett fra gjennom en bro.I dette eksemplet er det fire slike seksjoner - A, B, C, D. Deretter må du skille om tallet av broer som fører til disse individuelle seksjonene er partall eller oddetall. Så i vårt tilfelle fører fem broer til seksjon A, og tre broer hver til resten, dvs. antallet broer som fører til individuelle seksjoner er oddetall, og dette alene er nok for å løse problemet Når dette er bestemt, bruker vi følgende regel: hvis antallet broer som fører til hver separat seksjon var jevnt, ville den aktuelle omkjøringen vært mulig, og samtidig ville det være mulig å starte denne omvei fra en hvilken som helst seksjon. Hvis imidlertid to av disse tallene var hvis de var odde, fordi bare ett ikke kan være oddetall, så kan overgangen fullføres, som foreskrevet, men bare begynnelsen av omveien må absolutt tas fra en av de to seksjonene som et oddetall av broer fører til. Hvis det endelig var mer enn to seksjoner som et oddetall broer fører til, ville en slik bevegelse i det hele tatt være umulig; hvis andre, mer alvorlige problemer kunne bringes hit, kunne denne metoden være til enda større nytte og burde ikke bli neglisjert."

Begrunnelsen for ovennevnte regel finnes i et brev fra L. Euler til sin venn Ehler datert 3. april samme år. Nedenfor skal vi gjenfortelle et utdrag fra dette brevet.

Matematikeren skrev at overgangen er mulig hvis det ikke er mer enn to områder i elvens gaffel, som et oddetall broer fører til. For å gjøre det lettere å forestille seg dette, vil vi slette de allerede kryssede broene på figuren. Det er lett å sjekke at hvis vi begynner å bevege oss i samsvar med Eulers regler, krysser en bro og sletter den, så vil figuren vise et utsnitt hvor det igjen ikke er mer enn to områder som et oddetall broer fører til, og hvis det er områder med et oddetall broer vi vil ligge i en av dem. Fortsetter vi å gå videre slik, vil vi krysse alle broene en gang.

Historien om broene til byen Königsberg har en moderne fortsettelse.

Oppgave Det er syv øyer på innsjøen, som er forbundet med hverandre som vist i figur 2. Til hvilken øy skal en båt ta reisende slik at de kan krysse hver bro og kun én gang? Hvorfor kan ikke reisende transporteres til øy A?

Løsning. Siden dette problemet ligner problemet med Königsberg-broene, vil vi også bruke Eulers regel når vi løser det. Som et resultat får vi følgende svar: Båten må ta reisende til øy E eller F slik at de kan krysse hver bro én gang. Fra den samme Euler-regelen følger det at den nødvendige omveien er umulig hvis den starter fra øy A.

Deretter arbeidet Koenig (1774-1833), Hamilton (1805-1865) og moderne matematikere C. Berge, O. Ore, A. Zykov med grafer.

Historisk sett oppsto grafteori for mer enn to hundre år siden i prosessen med å løse gåter. I veldig lang tid var hun på sidelinjen av hovedretningene for vitenskapelig forskning, i matematikkens rike var hun i posisjonen til Askepott, hvis talenter ble fullstendig avslørt først da hun befant seg i sentrum av generell oppmerksomhet.

Det første verket om grafteori, eid av den kjente sveitsiske matematikeren L. Euler, dukket opp i 1736. Grafteori fikk en drivkraft for utvikling ved overgangen til 1800- og 1900-tallet, da antallet verk innen topologi og kombinatorikk , som det er nært knyttet til, kraftig økt slektskap. Grafer begynte å bli brukt i konstruksjonen av elektriske kretsdiagrammer og molekylære kretser. Som en egen matematisk disiplin ble grafteori først presentert i arbeidet til den ungarske matematikeren Koenig på 30-tallet av det tjuende århundre.

I det siste har grafer og relaterte forskningsmetoder organisk gjennomsyret nesten all moderne matematikk på ulike nivåer. Grafteori regnes som en av topologiens grener; det er også direkte relatert til algebra og tallteori. Grafer brukes effektivt i planleggings- og kontrollteori, planleggingsteori, sosiologi, matematisk lingvistikk, økonomi, biologi, medisin og geografi. Grafer er mye brukt innen områder som programmering, finite state machine theory, elektronikk, i løsning av sannsynlighets- og kombinatoriske problemer, korteste avstand osv. Matematisk underholdning og puslespill er også en del av grafteori. Grafteori utvikler seg raskt og finner nye applikasjoner.

Seksjon 2. Grunnleggende typer, begreper og struktur av grafer.

Grafteori er en matematisk disiplin skapt av matematikeres innsats, derfor inkluderer presentasjonen de nødvendige strenge definisjonene.

En graf er en samling av et begrenset antall punkter, kalt toppunkter på grafen, og linjer som forbinder noen av disse toppunktene i par, kalt kanter eller buer på grafen.

Nr Navn på graf Definisjon Figur Eksempel på bruk av denne typen graf

1 Null graf Topppunkter på grafen som ikke hører hjemme Oppgave: Arkady, Boris. Vladimir, Grigory og Dmitry utvekslet håndtrykk på møtet; hver håndhilste på hverandre én gang. Hvor mange kanter det er kalles isolerte. ble håndtrykk utført? Situasjonen som tilsvarer øyeblikket da håndtrykk ennå ikke er utført, er punktmønsteret vist i figuren.

En graf som kun består av isolerte toppunkter kalles en nullgraf.

Notasjon: O" - en graf med hjørner og ingen kanter

2 Komplette grafer En graf der hvert par av hjørner Legg merke til at hvis en komplett graf har n hjørner, vil antall kanter være Alle håndtrykk er fullført.

Betegnelse: U" - en graf bestående av n 10.

toppunkter og kanter som forbinder alle mulige par av disse toppunktene. En slik graf kan representeres som en n-gon der alle diagonaler er tegnet

3 Ufullstendige grafer Grafer der alle håndtrykk ennå ikke er fullført, håndtrykk A og B, A og D, D og mulige kanter er ristet, kalles ufullstendig G, C og D.

4 Bane i grafen. Syklus. En sti i grafen fra et toppunkt til et annet. Ved punkt A er det en garasje for en snøplog. Føreren av bilen ble tilkalt for å fjerne snø fra gatene i bydelen som er vist på bildet. Kan han ha en rekke kanter langs som han kan fullføre arbeidet i krysset der garasjen er plassert, hvis sjåføren kan passere hver gate mellom disse gatene i sin del av byen bare én gang?

topper.

I dette tilfellet skal ingen kant av ruten vises mer enn én gang. Toppunkt, fra Det er umulig, siden en lukket bane som går langs alle kanter av grafen, og langs hvilken ruten legges, sies å eksistere for hver kant bare én gang, hvis gradene til alle toppunktene på grafen er jevne.

begynnelsen av stien, toppen på slutten av ruten -

slutten på veien. En syklus er en sti der figuren ved hjelp av en graf viser et diagram over veier mellom befolkede områder hvis begynnelse og slutt faller sammen. I enkle punkter.

en syklus er en syklus som ikke passerer. For eksempel kan fra punkt A (toppunktet på grafen) til punkt H nås via ulike ruter: ADGH, AEH, AEFCEH, ABCEH.

gjennom en av toppunktene på grafen mer enn én Hvordan skiller ruten AEH seg fra ruten AEFCEH?

ganger. For på den andre ruten besøkte vi "krysset" ved punkt E to ganger.

Denne ruten er lengre enn AEH. AEH-ruten kan fås fra ruten

Hvis syklusen inkluderer alle kantene AEFCEH, "krysser" FCE-ruten fra den siste.

graf en gang om gangen, så er en slik syklus Rute AEH en sti i grafen, men rute AEFCEH er ikke en sti.

kalt Euler-linjen.

Tilkoblede og frakoblede grafer. Bestemmelse 1: Er det mulig å lage en ramme av en kube med en kantlengde fra en ledning på 12 dm

Kalles to toppunkter i en graf koblet, 1 dm, uten å bryte ledningen i biter?

hvis det er en bane i grafen med ender ved disse toppunktene. Hvis en slik bane ikke eksisterer, sies toppunktene ikke å være sammenkoblet.

Siden en bane som går langs alle kanter av grafen, og langs hver kant bare én gang, eksisterer bare i følgende tilfeller:

1) når graden av hvert toppunkt er jevn (banen er stengt)

2) når det bare er to toppunkter med en oddetall.

Definisjon 2:

En graf kalles koblet hvis et hvilket som helst par av toppunktene er koblet sammen.

En graf kalles frakoblet hvis den har minst ett frakoblet toppunktpar.

6 Trær Et tre er en hvilken som helst tilkoblet graf, vedlegg nr. 1. Slektstre til Zholmurzaeva Tomiris.

topper. En frakoblet graf som utelukkende består av trær kalles en skog.

7 isomorfe grafer. Grafene vist i figuren gir samme informasjon. Slike grafer kalles isomorfe (identiske).

8 Konseptet med en plan graf En graf som kan representeres på oppgaven. Tre fly bor i tre forskjellige hus og naboer har kranglet seg imellom. Ikke langt fra husene deres, der ribbene krysser hverandre, er det tre brønner. Er det mulig fra bare på toppene, kalt hvert hus å legges flatt til hver av brønnene. sti slik at ikke to av dem krysser hverandre?

Løsning: Etter å ha tegnet åtte stier, kan du forsikre deg om at det ikke er mulig å tegne en niende som ikke krysser noen av de tidligere tegnede banene.

La oss konstruere en graf hvis toppunkter

A, B, C, 1, 2, 3

forholdene til problemet tilsvarer hus og brønner, og vi skal prøve å bevise at den niende banen - en kant på grafen som ikke skjærer de andre kantene - ikke kan tegnes.

Kantene tegnet i grafen i figuren

A1, A2, A3 og B1, B2, VZ (tilsvarer stiene fra hus A og B til alle brønner).

Den konstruerte grafen delte planet inn i tre regioner: X, Y, Z. Toppunkt B, avhengig av plasseringen på planet, faller inn i en av disse tre regionene. Hvis du vurderer hvert av de tre tilfellene av å "treffe" toppunktet

B til et av områdene X, Y eller Z, og sørg for at hver gang en av toppunktene på grafen er 1, 2 eller 3

(en av brønnene) vil være "utilgjengelig" for toppunkt B (det vil si at det ikke vil være mulig å tegne en av kantene B1, B2 eller B3 som ikke vil krysse kantene som allerede eksisterer i grafen).

Svaret på problemspørsmålet vil være: "Nei!"

Rettede grafer En kant av en graf kalles en rettet kant hvis en av toppunktene regnes som begynnelsen og den andre slutten av denne kanten.

En graf der alle kanter er rettet kalles en rettet graf.

Så jeg gjennomgikk de grunnleggende konseptene for grafteori, uten hvilke det ville være umulig å bevise teoremer, og følgelig løse problemer.

Konklusjon på arbeidet som er utført:

Jeg lærte å strukturere alt informasjonsmateriell i en tabell;

Ordning teoretisk materiale bidra til en visuell forståelse av typene grafer og deres anvendelse;

Jeg jobbet med eksempler på bruk av grafteori i utarbeidelsen av slektstreet mitt.

Vedlegg nr. 1.

GENEOLOGISK TRE

Konstruer et slektstre av Zholmurzaeva Tomiris.

Løsningsmetode.

Grafisk måte å løse problemet på.

En grafisk måte å løse problemet på er å tegne et "tre av logiske forhold". "Tre" uttrykker i form av en enkel tegning det logiske forholdet mellom slektninger. Hver generasjon på treet tilsvarer én gren.

Jeg tok slektstreet mitt som et eksempel.

Del 3. Anvendelse av grafteori.

Vi møter grafer oftere enn det er mulig ved første øyekast. Eksempler på grafer inkluderer et hvilket som helst veikart, elektrisk diagram, tegning av polygoner osv. Lenge trodde man at grafteori hovedsakelig brukes til å løse logiske problemer. Når man løser logiske problemer, er det ofte vanskelig å huske de mange forholdene gitt i oppgaven og etablere sammenhenger mellom dem. Grafer hjelper til med å løse slike problemer, og gjør det mulig å visuelt representere sammenhengene mellom dataene i problemet. Grafteori i seg selv ble ansett som en del av geometri. Imidlertid ble det på det tjuende århundre funnet brede anvendelser av grafteori innen økonomi, biologi, kjemi, elektronikk, nettverksplanlegging, kombinatorikk og andre felt innen vitenskap og teknologi. Som et resultat begynte den å utvikle seg raskt og ble til en uavhengig forgrenet teori.Løsningen av mange matematiske problemer er forenklet hvis det er mulig å bruke grafer. Å presentere data i form av en graf gjør det klarere. Mange bevis blir også forenklet og blir mer overbevisende hvis du bruker grafer.

3. 1. Anvendelse av grafer i geometriske oppgaver og teoremer.

Ved hjelp av grafer kan du enkelt etablere kjeder av logiske konsekvenser som fører til at påstanden blir bevist. Gi kort og nøyaktig bevis for teoremet og løsningen på oppgaven.

Bevis at for en likebenet trekant er halveringslinjene trukket fra hjørnene ved bunnen like.

Metoder for løsninger.

Bevis på problemet ved å bruke resonnement.

La ABC være en likebenet trekant med

B1 A1 base AB og halveringslinjer AA1 og BB1.

La oss vurdere ∆АВВ1 og ∆ВАА1. De har ∟В1АВ=

∟A1BA som vinklene ved bunnen av den likebenede trekanten ∆ABC. ∟АВВ1= ∟А1АВ

A B siden AA1 og BB1 er halveringslinjene til vinklene ved bunnen av en likebenet trekant. AB er fellessiden. Midler

∆АВВ1 = ∆ВАВ1 langs siden og to tilstøtende vinkler. Fra trekantenes likhet følger det at sidene deres AA1 og BB1 er like.

Bevis på problemet ved hjelp av en graf.

Bevis: AA=BB

Vi bruker grafen til resonnement. Toppunktene i grafen er betingelsene for teoremet eller problemet og stadiene av beviset.

Kantene på grafen er logiske konsekvenser. Slutten av grafdiagrammet er et bevisbart utsagn.

Farge brukes til å fremheve komponentene. Teoremet og problemforholdene er blå. Utsagnet som bevises er rødt. Stadier av bevis - svart.

Den beskrevne formen for å bevise teoremer og løse problemer er nyttig og praktisk for studenter, siden den gjør det mulig å fremheve hovedstadiene for å bevise teoremer og løse problemet.

3. 2. Programvare og metodologisk kompleks.

a) Lærerhåndbok.

Den foreslåtte manualen er satt sammen i samsvar med læreboken om geometri for klasse 7-9 av A.V. Pogorelov. Hovedformålet er å gi prosessen med å studere geometri de nødvendige visuelle hjelpemidlene, for å hjelpe læreren med å undervise i geometri: å lette prosessen med å bevise teoremer, mestre teoretisk materiale i prosessen med å løse problemer. Grafdiagrammer er mangefasettert og kan, avhengig av klassenes mål og form, brukes på forskjellige måter: som illustrerende, rettet mot å øke klarheten når man forklarer nytt teoretisk materiale, ved generalisering og systematisering av nytt materiale (grafdiagrammer med teoremer); som kort brukt ved gjennomføring av individuelle og frontale undersøkelser (grafdiagrammer med oppgaver). Denne håndboken kommer med en elevarbeidsbok. En arbeidsbok kan brukes til å organisere selvstendig arbeid elever i og etter skoletid.

b) Arbeidsbok for studenter.

Manualen er laget i form av en arbeidsbok. Manualen inneholder 28 grafdiagrammer med teoremer og 28 grafdiagrammer med oppgaver. Grafiske diagrammer inneholder hovedprogrammaterialet, som presenteres med nødvendig klarhet og representerer løsningens rammeverk. Elevene fyller sekvensielt ut de tomme cellene med informasjon som utgjør løsningen på problemet.

Farge brukes til å fremheve komponentene. Betingelsene for teoremet og problemet er blå, utsagnet som skal bevises er rødt, stadiene i beviset er svarte.

Manualen er nyttig for elever i 7.-9.

c) Elektronisk manual.

Resultater av arbeidet og deres diskusjon. Prosjektet er et resultat av en toårig studie av bruk av grafer i et skolematematikkkurs.

Oppretting programmatisk – metodologisk kompleks og implementeringen ble utført under:

Gjennomføre klasser for Aristoteles-klubben om emnet "Løse logiske problemer ved hjelp av grafer."

Anvendelser av grafer i bevis for geometriske teoremer og problemer

I geometritimer på 8. og 9. klassetrinn.

Presentasjoner med prosjekt på skolen vitenskapelig og praktisk konferanser.

KONKLUSJON.

Ved å oppsummere resultatene av studien av bruken av grafer i et skolegeometrikurs, kom jeg til følgende konklusjon:

1. Fordelen med grafbevis for teoremer og problemløsning fremfor den tradisjonelle er illustrasjonen av dynamikken til bevis for teoremer og problemer.

2. Introduksjon til prosessen med å bevise geometriske teoremer og problemer med grafskjemametoden bidrar til å styrke elevenes ferdigheter i å konstruere et bevis.

3. Utviklet programvare og metodisk kompleks for å studere geometri i klasse 7-9: a) lærerhåndbok; b) arbeidsbok for studenter; c) den elektroniske manualen er nyttig for elever i 7.-9.

Pedagogisk utgave

Yuyukin Nikolay Alekseevich

LR-nr. Signert for segl

Uch. Ed. l.. , .

Voronezh State Technical University

394026 Voronezh, Moskovsky-prospektet. 14

KATALOG OVER MAGNETISK DISKE

Institutt for høyere matematikk og fysisk og matematisk modellering

PÅ. Yuyukin

DISKRET MATEMATIKK Del 1. Elementer i grafteori

Opplæringen

PÅ. Yuyukin

DISKRET MATEMATIKK Del 1. Elementer i grafteori

Opplæringen

Voronezh 2004

INTRODUKSJON

Denne håndboken kan brukes i kurset "Diskret matematikk" av VSTU-studenter som studerer i følgende spesialiteter:

090102 – Datasikkerhet;

090105 – Omfattende informasjonssikkerhet for automatiserte systemer;

090106 - Informasjonssikkerhet for telekommunikasjonssystemer.

Disiplinen "Diskret matematikk" sikrer tilegnelse av kunnskap og ferdigheter i henhold til statens, allmennutdanningsstandard, og bidrar samtidig til tilegnelsen grunnleggende utdanning, dannelse av verdensbilde og utvikling av logisk tenkning.

Grafteori er et effektivt verktøy for å formalisere moderne ingeniørproblemer knyttet til diskrete objekter. Det brukes i design av integrerte kretser og kontrollkretser, studiet av automatiske maskiner og logiske kretser, i system analyse, automatisert produksjonskontroll, i utvikling av data- og informasjonsnettverk, i kretsdesign og design-topologisk design, etc.

I lærebok skisserer det grunnleggende, grunnleggende metoder og algoritmer for grafteori. Her presenterer vi n-grafer og digrafer; isomorfismer; trær; Euler-grafer; plane grafer; belegg og uavhengige sett; sterk tilkobling

V digrafer; Markov kjede graf analyse; algoritmer for å finne korteste veier i grafer; Hamiltonian-sykkelsøkeproblem

V kurve; reisende selger problem; oppregning av grafer og kartlegginger; ekstreme oppgaver; optimaliseringsproblemer; universelle oppgaver; gren og bundet metode; og også utvikle praktiske ferdigheter i å bruke begrepene ovenfor.

Målet med kurset er å utvikle studentenes teoretiske kunnskaper, praktiske ferdigheter og evner innen modellering av prosesser og fenomener innen naturvitenskap og teknologi.

ke, med evnen til å bruke matematiske symboler for å uttrykke de kvantitative og kvalitative relasjonene til objekter som er nødvendige for å utføre offisielle aktiviteter innen informasjonssikkerhet på et høyt faglig nivå.

Følgende oppgaver tjener for å nå dette målet:

studere det bredest mulige spekteret av grafteoretiske konsepter;

få ferdigheter i å løse pedagogiske og praktiske problemer;

mestre optimaliseringsmetoder;

utvikle ferdigheter i å sette og løse informasjonsproblemer, modellere og analysere informasjon ved hjelp av grafer.

Disiplinen "Diskret matematikk" er en av de anvendte matematiske disiplinene. Den er basert på kunnskapen studentene har tilegnet seg mens de studerte disiplinene "Algebra" og "Matematisk logikk og teori om algoritmer". Kunnskapen og ferdighetene tilegnet i studiet av disiplinen "Diskret matematikk" brukes i studiet generell profesjonell og spesielle disipliner.

1. GRUNNLEGGENDE KONSEPT FOR GRAFTEORIEN.

1.1. Problemer med grafteori.

Grafteori er en gren av matematikken som studerer systemer av sammenhenger mellom ulike objekter, akkurat som man gjør med begrepet en relasjon. En uavhengig definisjon av grafen forenkler imidlertid presentasjonen av teorien og gjør den mer forståelig og visuell.

De første problemene med grafteori var relatert til å løse underholdningsproblemer og gåter.

Første oppgave. Problemet med Königsberg-broene ble stilt og løst av Euler i 1786. Byen lå på bredden og to øyer av Pregolya-elven. Øyene var forbundet mellom hverandre og breddene med syv broer, som vist på figuren.

Spørsmålet oppsto: er det mulig å forlate huset og gå tilbake, krysse hver bro nøyaktig én gang?

Andre oppgave. Problemet med tre hus og tre brønner. Det er tre hus og tre brønner.

Det er påkrevd å tegne en sti fra hvert hus til hver brønn slik at stiene ikke krysser hverandre. Oppgaven var

løst av Pontryagin og uavhengig av ham av Kuratovsky i

Tredje oppgave. Omtrent fire farger. Fargelegg et hvilket som helst kart på et plan med fire farger slik at ikke to tilstøtende områder males med samme farge.

Mange resultater fra grafteori brukes til å løse praktiske problemer innen naturvitenskap og teknologi. På midten av 1800-tallet brukte Kirchhoff således grafteori for å beregne komplekse elektriske kretser. Men som en matematisk disiplin ble grafteori først dannet på 30-tallet av det 20. århundre. I dette tilfellet betraktes grafer som noen abstrakte matematiske objekter. De brukes i analyse og syntese av kretser og systemer, i nettverksplanlegging og -styring, operasjonsforskning, programmering, modellering av livet til en organisme og andre områder.

1.2. Grunnleggende definisjoner.

En graf G= (V,E) er en samling av to sett - et ikke-tomt sett med toppunkter V og et sett med uordnede og ordnede par med toppunkt E. I det følgende vil vi vurdere endelige grafer, dvs. grafer med et begrenset sett med toppunkter og en endelig familie av par. Et uordnet par av hjørner kalles en kant, og et ordnet par kalles en bue.

Vanligvis er en graf representert av et diagram: toppunkter er prikker (eller sirkler), kanter er linjer med vilkårlig konfigurasjon. En pil indikerer i tillegg retningen på buen. Vær oppmerksom på at når du viser en graf, er bæreren

de geometriske egenskapene til ribbene (lengde, krumning), samt gjensidig ordning hjørner på planet.

Topper som ikke tilhører noen kant (bue) kalles isolerte. Topppunkter forbundet med en kant eller bue kalles tilstøtende. En kant (bue) og hvilken som helst av dens to toppunkter kalles hendelse.

De sier at en kant (u,v) forbinder toppunktene u og v, og en bue (u,v) starter ved toppunktet u og slutter ved toppunktet v, med u kalt begynnelsen og v slutten av denne buen.

Et par hjørner kan kobles sammen med to eller flere kanter (buer i samme retning). Slike kanter (buer) kalles multiple. En bue (eller kant) kan starte eller slutte ved samme toppunkt. En slik bue (kant) kalles en løkke. En graf som inneholder looper kalles en pseudograf. En graf som har flere kanter (buer) kalles en multigraf.

En graf uten løkker eller flere kanter kalles enkel. En enkel graf kalles komplett hvis det er en kant (bue) for et hvilket som helst par av hjørnene som forbinder dem. En fullstendig graf med n toppunkter er betegnet med K n. Dette er for eksempel grafer

En graf som består av ett isolert toppunkt (K 1) kalles trivielt.

Komplementet til en graf G er en graf G som har de samme toppunktene som grafen G og inneholder de kantene som må legges til grafen G for å få en fullstendig graf.

Til alle ikke-digrafer kanonisk samsvarer en rettet graf med samme sett med toppunkter, der hver kant er erstattet av to buer som faller inn på de samme toppunktene og har motsatte retninger.

1.3. Grader av grafens toppunkter.

Graden (valens) (notasjon d (v) eller deg (v)) til et toppunkt v i en enkel graf G er antallet kanter eller buer som faller inn på et gitt toppunkt v. Når du beregner valensen til toppunktene til en pseudograf, bør hver løkke telles to ganger.

Hvis gradene til alle toppunktene i en n-graf er lik k, kalles grafen vanlig (uniform) grad k. Hvis graden av et toppunkt er 0, er det isolert. Hvis graden av et toppunkt er 1, kalles toppunktet et terminalt toppunkt (hengende, blindvei).

For en digraf kalles antallet buer som kommer fra toppunktet v

varierer halvgrad av utfall				(v), og innkommende – semi-trinn-

ny samtale d			(v), I dette tilfellet er relasjonen d (v)=

	(v)+	(v).

Eulers teorem: Summen av gradene av toppunktene til en graf er

doble antall ribber, dvs.

d(vi)



			(v)

Hvor n er antall toppunkter; m – tall

ribber (buer). Denne påstanden er bevist av det faktum at når man beregner summen av grader av hjørner, tas hver kant i betraktning to ganger - for den ene enden av kanten og for den andre.

1.4. Grafisk isomorfisme.

En graf kalles merket (eller omnummerert) hvis toppunktene skiller seg fra hverandre på en eller annen måte.

etiketter (tall). Antallet vurderes fullstendig gitt i streng forstand, hvis nummereringen av verteksene og kantene er fast. I dette tilfellet kalles grafene G 1 og G 2 like (betegnelse G 1 = G 2), hvis settene med toppunkter og kanter faller sammen. To grafer eller pseudografer G 1 = (V 1 ,E 1 ) og G 2 = (V 2 ,E 2 ) kalles

	isomorf (notasjon G	hvis de eksisterer

	en-til-en-tilordninger: 1)	: V 1 V 2
: E 1 E 2 slik at for alle to hjørner u, v i grafen
	relasjonen ((u, v)) ((u), (v)) er gyldig.

	To enkle grafer (uten løkker og flere kanter) G 1		og G 2

vise seg å være isomorfe hvis det er gjensidig identiske

verdikartlegging

: V 1 V 2

Hva så?

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

Dermed er grafer som bare skiller seg i nummereringen av toppunkter og kanter isomorfe. Grafisomorfisme er en ekvivalensrelasjon fordi den har egenskapene:

Refleksivitet -

G1,

og bijeksjonen

er en identisk funksjon.

Symmetri.

med bijeksjon

Transitivitet.

G 1 G 2

bijeksjon

1,a

med bijeksjon

deretter G G

med bijeksjon

2 (1 ) .

Grafteori finner anvendelse, for eksempel i geografiske informasjonssystemer (GIS). Eksisterende eller nydesignede hus, konstruksjoner, blokker etc. regnes som hjørner, og veier, bruksnett, kraftledninger etc. som forbinder dem regnes som kanter. Bruk av ulike beregninger utført på en slik graf gjør det for eksempel mulig å finne den korteste omkjøringsveien eller nærmeste dagligvarebutikk, eller å planlegge den optimale ruten.

Grafteori inneholder et stort antall uløste problemer og ennå ikke beviste hypoteser.

De viktigste bruksområdene for grafteori:

I kjemi (for å beskrive strukturer, baner for komplekse reaksjoner, kan faseregelen også tolkes som et grafteoretisk problem); Beregningskjemi er et relativt ungt område innen kjemi basert på anvendelse av grafteori. Grafteori er det matematiske grunnlaget for kjemoinformatikk. Grafteori gjør det mulig å nøyaktig bestemme antall teoretisk mulige isomerer i hydrokarboner og andre organiske forbindelser;

I informatikk og programmering (grafdiagram av algoritmen);

I kommunikasjons- og transportsystemer. Spesielt for ruting av data på Internett;

I økonomi;

Innen logistikk;

I kretsdesign (topologien til sammenkoblinger av elementer på et trykt kretskort eller mikrokrets er en graf eller hypergraf).

Det er en spesiell type graf, tre.Tre er en tilkoblet asyklisk graf. Sammenheng betyr tilstedeværelsen av stier mellom et hvilket som helst par av toppunkter, asyklisitet betyr fravær av sykluser og det faktum at det bare er én vei mellom par av toppunkter. På Fig 1.3 presentert binært tre.

Binært tre- en tredatastruktur der hver node ikke har mer enn to etterkommere(barn). Vanligvis kalles den første overordnet node, og barna blir kalt venstre Og rette arvinger.

Matriserepresentasjon av grafer. Hendelsesmatrise.

Utviklingen av algoritmiske tilnærminger til analyse av grafegenskaper krever visse metoder for å beskrive grafer som er mer egnet for praktiske beregninger, inkludert bruk av datamaskin. La oss se på de tre vanligste måtene å representere grafer på.

Anta at alle toppunkter og alle kanter på en urettet graf eller alle toppunkter og alle buer (inkludert løkker) til en rettet graf er nummerert fra én. En graf (urettet eller rettet) kan representeres som en matrise av typen , hvor er antall toppunkter og er antall kanter (eller buer). For en urettet graf er elementene i denne matrisen spesifisert som følger:

For en rettet graf er matriseelementene spesifisert som følger:

En matrise av typen definert på denne måten kalles hendelsesmatrise.

Et eksempel på innhenting av en hendelsesmatrise. For grafen vist nedenfor ( Ris. 2.1 aFigur 2.1 b).

Fig. 2.1 a Fig. 2,1 b

Adjacency matrise.

Til tross for at det å representere en graf i form av en forekomstmatrise spiller en svært viktig rolle i teoretisk forskning, er denne metoden i praksis svært ineffektiv. For det første har matrisen bare to ikke-null-elementer i hver kolonne, noe som gjør denne metoden for å representere en graf uøkonomisk når det er et stort antall hjørner. I tillegg er det svært arbeidskrevende å løse praktiske problemer ved å bruke en hendelsesmatrise.

La oss for eksempel estimere tidskostnadene for å løse et så enkelt problem i en rettet graf ved å bruke insidensmatrisen: for et gitt toppunkt, finn dets "miljø" - settet med etterfølgere og settet med forgjengere til toppunktet, dvs. settet med alle toppunkter som er direkte tilgjengelig fra, og settet med alle toppunkter som det er direkte tilgjengelig fra.

For å løse dette problemet på insidensmatrisen til en rettet graf, må du gå langs raden med tallet til et element som ikke er null vises (+1 eller –1). Hvis +1 oppdages, må du i den tilsvarende kolonnen finne linjen der tallet –1 er skrevet. Nummeret på linjen der dette nummeret vises, gir nummeret på toppunktet som er direkte tilgjengelig fra dette toppunktet. Hvis -1 oppdages, må du finne raden i kolonnen som inneholder 1 og få nummeret på toppunktet som dette toppunktet er direkte tilgjengelig fra. For å få hele "miljøet" må du gjøre det spesifiserte søket etter alle elementer som ikke er null kth linje. Den mest tidkrevende prosedyren er å finne et element som ikke er null i en kolonne. Antallet slike søkeprosedyrer er lik graden av toppunktet. I dette tilfellet vil vi si at kompleksiteten til algoritmen for å analysere miljøet til et toppunkt er (rekkefølge).

Det kan sees at søking etter "miljøet" til alle toppunktene vil ta tid i størrelsesorden produktet av antall toppunkter i en rettet graf med summen av gradene til alle toppunktene, som, som det kan vises, er proporsjonal med antall buer i den rettede grafen. Dermed er kompleksiteten til "miljø"-søkealgoritmen , dvs. søket tar tid på rekkefølgen av produktet av antall toppunkter og antall buer.

En mer effektiv matrisestruktur som representerer en graf er vertex adjacency matrise, eller Boolsk matrise kurve. Dette er en kvadratisk matrise av orden B n, hvis elementer er definert som følger:

for en urettet graf:

for en rettet graf:

For grafen vist nedenfor ( Ris. 2.2 a) insidensmatrisen vil være matrisen presentert på ( Figur 2.2 b).

Teksten til verket er lagt ut uten bilder og formler.
Full versjon arbeid er tilgjengelig i fanen "Arbeidsfiler" i PDF-format

INTRODUKSJON

"I matematikk er det ikke formlene som skal huskes, men prosessen med å tenke ..."

E. I. Ignatiev

Grafteori er for tiden en gren av matematikk i intensiv utvikling. Dette forklares med at mange objekter og situasjoner er beskrevet i form av grafmodeller, noe som er svært viktig for det sosiale livets normale funksjon. Det er denne faktoren som bestemmer relevansen av deres mer detaljerte studie. Derfor er emnet for dette arbeidet ganske relevant.

Mål forskningsarbeid: Finn ut funksjonene ved anvendelsen av grafteori i ulike kunnskapsfelt og i løsning av logiske problemer.

Målet identifiserte følgende oppgaver:

bli kjent med grafteoriens historie;

studere de grunnleggende konseptene for grafteori og de viktigste egenskapene til grafer;

vise praktisk anvendelse av grafteori i ulike kunnskapsfelt;

Vurder måter å løse problemer ved hjelp av grafer og lag dine egne problemer.

En gjenstand forskning: sfæren av menneskelig aktivitet for anvendelse av grafmetoden.

Punkt Forskning: seksjon for matematikk "Graph Theory".

Hypotese. Vi antar at læring av grafteori kan hjelpe elevene med å løse logiske problemer i matematikk, som vil forme deres fremtidige interesser.

Metoder forskningsarbeid:

Under vår forskning ble følgende metoder brukt:

1) Arbeide med ulike informasjonskilder.

2) Beskrivelse, innsamling, systematisering av materiale.

3) Observasjon, analyse og sammenligning.

4) Utarbeidelse av oppgaver.

Teoretisk og praktisk betydning Dette arbeidet er bestemt av at resultatene kan brukes innen informatikk, matematikk, geometri, tegning og klasseroms timer, så vel som for et bredt spekter av lesere som er interessert i dette emnet. Forskningsarbeidet har en klar praktisk orientering, siden forfatteren i verket presenterer tallrike eksempler på bruk av grafer i mange kunnskapsfelt, og har utarbeidet egne oppgaver. Dette materialet kan brukes i valgfrie matematikktimer.

KAPITTEL I. TEORETISK GJENNOMGANG AV MATERIALET OM FORSKNINGSEMNET

I matematikk kan en "graf" avbildes som et bilde, som representerer et antall punkter forbundet med linjer. "Count" kommer fra det latinske ordet "graphio" - jeg skriver, som en velkjent adelstittel.

I matematikk er definisjonen av en graf gitt som følger:

Begrepet "graf" i matematikk er definert som følger:

Kurve - dette er et begrenset sett med punkter - topper, som kan kobles sammen med linjer - ribbeina .

Eksempler på grafer inkluderer tegninger av polygoner, elektriske kretser, skjematiske representasjoner av flyselskaper, undergrunnsbaner, veier, etc. Et slektstre er også en graf, der hjørnene er medlemmer av klanen, og familiebånd fungerer som kantene på grafen.

Ris. 1 Eksempler på grafer

Antall kanter som tilhører ett toppunkt kalles graf toppunkt grad . Hvis graden av et toppunkt er et oddetall, kalles toppunktet - merkelig . Hvis graden av et toppunkt er et partall, kalles toppunktet til og med.

Ris. 2 toppunktet på grafen

Null graf er en graf som kun består av isolerte hjørner som ikke er forbundet med kanter.

Komplett graf er en graf der hvert par topper er forbundet med en kant. En N-gon, der alle diagonaler er tegnet, kan tjene som et eksempel på en komplett graf.

Velger du en bane i en graf hvor start- og sluttpunktene faller sammen, så kalles en slik bane grafsyklus . Hvis hvert toppunkt på grafen passeres maksimalt én gang, da syklus kalt enkel .

Hvis hvert annet hjørne i en graf er forbundet med en kant, så er dette tilkoblet kurve. Grafen kalles ikke relatert , hvis den inneholder minst ett par usammenhengende hjørner.

Hvis en graf er koblet sammen, men ikke inneholder sykluser, kalles en slik graf tre .

Grevens vei er en sekvens der hver to tilstøtende kanter som deler et felles toppunkt bare forekommer én gang.

Lengden på den korteste kjeden av hjørner en og b kalles avstand mellom toppene en og b.

Vertex EN kalt senter graf, hvis avstanden mellom toppunktene EN og enhver annen toppunkt er den minste mulige. Det er en slik avstand radius kurve.

Den maksimale mulige avstanden mellom to punkter i en graf kalles diameter kurve.

Graffarging og applikasjon.

Hvis du ser nøye på et geografisk kart, kan du se jernbaner eller motorveier, som er grafer. I tillegg er det en graf på kartet, som består av grenser mellom land (distrikter, regioner).

I 1852 fikk den engelske studenten Francis Guthrie oppgaven med å fargelegge et kart over Storbritannia, og fremheve hvert fylke i en egen farge. På grunn av det lille utvalget av maling, gjenbrukte Guthrie dem. Han valgte fargene slik at de fylkene som delte en felles del av grensen, nødvendigvis ble malt i forskjellige farger. Spørsmålet oppsto om hva som er minimumsmengden maling som trengs for å fargelegge ulike kart. Francis Guthrie foreslo, selv om han ikke kunne bevise, at fire farger ville være tilstrekkelig. Dette problemet ble heftig diskutert i studentkretser, men ble senere glemt.

"Fire-fargeproblemet" vakte økende interesse, men ble aldri løst, selv ikke av eminente matematikere. I 1890 Engelsk matematiker Percy Heawood beviste at fem farger er nok til å fargelegge ethvert kart. Det var først i 1968 at de klarte å bevise at 4 farger ville være nok til å fargelegge et kart som viser mindre enn førti land.

I 1976 ble dette problemet løst ved hjelp av en datamaskin av to amerikanske matematikere Kenneth Appel og Wolfgangt Haken. For å løse det ble alle kort delt inn i 2000 typer. Det ble laget et dataprogram som undersøkte alle typer for å identifisere kort som fire farger ikke ville være nok til å fargelegge. Datamaskinen kunne ikke studere bare tre typer kart, så matematikere studerte dem på egen hånd. Som et resultat ble det funnet at 4 farger ville være nok til å fargelegge alle 2000 typer kort. De annonserte en løsning på problemet med fire farger. Denne dagen satte postkontoret ved universitetet der Appel og Haken jobbet et stempel på alle frimerkene med ordene: «Fire farger er nok».

Du kan forestille deg problemet med fire farger litt annerledes.

For å gjøre dette, vurder et vilkårlig kart som presenterer det i form av en graf: hovedstedene i stater er toppunktene på grafen, og kantene på grafen forbinder de toppunktene (hovedstedene) hvis stater har en felles grense. For å få en slik graf er følgende problem formulert: det er nødvendig å farge grafen ved hjelp av fire farger slik at toppunktene som har en felles kant er farget med forskjellige farger.

Euler og Hamiltonske grafer

I 1859 ga den engelske matematikeren William Hamilton ut et puslespill - et tredodekaeder (dodecahedron), hvis tjue topper var merket med stendere. Hver topp hadde navnet på en av de største byene i verden - Kanton, Delhi, Brussel, etc. Oppgaven var å finne en lukket sti som går langs kantene på polyederet, og besøker hvert toppunkt bare én gang. For å markere stien ble det brukt en snor som ble hektet på spiker.

En Hamilton-syklus er en graf hvis bane er en enkel syklus som går gjennom alle toppunktene på grafen én gang.

Byen Kaliningrad (tidligere Koenigsberg) ligger ved elven Pregel. Elven vasket to øyer, som var forbundet med hverandre og til bredden med broer. De gamle bruene er der ikke lenger. Minnet om dem forblir bare på kartet over byen.

En dag spurte en innbygger i byen vennen sin om det var mulig å gå over alle broene, besøke hver enkelt én gang og gå tilbake til stedet der vandringen begynte. Dette problemet interesserte mange byfolk, men ingen kunne løse det. Dette problemet har vakt interesse hos forskere fra mange land. Løsningen på problemet ble skaffet av matematiker Leonhard Euler. I tillegg formulerte han en generell tilnærming til å løse slike problemer. For å gjøre dette gjorde han kartet til en graf. Toppene på denne grafen var landet, og kantene var broene som forbinder det.

Mens han løste Königsberg-broproblemet, klarte Euler å formulere egenskapene til grafer.

Det er mulig å tegne en graf ved å starte fra ett toppunkt og avslutte ved samme toppunkt med ett slag (uten å tegne langs samme linje to ganger og uten å løfte blyanten fra papiret) hvis alle toppunktene på grafen er jevne.

Hvis det er en graf med to odde hjørner, kan toppene også kobles sammen med ett slag. For å gjøre dette, må du starte fra den ene og avslutte på den andre, et hvilket som helst odde toppunkt.

Hvis det er en graf med mer enn to odde hjørner, kan ikke grafen tegnes med ett slag.

Hvis vi bruker disse egenskapene til problemet med broer, kan vi se at alle toppunktene i grafen som studeres er odde, noe som betyr at denne grafen ikke kan kobles sammen med ett slag, dvs. Det er umulig å krysse alle broene en gang og avslutte reisen på stedet der den begynte.

Hvis en graf har en syklus (ikke nødvendigvis enkel) som inneholder alle kantene på grafen én gang, kalles en slik syklus Euler syklus . Euler-kjede (bane, syklus, kontur) er en kjede (bane, syklus, kontur) som inneholder alle kantene (buene) på grafen én gang.

KAPITTEL II. BESKRIVELSE AV STUDIEN OG DENS RESULTATER

2.1. Stadier av studien

For å teste hypotesen inkluderte studien tre stadier (tabell 1):

Forskningsstadier

Tabell 1.

		Metoder som brukes
Teoretisk studie av problemet	Studer og analyser pedagogisk og vitenskapelig litteratur.	- selvstendig tenkning;  studie av informasjonskilder; - søke etter nødvendig litteratur.
Kasusstudie Problemer	Gjennomgå og analysere områder praktisk anvendelse grafer;	- observasjon; - analyse; - sammenligning; - undersøkelse.
Trinn 3. Praktisk bruk av resultatene	Oppsummer informasjonen som er studert;	- systematisering;  rapport (muntlig, skriftlig, med demonstrasjon av materialer)	september 2017

2.2. Områder for praktisk anvendelse av grafer

Grafer og informasjon

Informasjonsteori bruker i stor grad egenskapene til binære trær.

For eksempel, hvis du trenger å kode et visst antall meldinger i form av visse sekvenser av nuller og ener med forskjellige lengder. En kode regnes som best for en gitt sannsynlighet for kodeord hvis den gjennomsnittlige ordlengden er den minste sammenlignet med andre sannsynlighetsfordelinger. For å løse dette problemet foreslo Huffman en algoritme der koden er representert som en tregraf innenfor rammen av søketeori. For hvert toppunkt foreslås et spørsmål, svaret på dette kan være enten "ja" eller "nei" - som tilsvarer de to kantene som kommer ut av toppunktet. Byggingen av et slikt tre er fullført etter å ha etablert det som var nødvendig. Dette kan brukes til å intervjue flere personer, når svaret på forrige spørsmål er ukjent på forhånd, er intervjuplanen representert som et binært tre.

Grafer og kjemi

A. Cayley vurderte også problemet med mulige strukturer av mettede (eller mettede) hydrokarboner, hvis molekyler er gitt av formelen:

CnH 2n+2

Alle hydrokarbonatomer er 4-valente, alle hydrogenatomer er 1-valente. Strukturelle formler De enkleste hydrokarbonene er vist i figuren.

Hvert mettet hydrokarbonmolekyl kan representeres som et tre. Når alle hydrogenatomene er fjernet, danner hydrokarbonatomene som er igjen et tre med topper hvis grad ikke er høyere enn fire. Dette betyr at antall mulige ønskede strukturer (homologer av et gitt stoff) er lik antall trær hvis toppunktgrader ikke er mer enn 4. Dette problemet reduserer til problemet med å telle opp trær av en bestemt type. D. Polya vurderte dette problemet og dets generaliseringer.

Grafer og biologi

Prosessen med bakteriell reproduksjon er en av typene forgreningsprosesser som finnes i biologisk teori. La hver bakterie etter en viss tid enten dø eller dele seg i to. Derfor får vi for en bakterie et binært tre av reproduksjonen til dens avkom. Spørsmålet om problemet er følgende: hvor mange saker inneholder det? k etterkommere i nte generasjon en bakterie? Dette forholdet i biologi kalles Galton-Watson-prosessen, som angir det nødvendige antallet nødvendige tilfeller.

Grafer og fysikk

En vanskelig og kjedelig oppgave for enhver radioamatør er å lage trykte kretser (en plate av dielektrisk - isolerende materiale og etsede spor i form av metallstrimler). Skjæringspunktet mellom spor skjer bare på visse punkter (plassering av trioder, motstander, dioder, etc.) i henhold til visse regler. Som et resultat står forskeren overfor oppgaven med å tegne en flat graf med toppunkter inn

Så alt det ovennevnte bekrefter den praktiske verdien av grafer.

Internett-matematikk

Internett er et verdensomspennende system av sammenkoblede datanettverk for lagring og overføring av informasjon.

Internett kan representeres som en graf, der toppunktene på grafen er Internett-sider, og kantene er lenker (hyperkoblinger) som går fra ett nettsted til et annet.

Nettgrafen (Internett), som har milliarder av hjørner og kanter, er i konstant endring – nettsteder blir spontant lagt til og forsvunnet, lenker forsvinner og blir lagt til. Internett har imidlertid en matematisk struktur, adlyder grafteori og har flere "stabile" egenskaper.

Webgrafen er sparsom. Den inneholder bare noen få ganger flere kanter enn hjørner.

Til tross for sparsomheten er Internett veldig overfylt. Du kan gå fra et nettsted til et annet ved å bruke lenker på 5 - 6 klikk (den berømte teorien om "seks håndtrykk").

Som vi vet, er graden av en graf antall kanter som et toppunkt tilhører. Gradene av toppunktene til en webgraf er fordelt i henhold til en viss lov: andelen nettsteder (vertekser) med et stort antall lenker (kanter) er liten, og andelen nettsteder med et lite antall lenker er stor. Matematisk kan det skrives slik:

hvor er andelen toppunkter av en viss grad, er graden av toppunkt, er en konstant uavhengig av antall toppunkter i webgrafen, dvs. endres ikke under prosessen med å legge til eller fjerne nettsteder (vertekser).

Denne kraftloven er universell for komplekse nettverk – fra biologiske til interbanknettverk.

Internett som helhet er motstandsdyktig mot tilfeldige angrep på nettsteder.

Siden ødeleggelsen og opprettelsen av nettsteder skjer uavhengig og med samme sannsynlighet, opprettholder webgrafen, med en sannsynlighet nær 1, sin integritet og blir ikke ødelagt.

For å studere Internett er det nødvendig å bygge en tilfeldig grafmodell. Denne modellen skal ha egenskapene til det virkelige Internett og bør ikke være for kompleks.

Dette problemet er ennå ikke helt løst! Å løse dette problemet - å bygge en høykvalitetsmodell av Internett - vil tillate oss å utvikle nye verktøy for å forbedre informasjonssøk, identifisere spam og spre informasjon.

Konstruksjonen av biologiske og økonomiske modeller begynte mye tidligere enn oppgaven med å konstruere en matematisk modell av Internett oppsto. Fremskritt i utviklingen og studiet av Internett har imidlertid gjort det mulig å svare på mange spørsmål angående alle disse modellene.

Internettmatematikk er etterspurt av mange spesialister: biologer (forutsi veksten av bakteriepopulasjoner), finansfolk (risiko for kriser), etc. Studiet av slike systemer er en av de sentrale grenene innen anvendt matematikk og informatikk.

Murmansk ved hjelp av grafen.

Når en person ankommer en ny by, er som regel det første ønsket å besøke hovedattraksjonene. Men samtidig er tiden ofte begrenset, og ved forretningsreise svært liten. Derfor er det nødvendig å planlegge sightseeingen på forhånd. Og grafer vil være til stor hjelp når du bygger ruten din!

Som et eksempel, tenk på et typisk tilfelle av å ankomme Murmansk fra flyplassen for første gang. Vi planlegger å besøke følgende attraksjoner:

1. Marine-ortodokse kirken til Frelseren på vannet;

2. St. Nicholas-katedralen;

3. Oceanarium;

4. Monument til katten Semyon;

5. Atomisbryter Lenin;

6. Parklys i Murmansk;

7. Park Valley of Comfort;

8. Kolabroen;

9. Museum for historien til Murmansk Shipping Company;

10. Five Corners Square;

11. Sjøhandelshavn

La oss først finne disse stedene på kartet og få en visuell representasjon av plasseringen og avstanden mellom attraksjonene. Veinettet er ganske utbygd, og det vil ikke være vanskelig å reise med bil.

Attraksjoner på kartet (til venstre) og den resulterende grafen (til høyre) er vist i den tilsvarende figuren i VEDLEGG nr. 1. Dermed vil nykommeren først passere i nærheten av Kolabroen (og om ønskelig kan krysse den frem og tilbake); så vil han slappe av i Lights of Murmansk Park og Valley of Comfort og gå videre. Som et resultat vil den optimale ruten være:

Ved hjelp av grafen kan du også visualisere opplegget for å gjennomføre meningsmålinger. Eksempler er presentert i VEDLEGG nr. 2. Avhengig av svarene som gis, blir respondenten stilt ulike spørsmål. For eksempel, hvis respondenten i sosiologisk undersøkelse nr. 1 anser matematikk som den viktigste av vitenskapene, vil han bli spurt om han føler seg trygg på fysikktimene; hvis han mener noe annet, vil det andre spørsmålet gjelde etterspørselen humaniora. Toppene til en slik graf er spørsmål, og kantene er svaralternativer.

2.3. Anvendelse av grafteori til problemløsning

Grafteori brukes til å løse problemer fra mange fagområder: matematikk, biologi, informatikk. Vi studerte prinsippet om å løse problemer ved hjelp av grafteori og laget våre egne problemer om temaet forskning.

Oppgave nr. 1.

Fem klassekamerater håndhilste på en gjenforening på videregående. Hvor mange håndtrykk ble gjort?

Løsning: La oss angi klassekamerater ved toppunktene på grafen. La oss koble hvert toppunkt med linjer til fire andre toppunkter. Vi får 10 linjer, dette er håndtrykk.

Svar: 10 håndtrykk (hver linje betyr ett håndtrykk).

Oppgave nr. 2.

I min bestemors landsby, nær huset hennes, vokser 8 trær: poppel, eik, lønn, epletre, lerk, bjørk, rogn og furu. Rogne er høyere enn lerk, epletre er høyere enn lønn, eik er lavere enn bjørk, men høyere enn furu, furu er høyere enn rogne, bjørk er lavere enn poppel, og lerk er høyere enn epletre. I hvilken rekkefølge vil trærne bli ordnet i høyden fra høyeste til korteste?

Løsning:

Trær er toppunktene i grafen. La oss betegne dem med den første bokstaven i sirkelen. La oss tegne piler fra et lavt tre til et høyere. Det sies at rognen er høyere enn lerken, så setter vi pilen fra lerken til rognen, bjørka er lavere enn poppelen, så setter vi pilen fra poppelen til bjørka osv. Vi får en graf der vi kan se at det korteste treet er lønn, deretter eple, lerk, rogn, furu, eik, bjørk og poppel.

Svar: lønn, eple, lerk, rogn, furu, eik, bjørk og poppel.

Oppgave nr. 3.

Mamma har 2 konvolutter: vanlig og luft, og 3 frimerker: kvadratiske, rektangulære og trekantede. På hvor mange måter kan mor velge en konvolutt og et frimerke for å sende et brev til far?

Svar: 6 måter

Oppgave nr. 4.

Mellom bosetninger A, B, C, D, E veier bygges. Trenger å bestemme lengden korteste vei mellom punktene A og E. Du kan kun kjøre på veier hvis lengde er angitt i figuren.

Oppgave nr. 5.

Tre klassekamerater - Maxim, Kirill og Vova bestemte seg for å gå inn for sport og besto utvalget av sportsseksjoner. Det er kjent at 1 gutt søkte på basketballseksjonen, og tre ville spille hockey. Maxim var kun på audition for seksjon 1, Kirill ble valgt ut til alle tre seksjonene, og Vova ble valgt til seksjon 2. Hvem av guttene ble valgt ut til hvilken idrettsseksjon?

Løsning: For å løse problemet vil vi bruke grafer

Basketball Maxim

Fotball Kirill

Hockey Vova

Siden til basketball bare én pil går, så ble Kirill valgt til seksjonen basketball. Da vil ikke Kirill spille hockey, som betyr i hockey seksjonen ble valgt av Maxim, som bare var på audition for denne seksjonen, så blir Vova fotballspiller.

Oppgave nr. 6.

På grunn av sykdom hos noen lærere, må rektor ved skolen utarbeide et fragment av skoleplanen i minst én dag, og ta hensyn til følgende omstendigheter:

1. Livssikkerhetslæreren samtykker i å gi kun den siste leksjonen;

2. Geografilæreren kan gi enten andre eller tredje leksjon;

3. Matematikeren er klar til å gi enten den første eller bare den andre leksjonen;

4. En fysikklærer kan gi enten den første, andre eller tredje leksjonen, men bare i én klasse.

Hva slags timeplan kan rektor på en skole lage slik at den tilfredsstiller alle lærere?

Løsning: Dette problemet kan løses ved å gå gjennom alle mulige alternativer, men det er lettere hvis du tegner en graf.

1. 1) fysikk 2. 1) matematikk 3. 1) matematikk

2) matematikk 2) fysikk 2) geografi

3) geografi 3) geografi 3) fysikk

4) OBZH 4) OBZH 4) OBZH

Konklusjon

I dette forskningsarbeidet ble grafteori studert i detalj, hypotesen ble bevist at studiet av grafer kan hjelpe til med å løse logiske problemer, i tillegg ble grafteori i forskjellige vitenskapsfelt vurdert og 7 problemer ble satt sammen.

Bruken av grafer når elevene lærer hvordan de skal finne løsninger på problemer, lar elevene forbedre sine grafiske ferdigheter og kommunisere resonnement på et spesielt språk med et begrenset sett med punkter, hvorav noen er forbundet med linjer. Alt dette bidrar til arbeidet med å lære elevene å tenke.

Effektivitet pedagogiske aktiviteter i utviklingen av tenkning avhenger i stor grad av graden av kreativ aktivitet til elevene når de løser matematiske problemer. Derfor er det behov for matematiske oppgaver og øvelser som vil aktivere den mentale aktiviteten til skolebarn.

Anvendelse av oppgaver og bruk av elementer fra grafteori i valgfag på skolen forfølger nettopp målet om å aktivere den mentale aktiviteten til elevene. Vi tror at praktisk materiale om forskningen vår kan være nyttig i valgfrie matematikktimer.

Dermed er målet med forskningsarbeidet nådd, problemene er løst. I fremtiden planlegger vi å fortsette å studere grafteori og utvikle våre egne ruter, for eksempel ved å bruke en graf til å lage en ekskursjonsrute for en skolebuss i ZATO Aleksandrovsk til museer og minneverdige steder Murmansk.

LISTE OVER BRUKTE REFERANSER

Berezina L. Yu. "Graphs and their application" - M.: "Enlightenment", 1979

Gardner M. "Mathematical leisure", M. "Mir", 1972

Gardner M." Matematikkoppgaver og underholdning", M. "Mir", 1971

Gorbatsjov A. "Samling av Olympiade-problemer" - M. MTsNMO, 2005

Zykov A. A. Grunnleggende om grafteori. - M.: "Universitetsbok", 2004. - S. 664

Kasatkin V. N. "Uvanlige problemer med matematikk", Kiev, "Radianska School", 1987

Matematisk komponent / Redaktører og kompilatorer N.N. Andreev, S.P. Konovalov, N.M. Panyushkin. - M.: Stiftelsen "Mathematical Etudes" 2015 - 151 s.

Melnikov O. I. "Underholdende problemer i grafteori", Mn. "TetraSystems", 2001

Melnikov O.I. Dunno in the land of counts: En manual for studenter. Ed. 3., stereotypisk. M.: KomKniga, 2007. - 160 s.

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. "Gamle underholdende problemer", M. "Science", 1988

Ore O. "Graphs and their applications", M. "Mir", 1965

Harari F. Graph Theory / Oversettelse fra engelsk. og forord V. P. Kozyreva. Ed. G.P. Gavrilova. Ed. 2. - M.: Redaksjonell URSS, 2003. - 296 s.

VEDLEGG nr. 1

Tegne den optimale ruten for å besøke hovedattraksjonene

Murmansk ved hjelp av grafen.

Den optimale ruten vil være:

8. Kolabroen6. Parklys i Murmansk7. Park Valley of Comfort2. St. Nicholas-katedralen10. Five Corners Square5. Atomisbryter Lenin9. Museum for historien til Murmansk Shipping Company11. Sjøhandelshavn1. Marine-ortodokse Frelserens kirke på vannet4. Monument til katten Semyon3. Oceanarium.

GUIDE TIL MURMANSK ATTRAKSJONER

VEDLEGG nr. 2

Sosiologiske undersøkelser nr. 1, 2

Hva er grafmetoden?

Ordet "graf" i matematikk betyr et bilde med flere punkter tegnet, hvorav noen er forbundet med linjer. For det første er det verdt å si at tellingene som vil bli diskutert ikke har noe med svunne tiders aristokrater å gjøre. Våre "grafer" er forankret i det greske ordet "grapho", som betyr "jeg skriver." Den samme roten er i ordene "graf", "biografi".

I matematikk grafdefinisjon er gitt som følger: en graf er et begrenset sett med punkter, hvorav noen er forbundet med linjer. Punktene kalles toppunkter på grafen, og forbindelseslinjene kalles kanter.

Et grafdiagram bestående av "isolerte" hjørner kalles null graf. (Fig.2)

Grafer der alle mulige kanter ikke er konstruert kalles ufullstendige grafer. (Fig.3)

Grafer der alle mulige kanter er konstruert kalles komplette grafer. (Fig.4)

En graf der hvert toppunkt er koblet til en kant på hvert annet toppunkt kalles fullstendig.

Merk at hvis en komplett graf har n toppunkter, vil antallet kanter være lik

n(n-1)/2

Faktisk er antallet kanter i en komplett graf med n toppunkter definert som antall uordnede par som består av alle n kantpunkter på grafen, dvs. som antall kombinasjoner av n elementer av 2:

En graf som ikke er fullstendig kan fullføres for å være komplett med de samme toppunktene ved å legge til de manglende kantene. For eksempel viser figur 3 en ufullstendig graf med fem hjørner. I figur 4 er kantene som forvandler grafen til en komplett graf avbildet i en annen farge; samlingen av toppunktene til grafen med disse kantene kalles komplementet til grafen.

Grader av toppunkter og telling av antall kanter.

Antall kanter som forlater et toppunkt av grafen kalles toppunkt grad. Et toppunkt på en graf som har en oddetall kalles merkelig, og til og med grad – til og med.

Hvis gradene til alle toppunktene i en graf er like, kalles grafen homogen. Dermed er enhver fullstendig graf homogen.

Fig.5

Figur 5 viser en graf med fem toppunkter. Graden av toppunkt A vil bli betegnet med St.A.

På figuren: St.A = 1, St.B = 2, St.B = 3, St.G = 2, St.D = 0.

La oss formulere noen regelmessigheter som er iboende i visse grafer.

Mønster 1.

Gradene til toppunktene til en komplett graf er de samme, og hver av dem er 1 mindre enn antall toppunkter i denne grafen.

Bevis:

Dette mønsteret er åpenbart etter å ha vurdert en fullstendig graf. Hver toppunkt er forbundet med en kant til hvert toppunkt unntatt seg selv, dvs. fra hvert toppunkt i en graf som har n toppunkter, kommer n-1 kanter ut, som er det som måtte bevises.

Mønster 2.

Summen av gradene av toppunktene til en graf er et partall lik to ganger antall kanter på grafen.

Dette mønsteret gjelder ikke bare for en fullstendig graf, men også for enhver graf. Bevis:

Faktisk forbinder hver kant av grafen to toppunkter. Dette betyr at hvis vi legger til antall grader av alle toppunktene i grafen, vil vi få dobbelt så mange kanter 2R (R er antall kanter på grafen), siden hver kant ble telt to ganger, som er det som trengs for å bli bevist

Antall odde hjørner i en graf er partall. Bevis:

Betrakt en vilkårlig graf G. La antall toppunkter i denne grafen hvis grad er 1 være lik K1; antall toppunkter hvis grad er 2 er lik K2; ...; antall toppunkter hvis grad er n er lik Kn. Da kan summen av gradene til toppunktene i denne grafen skrives som
K1 + 2K2 + ZK3 + ...+ nKn.
På den annen side: hvis antall kanter på grafen er R, så er det fra lov 2 kjent at summen av gradene til alle toppunktene i grafen er lik 2R. Da kan vi skrive likheten
K1 + 2K2 + ZK3 + ... + nKn = 2R. (1)
La oss velge på venstre side av likheten en sum som er lik antall odde hjørner av grafen (K1 + K3 + ...):
K1 + 2K2 + ZK3 + 4K4 + 5K5 + ... + nK = 2R,
(K1 + K3 + K5 +...) + (2K2 + 2X3 +4K4 + 4K5 + ...)=2R
Den andre parentesen er et partall som summen av partall. Den resulterende summen (2R) er et partall. Derfor er (K1 + K3 + K5 +...) et partall.

La oss nå vurdere problemer løst ved hjelp av grafer:

Oppgave. Klassemesterskap . Det er 6 deltakere i klassemesterskapet i bordtennis: Andrey, Boris, Victor, Galina, Dmitry og Elena. Mesterskapet avholdes på round-robin-basis - hver deltaker spiller hver av de andre en gang. Til dags dato har noen spill allerede blitt spilt: Andrey spilte med Boris, Galina og Elena; Boris, som allerede nevnt, er sammen med Andrei og også med Galina; Victor - med Galina, Dmitry og Elena; Galina med Andrey og Boris; Dmitry - med Victor og Elena - med Andrey og Victor. Hvor mange kamper har blitt spilt så langt og hvor mange er igjen?

Diskusjon. La oss skildre disse oppgavene i form av et diagram. Vi vil skildre deltakerne som prikker: Andrey - punkt A, Boris - punkt B, etc. Hvis to deltakere allerede har spilt med hverandre, vil vi koble punktene som representerer dem med segmenter. Resultatet er diagrammet vist i figur 1.

Punktene A, B, C, D, D, E er toppunktene på grafen, og segmentene som forbinder dem er kantene på grafen.

Merk at skjæringspunktene til kantene på grafen ikke er toppene.

Antall spill spilt så langt er lik antall kanter, dvs. 7.

For å unngå forvirring er toppunktene i en graf ofte ikke avbildet som prikker, men som små sirkler.

For å finne antall spill som må spilles skal vi bygge en annen graf med de samme toppunktene, men med kanter vil vi koble sammen de deltakerne som ennå ikke har spilt med hverandre (fig 2) Denne grafen viste seg å ha 8 kanter, som betyr at det er 8 kamper igjen å spille: Andrey - med Victor og Dmitry; Boris - Med Victor, Dmitry og Elena, etc.

La oss prøve å bygge en graf for situasjonen beskrevet i følgende oppgave:

Oppgave . Hvem spiller Lyapkin - Tyapkin? Skolens dramaklubb bestemte seg for å sette opp Gogols The Inspector General. Og så brøt det ut en heftig krangel. Det hele startet med Lyapkin - Tyapkin.

Lyapkin - jeg vil være Tyapkin! – uttalte Gena bestemt.

Nei, jeg blir Lyapkin - Tyapkin, innvendte Dima.- Fra tidlig barndom drømte jeg om å bringe dette bildet til live på scenen.

Vel, ok, jeg gir opp denne rollen hvis de lar meg spille Khlestakov,» viste Gena raushet.

"...Og for meg - Osipa," ga Dima ikke etter for ham i generøsitet.

"Jeg vil bli jordbær eller ordfører," sa Vova.

Nei, jeg skal være ordfører,” ropte Alik og Borya unisont. - Eller Khlestakov, -

Vil det være mulig å fordele rollene slik at utøverne blir fornøyde?

Diskusjon. La oss skildre de unge skuespillerne med sirkler på øverste rad: A - Alik, B - Boris, C - Vova, G - Gena, D - Dima, og rollene de skal spille - med sirkler i andre rad (1 - Lyapkin - Tyapkin, 2 - Khlestakov, 3 - Osip, 4 - Strawberry, 5 - Ordfører). Deretter vil vi trekke ut segmenter fra hver deltaker, d.v.s. ribbe, til rollene han gjerne vil spille. Vi vil få en graf med ti topper og ti kanter (fig. 3)

For å løse problemet må du velge fem kanter av ti som ikke har felles toppunkter. Det er enkelt å gjøre. Det er nok å merke seg at en kant fører til toppunktene 3 og 4, fra henholdsvis toppunktene D og B. Dette betyr at Osip (topp 3) bør spilles av Dima (hvem ellers?), og Zemlyanichka av Vova. Vertex 1 - Lyapkin - Tyapkin - er forbundet med kanter til G og D. Edge 1 - D gir opp, siden Dima allerede er opptatt, 1 - G gjenstår, Lyapkina - Tyapkina skal spilles av Gena. Det gjenstår å koble toppunktene A og B med toppunktene 2 og 5, tilsvarende rollene til Khlestakov og Gorodnichy. Dette kan gjøres på to måter: enten velg kant A -5 og B - 2, eller kant A -2 og B -5. I det første tilfellet vil Alik spille ordføreren, og Borya vil spille Khlestakov, i det andre tilfellet, omvendt. Som grafen viser, har problemet ingen andre løsninger.

Den samme grafen vil bli oppnådd når du løser følgende oppgave:

Oppgave. Gretten naboer. Innbyggerne i fem hus kranglet med hverandre og, for ikke å møtes ved brønnene, bestemte de seg for å dele dem (brønnene) slik at eieren av hvert hus skulle gå til "sin" brønn langs "hans" vei. Vil de klare dette?

Spørsmålet oppstår:var det virkelig behov for grafer i problemene som ble diskutert? Er det ikke mulig å komme frem til en løsning med rent logiske midler? Ja det kan du. Men grafene gjorde forholdene klarere, forenklet løsningen og avslørte likheten mellom problemene, og gjorde to problemer til ett, og dette er ikke så lite. Tenk deg nå problemer hvis grafer har 100 eller flere toppunkter. Men det er nettopp slike problemer moderne ingeniører og økonomer må løse. Du klarer deg ikke uten grafer her.

III. Euler-grafer.

Grafteori er en relativt ung vitenskap: på Newtons tid eksisterte ikke en slik vitenskap ennå, selv om "slektstre", som er varianter av grafer, var i bruk. Det første arbeidet med grafteori tilhører Leonhard Euler, og det dukket opp i 1736 i publikasjonene til St. Petersburgs vitenskapsakademi. Dette arbeidet startet med vurdering av følgende problem:

EN) Problem om Königsberg-broene. Byen Koenigsberg (nå Kaliningrad) ligger på bredden og to øyer av elven Pregel (Pregoli).De ulike delene av byen var forbundet med syv broer, som vist på bildet. På søndager går innbyggerne turer rundt i byen. Er det mulig å velge en rute slik at man krysser hver bru én gang og bare én gang og så tilbake til utgangspunktet?
Før vi vurderer løsningen på dette problemet, introduserer vi konseptet " Euler-grafer.

La oss prøve å sirkle rundt grafen vist i fig. 4 med ett slag, det vil si uten å løfte blyanten fra papirarket og uten å passere langs samme del av linjen mer enn en gang.

Denne figuren, så enkel i utseende, viser seg å ha en interessant funksjon. Hvis vi begynner å bevege oss fra toppunkt B, så vil vi definitivt lykkes. Hva vil skje hvis vi begynner å bevege oss fra toppunkt A? Det er lett å se at i dette tilfellet vil vi ikke kunne spore linjen: vi vil alltid ha ugjennomtrengte kanter, som ikke lenger er mulig å nå.

I fig. Figur 5 viser en graf som du sannsynligvis vet hvordan du tegner med ett slag. Dette er en stjerne. Det viser seg at selv om det ser mye mer komplekst ut enn forrige graf, kan du spore det ved å starte fra et hvilket som helst toppunkt.

Grafene tegnet i fig. 6 kan også tegnes med ett pennestrøk.

Prøv nå å tegne med ett slag graf vist i fig. 7

Du klarte ikke å gjøre dette! Hvorfor? Finner du ikke toppunktet du leter etter? Nei! Det er ikke poenget. Denne grafen kan vanligvis ikke tegnes med ett pennestrøk.

La oss gjennomføre resonnementer som vil overbevise oss om dette. Tenk på node A. Tre toppunkter kommer ut av den. La oss begynne å tegne grafen fra dette toppunktet. For å gå langs hver av disse kantene, må vi gå ut av toppunktet A langs en av dem, på et tidspunkt må vi gå tilbake til den langs den andre og gå ut langs den tredje. Men vi kan ikke komme inn igjen! Dette betyr at hvis vi begynner å tegne fra toppunkt A, vil vi ikke kunne fullføre der.

La oss nå anta at toppunktet A ikke er begynnelsen. Så, i ferd med å tegne, må vi gå inn langs en av kantene, gå ut langs den andre og gå tilbake igjen langs den tredje. Og siden vi ikke kan komme ut av det, så må topp A i dette tilfellet være slutten.

Så, toppunkt A må enten være begynnelsen eller sluttnoden på tegningen.

Men det samme kan sies om de tre andre toppunktene i grafen vår. Men startpunktet for tegningen kan bare være ett toppunkt, og det endelige toppunktet kan også være bare ett toppunkt! Dette betyr at det er umulig å tegne denne grafen med ett slag.

En graf som kan tegnes uten å løfte blyanten fra papiret kalles Eulerian (Fig. 6).

Disse grafene er oppkalt etter vitenskapsmannen Leonhard Euler.

Mønster 1. (følger av teoremet vi vurderte).

Det er umulig å tegne en graf med et oddetall odde hjørner.
Mønster 2.

Hvis alle toppunktene på grafen er jevne, kan du tegne denne grafen uten å løfte blyanten fra papiret ("med ett slag"), og bevege deg langs hver kant bare én gang. Bevegelsen kan starte fra hvilket som helst toppunkt og ende ved samme toppunkt.
Mønster 3.

En graf med bare to odde hjørner kan tegnes uten å løfte blyanten fra papiret, og bevegelsen må begynne ved en av disse odde hjørnene og slutte ved den andre av dem.
Mønster 4.

En graf med mer enn to odde hjørner kan ikke tegnes med «ett slag».
En figur (graf) som kan tegnes uten å løfte blyanten fra papiret kalles unikursal.

Grafen kalles sammenhengende, hvis noen av to av hjørnene kan forbindes med en bane, det vil si en sekvens av kanter, som hver begynner på slutten av den forrige.

Grafen kalles usammenhengende, dersom denne betingelsen ikke er oppfylt.

Fig.7 Fig.8

Figur 7 viser åpenbart en frakoblet graf. Hvis du for eksempel i figuren tegner en kant mellom hjørnene D og E, vil grafen henge sammen. (fig.8)

I grafteori kalles en slik kant (etter fjerning som grafen fra en tilkoblet en blir til en frakoblet) bro.

Eksempler på broer i figur 7 kan være kantene DE, A3, VZH, etc., som hver vil forbinde toppunktene til "isolerte" deler av grafen (fig. 8).

En frakoblet graf består av flere "stykker". Disse "bitene" kalles tilkoblingskomponenter kurve. Hver tilkoblet komponent er selvfølgelig en tilkoblet graf. Merk at en tilkoblet graf har én tilkoblet komponent.
TEOREM.

En graf er eulerisk hvis og bare hvis den er koblet sammen og har høyst to odde hjørner.

Bevis:

Ved å tegne grafen for hvert toppunkt, med unntak av de første og siste, vil vi legge inn samme antall ganger som vi går ut av det. Derfor må gradene til alle toppunktene være partall, bortsett fra to, noe som betyr at en Eulersk graf har maksimalt to oddepunkt.

La oss nå gå tilbake til problemet med Königsberg-broene.

Diskusjon av problemet . La oss betegne de forskjellige delene av byen med bokstavene A, B, C, D, og broene med bokstavene a, b, c, d, e, f, g - broer som forbinder de tilsvarende delene av byen. I denne oppgaven er det bare kryssinger over broer: krysser vi en hvilken som helst bro, ender vi alltid fra en del av byen til en annen. Og omvendt, krysser vi fra en del av byen til en annen, vil vi helt sikkert krysse en bro. La oss derfor skildre byplanen i form av en graf, hvis hjørner A, B, C, D (fig. 8) viser enkelte deler av byen, og kantene a, b, c, d, e , f, g er broer som forbinder de tilsvarende delene av byen. Det er ofte mer praktisk å skildre kanter ikke som rette segmenter, men som krumlinjede - "buer".

Hvis det var en rute som tilfredsstilte betingelsene for problemet, ville det være en lukket kontinuerlig kryssing av denne grafen, som passerte en gang langs hver kant. Denne grafen skal med andre ord tegnes med ett slag. Men dette er umulig - uansett hvilket toppunkt vi velger som det første, må vi gå gjennom de gjenværende toppunktene, og samtidig hver "innkommende" kant (broen langs hvilken vi kom inn i denne delen av byen) vil tilsvare en "utgående" kant, broen som vi og deretter bruker den til å forlate denne delen av byen): antall kanter som kommer inn i hvert toppunkt vil være lik antall kanter som forlater den, dvs. totalt antall kanter som konvergerer ved hvert toppunkt må være jevne. Grafen vår tilfredsstiller ikke denne betingelsen, og derfor eksisterer ikke den nødvendige ruten.