Kommunal videregående opplæring statsfinansiert organisasjon -

Ungdomsskole nr. 51

Orenburg.

Prosjekt på:

matematikklærer

Egorcheva Victoria Andreevna

2017

Hypotese : Hvis grafteori bringes nærmere praksis, kan de mest fordelaktige resultatene oppnås.

Mål: Bli kjent med konseptet med grafer og lær hvordan du kan bruke dem til å løse ulike problemer.

Oppgaver:

1) Utvide kunnskap om metoder for å konstruere grafer.

2) Identifiser typer problemer hvis løsning krever bruk av grafteori.

3) Utforsk bruken av grafer i matematikk.

"Euler beregnet, uten noen synlig innsats, hvordan en person puster eller hvordan en ørn svever over jorden."

Dominic Arago.

JEG. Introduksjon. s.

II . Hoveddel.

1. Konseptet med en graf. Problem om Königsberg-broene. s.

2. Egenskaper til grafer. s.

3. Problemer med grafteori. s.

Sh. Konklusjon.

Betydningen av grafer. s.

IV. Bibliografi. s.

Jeg . INTRODUKSJON

Grafteori er en relativt ung vitenskap. "Graphs" har roten til det greske ordet "grapho", som betyr "jeg skriver." Den samme roten er i ordene "graf", "biografi".

I arbeidet mitt ser jeg på hvordan grafteori brukes på ulike områder av menneskers liv. Hver mattelærer og nesten hver elev vet hvor vanskelig det er å løse geometriske problemer, så vel som algebraordoppgaver. Etter å ha utforsket muligheten for å bruke grafteori i et skolematematikkkurs, kom jeg til at denne teorien i stor grad forenkler forståelse og løsning av problemer.

II . HOVEDDEL.

1. Konseptet med en graf.

Det første arbeidet med grafteori tilhører Leonhard Euler. Den dukket opp i 1736 i publikasjoner fra St. Petersburgs vitenskapsakademi og begynte med en vurdering av problemet med Königsberg-broene.

Du vet sikkert at det er en slik by som Kaliningrad; den pleide å hete Koenigsberg. Pregolya-elven renner gjennom byen. Den er delt i to grener og går rundt øya. På 1600-tallet var det syv broer i byen, ordnet som vist på bildet.

De forteller at en dag en innbygger i byen spurte vennen sin om han kunne gå over alle broene for å besøke hver av dem bare én gang og gå tilbake til stedet der vandringen begynte. Mange byfolk ble interessert i dette problemet, men ingen kunne komme med en løsning. Dette problemet har tiltrukket seg oppmerksomheten til forskere fra mange land. Den kjente matematikeren Leonhard Euler klarte å løse problemet. Leonhard Euler, opprinnelig fra Basel, ble født 15. april 1707. Eulers vitenskapelige prestasjoner er enorme. Han påvirket utviklingen av nesten alle grener av matematikk og mekanikk både i feltet grunnundersøkelser, og i søknadene deres. Leonhard Euler løste ikke bare dette spesifikke problemet, men kom også opp med en generell metode for å løse disse problemene. Euler gjorde følgende: han "komprimerte" landet til punkter, og "strakte" broene til linjer. Resultatet er figuren vist på figuren.

En slik figur, som består av punkter og linjer som forbinder disse punktene, kallestelle. Punktene A, B, C, D kalles toppunktene til grafen, og linjene som forbinder toppunktene kalles grafens kanter. I en tegning av hjørner B, C, D 3 ribber kommer ut, og fra toppen EN - 5 ribber. Topppunkt hvorfra et oddetall kanter kommer ut kallesmerkelige hjørner, og hjørner hvorfra et jevnt antall kanter kommer ut ertil og med.

2. Egenskaper til grafen.

Mens han løste problemet med Königsberg-broene, etablerte Euler spesielt egenskapene til grafen:

1. Hvis alle toppunktene i grafen er jevne, kan du tegne en graf med ett slag (det vil si uten å løfte blyanten fra papiret og uten å tegne to ganger langs samme linje). I dette tilfellet kan bevegelsen starte fra hvilket som helst toppunkt og ende ved samme toppunkt.

2. En graf med to odde hjørner kan også tegnes med ett slag. Bevegelsen må begynne fra et hvilket som helst oddetall og ende ved et annet oddetall.

3. En graf med mer enn to odde hjørner kan ikke tegnes med ett slag.

4.Antallet oddepunkt i en graf er alltid partall.

5. Hvis en graf har odde hjørner, vil det minste antall streker som kan brukes til å tegne grafen være lik halvparten av antallet oddepunkt i denne grafen.

For eksempel, hvis en figur har fire oddetall, kan den tegnes med minst to slag.

I problemet med de syv broene i Königsberg er alle fire toppunktene i den tilsvarende grafen odde, dvs. Du kan ikke krysse alle broene én gang og avslutte reisen der den startet.

3. Løse problemer ved hjelp av grafer.

1. Oppgaver om å tegne figurer med ett slag.

Forsøk på å tegne hver av de følgende formene med ett pennestrøk vil resultere i forskjellige resultater.

Hvis det ikke er noen odde punkter i figuren, kan den alltid tegnes med ett pennestrøk, uansett hvor du begynner å tegne. Dette er figur 1 og 5.

Hvis en figur bare har ett par oddepunkter, kan en slik figur tegnes med ett slag, og begynner å tegne på et av oddepunktene (det spiller ingen rolle hvilket). Det er lett å forstå at tegningen skal ende på det andre odde punktet. Dette er figurene 2, 3, 6. I figur 6, for eksempel, må tegningen begynne enten fra punkt A eller fra punkt B.

Hvis en figur har mer enn ett par oddepunkter, kan den ikke tegnes med ett slag i det hele tatt. Dette er figurene 4 og 7, som inneholder to par oddetallspunkter. Det som er sagt er nok til nøyaktig å gjenkjenne hvilke figurer som ikke kan tegnes med ett slag og hvilke som kan tegnes, samt fra hvilket punkt tegningen skal begynne.

Jeg foreslår å tegne følgende figurer i ett slag.

2. Løse logiske problemer.

OPPGAVE nr. 1.

Det er 6 deltakere i klassemesterskapet i bordtennis: Andrey, Boris, Victor, Galina, Dmitry og Elena. Mesterskapet holdes i et round robin-system - hver deltaker spiller hver av de andre en gang. Til dags dato har noen spill allerede blitt spilt: Andrey spilte med Boris, Galina, Elena; Boris - med Andrey, Galina; Victor - med Galina, Dmitry, Elena; Galina - med Andrey, Victor og Boris. Hvor mange kamper har blitt spilt så langt og hvor mange er igjen?

LØSNING:

La oss bygge en graf som vist i figuren.

7 kamper spilt.

I denne figuren har grafen 8 kanter, så det er 8 spill igjen å spille.

OPPGAVE #2

På gårdsplassen, som er omgitt av et høyt gjerde, er det tre hus: rødt, gult og blått. Gjerdet har tre porter: rød, gul og blå. Fra det røde huset tegner du en sti til den røde porten, fra det gule huset til den gule porten, fra det blå huset til det blå slik at disse stiene ikke krysser hverandre.

LØSNING:

Løsningen på problemet er vist i figuren.

3. Løse ordproblemer.

For å løse problemer ved hjelp av grafmetoden, må du kjenne til følgende algoritme:

1.Hvilken prosess snakker vi om i problemstillingen?2.Hvilke mengder kjennetegner denne prosessen?3.Hva er forholdet mellom disse mengdene?4.Hvor mange ulike prosesser er beskrevet i oppgaven?5.Er det en sammenheng mellom elementene?

Ved å svare på disse spørsmålene analyserer vi tilstanden til problemet og skriver det ned skjematisk.

For eksempel . Bussen kjørte i 2 timer med en hastighet på 45 km/t og i 3 timer med en hastighet på 60 km/t. Hvor langt kjørte bussen i løpet av disse 5 timene?

S
¹=90 km V ¹=45 km/t t ¹=2t

S=VT

S ²=180 km V ²=60 km/t t ²=3 t

S ¹ + S ² = 90 + 180

Løsning:

1)45 x 2 = 90 (km) - bussen kjørte på 2 timer.

2)60 x 3 = 180 (km) - bussen kjørte på 3 timer.

3)90 + 180 = 270 (km) - bussen reiste på 5 timer.

Svar: 270 km.

III . KONKLUSJON.

Som et resultat av arbeidet med prosjektet lærte jeg at Leonhard Euler var grunnleggeren av grafteori og løste problemer ved hjelp av grafteori. Jeg konkluderte selv med at grafteori brukes i ulike områder av moderne matematikk og dens mange anvendelser. Det er ingen tvil om nytten av å introdusere oss elever for grafteoriens grunnleggende begreper. Å løse mange matematiske problemer blir lettere hvis du kan bruke grafer. Datapresentasjon V formen til en graf gir dem klarhet. Mange bevis blir også forenklet og blir mer overbevisende hvis du bruker grafer. Dette gjelder spesielt for slike områder av matematikken som matematisk logikk og kombinatorikk.

Dermed har studiet av dette emnet stor generell pedagogisk, generell kulturell og generell matematisk betydning. I Hverdagen Grafiske illustrasjoner, geometriske representasjoner og andre teknikker og metoder for visualisering brukes i økende grad. For dette formålet er det nyttig å introdusere studiet av elementer av grafteori i grunnskoler og videregående skoler, i det minste i fritidsaktiviteter, siden dette emnet ikke er inkludert i matematikkplanen.

V . BIBLIOGRAFI:

2008

Anmeldelse.

Et prosjekt med temaet "Graffer rundt oss" ble fullført av Nikita Zaytsev, en elev i klasse 7 "A" ved kommunal utdanningsinstitusjon nr. 3, Krasny Kut.

Et særtrekk ved Nikita Zaitsevs arbeid er dets relevans, praktiske orientering, dybden av dekningen av emnet og muligheten for å bruke det i fremtiden.

Arbeidet er kreativt, i formen informasjonsprosjekt. Studenten valgte dette emnet for å vise forholdet mellom grafteori og praksis ved å bruke eksempelet på en skolebussrute, for å vise at grafteori brukes i ulike områder av moderne matematikk og dens mange anvendelser, spesielt innen økonomi, matematisk logikk og kombinatorikk . Han viste at det å løse problemer er mye forenklet hvis det er mulig å bruke grafer; å presentere data i form av en graf gir dem klarhet; mange bevis er også forenklet og blir overbevisende.

Arbeidet tar for seg problemstillinger som:

1. Konseptet med en graf. Problem om Königsberg-broene.

2. Egenskaper til grafer.

3. Problemer med grafteori.

4. Betydningen av grafer.

5. Rutealternativ for skolebuss.

Når han utførte sitt arbeid, brukte N. Zaitsev:

1. Alkhova Z.N., Makeeva A.V. " Fritidsaktiviteter matematikk".

2. Magasin "Matematikk på skolen". Vedlegg «Første september» nr. 13

2008

3. Ya.I.Perelman "Underholdende oppgaver og eksperimenter." - Moskva: Education, 2000.

Arbeidet ble utført kompetent, materialet oppfyller kravene til dette emnet, de tilsvarende tegningene er vedlagt.

Kuchin Anatoly Nikolaevich

Prosjektleder:

Kuklina Tatyana Ivanovna

Institusjon:

MBOU "Grunnleggende ungdomsskole" Troitsko-Pechorsk Rep. Komi

I hans forskningsarbeid i matematikk "In the world of graphs" Jeg vil prøve å finne ut av funksjonene ved å bruke grafteori i problemløsning og i praktiske aktiviteter. Resultatet av mitt matematikkforskningsarbeid på grafer vil være mitt slektstre.

I mitt forskningsarbeid i matematikk planlegger jeg å sette meg inn i grafteoriens historie, studere grunnleggende begreper og graftyper, og vurdere metoder for å løse problemer ved hjelp av grafer.

Også i forskningsprosjekt i matematikk om grafer vil jeg vise anvendelsen av grafteori på ulike områder av menneskelig aktivitet.

Introduksjon
Kapittel 1. Bli kjent med grafer
1.1. Historien om grafer.
1.2. Typer grafer
Kapittel 2. Muligheter for å anvende grafteori på ulike områder av hverdagen
2.1. Anvendelse av grafer på ulike områder av menneskers liv
2.2. Anvendelse av grafer i problemløsning
2.3. Familietre er en av måtene å anvende grafteori på
2.4. Beskrivelse av forskningen og sammenstillingen av slektstreet til familien min
Konklusjon
Referanser
applikasjoner

"I matematikk er det ikke formlene som bør huskes,
men prosessen med å tenke."
E.I. Ignatyeva

Introduksjon

Teller er overalt! I forskningsoppgaven min om matematikk om emnet "I verden av grafer" vil vi snakke om grafer som ikke har noe å gjøre med fortidens aristokrater. "" har roten til det greske ordet " grafo", Hva betyr " skriving" Den samme roten i ordene " rute», « biografi», « holografi».

For første gang med konseptet " kurve” Jeg møttes mens jeg løste matematikk-olympiadeoppgaver. Vanskeligheter med å løse disse problemene ble forklart med fraværet av dette emnet i den obligatoriske skolens læreplan. Problemet som oppsto var hovedgrunnen til å velge tema for dette forskningsarbeidet. Jeg bestemte meg for å studere i detalj alt relatert til grafer. Hvor mye grafmetoden brukes og hvor viktig den er i folks liv.

Det er til og med en spesiell seksjon i matematikk, som kalles: " Grafteori" Grafteori er en del av begge topologi, så kombinatorikk. Det faktum at dette er en topologisk teori følger av uavhengigheten av egenskapene til grafen fra plasseringen av toppunktene og typen linjer som forbinder dem.

Og bekvemmeligheten av å formulere kombinatoriske problemer i form av grafer har ført til at grafteori har blitt et av kombinatorikkens kraftigste verktøy. Når du løser logiske problemer, er det vanligvis ganske vanskelig å holde i minnet mange fakta gitt i tilstanden, etablere forbindelser mellom dem, uttrykke hypoteser, trekke spesielle konklusjoner og bruke dem.

Finn ut funksjonene ved bruk av grafteori til å løse problemer og i praktiske aktiviteter.

Studieobjekt er matematiske grafer.

Gjenstand for forskning er grafer som en måte å løse en rekke praktiske problemer på.

Hypotese: Hvis grafmetoden er så viktig, vil den absolutt bli mye brukt i ulike felt av vitenskap og menneskelig aktivitet.

For å nå dette målet la jeg frem følgende oppgaver:

1. bli kjent med grafteoriens historie;
2. studere de grunnleggende begrepene grafteori og graftyper;
3. vurdere måter å løse problemer ved hjelp av grafer;
4. vise bruken av grafteori på ulike områder av menneskelivet;
5. opprette et slektstre av familien min.

Metoder: observasjon, søk, utvalg, analyse, forskning.

Studere:
1. Internett-ressurser og trykte publikasjoner ble studert;
2. områder av vitenskap og menneskelig aktivitet der grafmetoden brukes er skissert;
3. løsning av problemer ved bruk av grafteori vurderes;
4. Jeg studerte metoden for å sette sammen familietreet til familien min.

Relevans og nyhet.
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. Grafteori brukes i ulike områder av moderne matematikk og dens mange anvendelser, spesielt innen økonomi, teknologi og ledelse. Å løse mange matematiske problemer blir lettere hvis du kan bruke grafer. Å presentere data i form av en graf gjør det klarere og enklere. Mange matematiske bevis blir også forenklet og blir mer overbevisende hvis grafer brukes.

For å sikre dette foreslo direktøren og jeg til elever på 5.-9.trinn, deltakere på skole- og kommuneturer. All-russisk Olympiade skolebarn, 4 problemer i å løse som du kan bruke grafteori ( Vedlegg 1).

Resultatene av å løse problemene er som følger:
Totalt 15 elever (5. trinn - 3 elever, 6. trinn - 2 elever, 7. trinn - 3 elever, 8. trinn - 3 elever, 9. trinn - 4 elever) brukte grafteori i 1 oppgave - 1, i 2 oppgave - 0 , i oppgave 3 – 6, oppgave 4 – 4 elever.

Praktisk betydning forskning er at resultatene utvilsomt vil være av interesse for mange mennesker. Har ikke noen av dere prøvd å bygge slektstreet deres? Hvordan gjøre dette riktig?
Det viser seg at de enkelt kan løses ved hjelp av grafer.

Vitenskapelig samfunn studenter

"Søk"

40 Åpent regionalt Vitenskapelig konferanse studenter.

Matematikkdelen.

Vitenskapelig arbeid om emnet:

"Teller" i min stamtavle

Fullført av: Victoria Loburets

7. klasse elev

Kommunal utdanningsinstitusjon "Kulomzinskaya ungdomsskole"

Veileder:

Lysenko Olga Grigorievna

matematikklærer

Kommunal utdanningsinstitusjon "Kulomzinskaya ungdomsskole"

Omsk - 2008

1. 
   Relevans og nyhet
2. 
   Mål og oppgaver

II. HOVEDDEL
1. Konseptet med grafer

2. Egenskaper til grafer

3.Bruk av grafer
III.Praktisk del
IV.Konklusjon
V. Litteratur

VI.vedlegg

INNHOLD

Introduksjon………………………………………………………………………………………………..…….3

S.1.1. Relevans og nyhet………………………………………………………..4

P.1.2.Mål og mål………………………………………………………………4

Kapittel I. Teoretisk del………………………………………….……….5

P.2.1 Konseptet med grafer…………………………………………………………………..5

Kapittel II. Praktisk del………………………………………………………………..11

S.2.1. “Teller” i min stamtavle…………………………………………..11

P.2.2 Løse logiske problemer ved hjelp av grafmetoden………………………..11

Konklusjon …………………………………………………………………………………………………...17

Litteratur……..…………………………………………………………………………..18

Søknader………………………………………………………………………………………………..19

Introduksjon
1. Relevans og nyhet
Grafteori brukes i ulike områder av moderne matematikk og dens mange anvendelser, spesielt innen økonomi, teknologi og ledelse. Grafteori er en viktig del av diskret matematikk, hvis praktiske rolle har økt på grunn av utviklingen av ulike automatiserte kontrollsystemer og diskret datateknologi; i teoretiske termer, i tillegg til forbindelser med kombinatorikk og geometri, har det vært endringer ved skjæringspunktet mellom grafteori med algebra og matematisk logikk.

Historisk sett oppsto grafteori fra gåteløsning for mer enn to hundre år siden. I svært lang tid var hun borte fra hovedretningene for vitenskapelig forskning. Grafteorien fikk en drivkraft for utvikling ved overgangen til 1800- og 1900-tallet, da antallet verk innen topografi og kombinatorikk, som den er nært knyttet til, økte kraftig. Den tidligste omtale av grafer finnes i arbeidet til L. Euler (1736). På midten av 1800-tallet utviklet elektroingeniøren G. Kirchhoff teorien om trær for å studere elektriske kretser, og matematiker A. Cayley løste i forbindelse med beskrivelsen av hydrokarbonene opptellingsproblemer for tre typer trær. Grafteori tok endelig form som en matematisk disiplin i 1936. etter utgivelsen av D. Koenigs monografi "The Theory of Finite and Infinite Graphs".

Nylig har grafer og relaterte forskningsmetoder organisk gjennomsyret ulike nivåer nesten all moderne matematikk. Grafteori finner mange anvendelser innen ulike felt av matematikk: algebra, geometri, topologi, kombinatorikk, kodingsteori, operasjonsforskning, og innen fysikk, kjemi, lingvistikk, økonomi, psykologi og andre vitenskaper.

Å løse mange matematiske problemer blir lettere hvis du kan bruke grafer. Å presentere data i form av en graf gjør det klarere og enklere.

Nyheten i dette arbeidet er beviset på effektiviteten til grafmetoden for å løse logiske problemer.

Hovedmålet med skolematematikkundervisning er å utvikle elevenes mentale evner. Vi trenger en overgang fra informasjons- og forklaringsteknologi til aktivitetsutviklingsteknologi rettet mot utvikling personlige kvaliteter hvert skolebarn. Ikke bare den ervervede kunnskapen skal bli viktig, men også metodene for assimilering og bearbeiding. pedagogisk informasjon, utvikling kognitiv aktivitet og elevens kreative potensial. De fleste skoleelever vil neppe bruke sin tilegnede kunnskap i matematikk i hverdagen, selv om mange av dem vil uteksamineres fra tekniske universiteter. En person glemmer raskt kunnskapen som han ikke bruker konstant, men logisk utvikling forblir hos ham for alltid. Det er dette aktuelle temaet om studentpersonlighetsutvikling som arbeidet mitt er dedikert til.

Gjenstand forskning er prosessen med å lære elevene grafmetoden.

Hypotese: i henhold til vår antagelse kan løsning av logiske problemer av elever ved hjelp av grafmetoden bidra til dannelse og utvikling av logisk tenkning.

Basert på hypotesen er følgende mål og målsettinger for studien fremmet.

2. Mål og mål.
Mål: bruk grafmetoden for å løse logiske problemer, og fremme utviklingen av logisk tenkning, vurder å løse problemer ved å bruke konseptet "Graph", sjekk implementeringen av "Graphs" på genealogier.

Oppgaver:

1) Studer populærvitenskapelig litteratur om dette problemet.

2) Undersøk implementeringen av «Graphs» for å avklare familieforhold.

3) Analyser resultatene av forsøkene.

4) Studie av «graf»-metoden som metode for å løse logiske problemer.

Kapittel I. Teoretisk del

S.2.1. Konseptet med grafer

Ordet "graf" i matematikk betyr et bilde med flere punkter tegnet, hvorav noen er forbundet med linjer. Matematiske grafer med den adelige tittelen "telling" er forbundet med en felles opprinnelse fra det latinske ordet "graphio" - jeg skriver. Typiske grafer er flyselskapsdiagrammer, som ofte legges ut på flyplasser, t-banediagrammer og på geografiske kart - et bilde jernbaner(Figur 1). De valgte punktene i grafen kalles dens toppunkter, og linjene som forbinder dem kalles kanter.

Bruker grever og adel. Figur 2 viser en del av slektstreet til en kjent adelsfamilie. Her er hjørnene medlemmene av denne slekten, og segmentene som forbinder dem er slektskapsforholdene som fører fra foreldre til barn.

Ordet "tre" i grafteori betyr en graf der det ikke er noen sykluser, det vil si der det er umulig å gå fra et bestemt toppunkt langs flere forskjellige kanter og gå tilbake til samme toppunkt. Et slektstre vil også være et tre i betydningen grafteori dersom det ikke fantes ekteskap mellom slektninger i denne familien.

Det er ikke vanskelig å forstå at en tregraf alltid kan avbildes slik at kantene ikke krysser hverandre. Grafer dannet av toppunktene og kantene til konvekse polyedre har samme egenskap. Figur 3 viser grafer som tilsvarer fem vanlige polyedre. I grafen som tilsvarer et tetraeder er alle fire toppunktene forbundet parvis med kanter.

Tenk på en graf med fem toppunkter koblet parvis til hverandre (fig. 4). Her krysser kantene på grafen seg. Det er umulig å skildre ham på en slik måte at det ikke er noen kryss, akkurat som det er umulig å oppfylle intensjonene til de tre personene beskrevet av Lewis Carroll. De bodde i tre hus, ikke langt fra dem var det tre brønner: en med vann, en annen med olje og den tredje med syltetøy, og de gikk til dem langs stiene vist i figur 5. En dag kranglet disse menneskene og bestemte seg for å trekke stier fra husene sine til brønner slik at disse stiene ikke krysser hverandre. Figur 6 viser nok et forsøk på å bygge slike løyper.

Grafene som er avbildet i figur 4 og 5 viser seg å spille en avgjørende rolle for å bestemme for hver graf om den er plan, det vil si om den kan tegnes på et plan uten å krysse kantene. Den polske matematikeren G. Kuratowski og akademiker

L.S. Pontryagin beviste uavhengig at hvis grafen ikke er plan, så "sitter" minst en av grafene vist i figur 4 og 5 i den, det vil si en "komplett fem-vertex" eller en "hus-brønner" graf. .

Grafer er blokkdiagrammer av dataprogrammer, nettverkskonstruksjonsgrafer, der toppunkter er hendelser som indikerer fullføring av arbeid på et bestemt område, og kantene som forbinder disse toppunktene er arbeid som kan begynne etter at en hendelse har skjedd og må fullføres for å fullføre den neste .

Hvis kantene på en graf har piler som indikerer retningen til kantene, kalles en slik graf rettet.

Pilen fra en jobb til en annen i grafen vist i fig. 7 betyr arbeidsrekkefølgen. Du kan ikke begynne å montere vegger uten å fullføre byggingen av fundamentet; for å starte etterbehandlingen må du ha vann på gulvene osv.

Fig.7.

Tall er angitt nær toppene av grafen - varigheten i dager for det tilsvarende arbeidet. Nå kan vi finne ut kortest mulig byggevarighet. For å gjøre dette, fra alle banene langs grafen i retning av pilene, må du velge banen hvis sum av tall ved hjørnene er størst. Den kalles den kritiske banen (i fig. 7 er den uthevet i brunt). I vårt tilfelle får vi 170 dager. Og reduserer man tiden for legging av det elektriske nettet fra 40 til 10 dager, så reduseres også byggetiden med 30 dager? Nei, i dette tilfellet vil den kritiske banen ikke gå gjennom dette toppunktet, men gjennom toppunktene som tilsvarer konstruksjonen av gropen, legge grunnlaget osv. Og Total tid bygging vil være på 160 dager, dvs. perioden reduseres med kun 10 dager.

Figur 8 viser et kart over veier mellom landsbyene M, A, B, C, D.

Her er hvert annet hjørne forbundet med en kant. En slik graf kalles komplett. Tallene i figuren angir avstandene mellom landsbyene langs disse veiene. La det bli postkontor i landsby M og postmannen skal levere brev til de fire andre landsbyene. Det er mange forskjellige reiseruter. Hvordan velge den korteste? Den enkleste måten er å analysere alle alternativene. En ny graf (under) vil hjelpe deg med dette, hvor du enkelt kan se mulige ruter. Topp M på toppen er starten på rutene. Du kan begynne å flytte fra den med fire forskjellige måter: i A, i B, i C, i D. Etter å ha besøkt en av landsbyene er det tre muligheter for å fortsette ruten, deretter to, så veien til den siste landsbyen og igjen til M. Totalt 4 × 3 × 2 × 1 = 24 måter.

La oss plassere tall langs kantene på grafen som indikerer avstandene mellom landsbyene, og på slutten av hver rute skriver vi summen av disse avstandene langs ruten. Av de 24 tallene som er oppnådd, er de minste to tall på 28 km, tilsvarende ruter M-V-B-A-G-M og M-G-A-B-V-M. Dette er samme vei, men reist i forskjellige retninger. Merk at grafen i fig. 8 kan også gjøres retningsbestemt ved å angi retningen fra topp til bunn på hver av kantene, som ville tilsvare postmannens bevegelsesretning. Lignende problemer oppstår ofte når man finner de beste alternativene for å distribuere varer til butikker og byggematerialer til byggeplasser.

Grafer brukes ofte til å løse logiske problemer som involverer oppregning av alternativer. Tenk for eksempel på følgende problem. Bøtten inneholder 8 liter vann, og det er to panner med en kapasitet på 5 og 3 liter. du må helle 4 liter vann i en fem-liters panne og la 4 liter stå i bøtta, dvs. hell vannet likt i bøtta og en stor panne. Løsning: Situasjonen i hvert øyeblikk kan beskrives med tre tall, der A er antall liter vann i bøtta, B er i en stor panne, C er i en mindre. I det første øyeblikket ble situasjonen beskrevet av en trippel av tall (8, 0, 0), hvorfra vi kan gå til en av to situasjoner: (3, 5, 0), hvis vi fyller en stor panne med vann, eller (5, 0, 3), hvis du fyller den mindre pannen. Som et resultat får vi to løsninger: en i 7 trekk, den andre i 8 trekk.

På lignende måte kan du lage en graf av et hvilket som helst posisjonsspill: sjakk, dam, tic-tac-toe, hvor posisjonene blir til hjørner, og de rettede segmentene mellom dem vil bety at du i ett trekk kan flytte fra en posisjon til en annen, i pilens retning. Men for sjakk og dam vil en slik graf være veldig stor, siden de forskjellige posisjonene i disse spillene teller i millioner. Men for spillet "tic-tac-toe" på et 3x3-brett er det ikke så vanskelig å tegne den tilsvarende grafen, selv om den vil inneholde flere titalls (men ikke millioner) hjørner. Når det gjelder grafer, kan problemet med tilsetting i stillinger enkelt formuleres og løses. Nemlig: Hvis det er flere ledige stillinger og en gruppe personer som er villige til å fylle dem, og hver av søkerne er kvalifisert for flere stillinger, under hvilke forutsetninger vil da hver av søkerne kunne få jobb i en av sine spesialiteter?

Egenskapene til grafer avhenger ikke av om toppunktene er forbundet med segmenter eller buede linjer. Dette gjør det mulig å studere egenskapene deres ved å bruke en av de unge vitenskapene - topologi, selv om problemene med grafteori i seg selv er typiske kombinatoriske problemer.

Kapittel II. Praktisk del.
S.2.1. "Teller" i min stamtavle.
Arbeidsmetoder:

Sammenligning og analyse av eksperimentelle resultater.

Arbeidsmetode:

Følgende ble valgt ut til forskning:

A) Min families stamtavle, dataarkiver, fødselsattester.

B) Stamtavle til Golitsyn-fyrstene, dataarkiver.

Jeg drev forskning, la forskningsresultatene inn i diagrammer og analyserte dem.

Metode 1.
Mål: sjekk implementeringen av "Teller" på stamtavlen din.

Resultater: Skjema 1 (se vedlegg 1).

Metode 2.
Mål: sjekk implementeringen av "tellingene" på slektsforskningen til Golitsyn-prinsene.

Resultat: skjema 2 (se vedlegg 2).

Konklusjon: Jeg la merke til at stamtavlen er en typisk graf.
S. 2.2. Løse logiske problemer ved hjelp av grafmetoden
I løpet av alle årene med å studere på skolen løser vi mange forskjellige problemer, inkludert logiske: underholdende problemer, gåter, anagrammer, rebuser, etc. For å lykkes med å løse problemer av denne typen, må du kunne identifisere dem generelle tegn, legge merke til mønstre, sette frem hypoteser, teste dem, bygge resonnementskjeder, trekke konklusjoner. Logiske problemer skiller seg fra vanlige ved at de ikke krever beregninger, men løses ved hjelp av resonnement. Vi kan si at en logisk oppgave er spesiell informasjon som ikke bare må behandles i henhold til en gitt betingelse, men du også ønsker å gjøre det. Logikk bidrar til å assimilere kunnskap bevisst, med forståelse, d.v.s. ikke formell; skaper mulighet for bedre gjensidig forståelse. Logikk er kunsten å resonnere, evnen til å trekke riktige konklusjoner. Dette er ikke alltid lett, fordi svært ofte er den nødvendige informasjonen "forkledd", presentert implisitt, og du må kunne trekke den ut. Som du vet, gir syn fødsel til tenkning. Et problem oppstår: hvordan etablere logiske sammenhenger mellom ulike fakta og hvordan formulere dem til en enkelt helhet. Metoden med grafdiagrammer lar deg se fremdriften til beviset og løsningen av problemer, noe som gjør beviset mer visuelt og lar deg kort og nøyaktig presentere bevisene for teoremer og løsninger på problemer.

Eksempel 1.1. Røde, blå, gule og grønne blyanter er i fire bokser, en om gangen. Fargen på blyanten er forskjellig fra fargen på boksen. Det er kjent at en grønn blyant er i en blå boks, men en rød blyant er ikke i en gul. Hvilken boks kommer hver blyant i?

Løsning. La oss betegne blyanter og bokser med prikker. En heltrukket linje vil indikere at blyanten er i den tilsvarende boksen, og en stiplet linje vil indikere at den ikke er det. Så, med tanke på problemet, har vi G1 (fig. 1).

Figur 1
Deretter fullfører vi grafen i henhold til følgende regel: siden det kan være nøyaktig én blyant i boksen, bør en hel linje og tre prikkete komme ut av hvert punkt. Resultatet er en graf G2 som gir en løsning på problemet.

Eksempel 1.2. Tre venner snakker: Belokurov, Chernov og Ryzhov. Brunetten sa til Belokurov: "Det er merkelig at en av oss er blond, en annen er brunette, den tredje er rød, men ingens hårfarge samsvarer med etternavnet deres." Hvilken hårfarge har hver av vennene dine?

Løsning. La oss konstruere en graf over forholdet spesifisert i problemstillingen. For å gjøre dette velger vi først og fremst settet med etternavn M og settet med hårfarger K, hvis elementer vil bli betegnet med prikker. La oss kalle punktene til settet M bokstaver B, H, R(Belokurov, Chernov og Ryzhov); poeng i det andre settet – b, br, r(blond, brunette, rød). Hvis et punkt fra ett sett tilsvarer et punkt fra et annet, vil vi koble dem med en heltrukket linje, og hvis det ikke samsvarer, vil vi koble dem med en stiplet linje. Tilstanden til problemet indikerer bare inkonsekvenser, derfor skal først grafen vist i figur 2 vises.

Fig.2

Av betingelsene for oppgaven følger det at for hvert punkt fra settet M er det ett og bare ett punkt fra settet K, som tilsvarer det første, og omvendt, for hvert punkt fra settet K tilsvarer det ett og bare ett punkt fra mengden M. Problemet koker ned til: å finne denne eneste mulige samsvar mellom elementene i settene M og K, det vil si å finne tre heltrukne linjer som forbinder de tilsvarende punktene i mengdene.

Prinsippet for å løse problemet er enkelt. Hvis et punkt er forbundet med to punkter i et annet sett med stiplede linjer, må det være forbundet med det tredje punktet med en heltrukket linje. Derfor er grafen i figur 2 supplert med heltrukne linjer som forbinder punktene B Og R, R Og br(Fig. 3).

Fig.3
Deretter gjenstår det å koble punktet med en hel linje H og periode b, siden poenget H koblet til et punkt br stiplet linje og prikk R er allerede "opptatt" (fig. 4).

Ris. 4

Dermed leser vi automatisk svaret i grafen til denne figuren: Belokurov er rødhåret, Chernov er blond, Ryzhov er brunette.

I den følgende oppgaven hjelper bruken av grafer til å oppdage tilstedeværelsen av to løsninger.

Eksempel 1.3. Masha, Lida, Zhenya og Katya kan spille forskjellige instrumenter (cello, piano, gitar og fiolin), men hver spiller bare ett. De snakker forskjellige fremmedspråk (engelsk, fransk, tysk og spansk), men hver bare ett. Det er kjent at:

1. jenta som spiller gitar snakker spansk;

2. Lida spiller ikke fiolin eller cello og kan ikke engelsk;

3. Masha spiller ikke fiolin eller cello og kan ikke engelsk;

4. jenta som snakker tysk spiller ikke cello;

5. Zhenya vet fransk, men spiller ikke fiolin.

Hvem spiller hvilket instrument og hvilket? fremmed språk vet?

Løsning. Problemforholdene tilsvarer grafen vist i figur 5.

Ris. 5

La oss tegne sekvensielt følgende solide segmenter: KS, VZH, VF, AK (fig. 6).

Ris. 6

Dermed dannes to "solide" trekanter ZHVF og KSA. Vi utfører et annet kontinuerlig segment av bæreraketten. Nå er vi overbevist om at betingelsene for problemet ikke sikrer det entydige valget av det tredje punktet for hvert av parene av RN og GI. Følgende alternativer for "solide" trekanter er mulige: MGI og OSR eller LGI og MRN. Dermed har problemet to løsninger.

I noen tilfeller kan det være vanskelig å løse kombinatoriske problemer. Du kan gjøre søkeprosessen enklere ved å lære å bruke søkeverktøy som tabeller og grafer. De lar deg dissekere resonnementet og tydelig utføre et søk uten å gå glipp av noen muligheter.

Først, som den enkleste måten å organisere søket på, må du bli kjent med tabeller.

Tenk for eksempel på dette oppgave:

Det er to fartøy med en kapasitet på 3L og 5L. Hvordan bruke disse karene til å helle 4 liter vann fra en kran?

La oss starte fra slutten. Hvordan kan resultatet bli 4L? – Hell 1 liter fra en 5-liters beholder. Hvordan gjøre det? – Du må ha nøyaktig 2 liter i et 3-liters kar. Hvordan få dem? – Hell 3 liter fra en 5-liters beholder. La oss nå skrive ned løsningen på problemet først i form av en tabell.

Søket etter en løsning kan startes med handlingen 3+1, som vil føre til løsningen skrevet i følgende tabell.

Fra tallene 3 og 5 kan du lage uttrykk som har verdien 4:

5-3+5-3=4 og 3+3-5+3=4

Det er lett å verifisere at de resulterende uttrykkene samsvarer med løsningene funnet ovenfor.

Det andre organisatoriske verktøyet som kan brukes ved løsning av kombinatoriske problemer er grafer.

Jeg vil gi et eksempel på en løsning som bruker et graftre for å løse et kombinatorisk problem.

For eksempel må du løse oppgave:«En dag møttes fem venner. Alle hilste på hverandre og håndhilste. Hvor mange håndtrykk ble gjort?

Først blir det klart hvordan hver person skal utpekes. Med tanke på ulike tilbud, kom til den konklusjonen at det er raskere og mer praktisk å avbilde mennesker med prikker. Prikkene må plasseres omtrent i en sirkel, tegnet med en fargeblyant slik at notatene er klare og visuelle. Fra to punkter mot hverandre, tegn linjer - "hender", som møtes for å danne en linje. Slik kommer de til det symbolske bildet av et håndtrykk. Først blir alle håndtrykkene til en person kompilert (punktet er forbundet med linjer til alle de andre). Så går de videre til en annen person. Linjene som trekkes hjelper til å se hvem han allerede har sagt hei til og hvem han ikke har. De manglende håndtrykkene tegnes opp (det er bedre å tegne disse linjene i en annen farge, siden det senere vil være bedre å beregne totalt antall håndtrykk). Og de gjør dette til alle sier hei til hverandre. Bruk grafen mottatt, tell antall håndtrykk (det er 10 totalt).

Neste oppgave:

"Hvor mange tosifrede tall kan du lage ved å bruke tallene 1,2,3,4?"

Løsning. Nummer 12: du må vise at det begynner med tallet 1 og slutter med tallet 2. En løkke vises når du for eksempel angir tallet 11: pilen må begynne og slutte på samme nummer. Etter å ha oppdaget disse symbolene (prikker, linjer, piler, løkker) i de første oppgavene, begynte jeg å bruke dem til å løse forskjellige problemer, lage grafer av en eller annen type (Figur 2).

svar: 16 tall.

La meg gi noen eksempler:

1.To russiske spillere, to tyske og to amerikanske spillere nådde finalen i damturneringen. Hvor mange kamper blir det i finalen hvis alle spiller mot hverandre en gang og representanter fra samme land ikke spiller mot hverandre? (Fig. 3.).

n

N



I finalen spilles 4x6 = 24 kamper.
2. Det var fire typer godteri i vasen. Hvert barn tok to godterier. Og alle hadde forskjellige sett med godteri. Hvor mange barn kan det være? (graf i fig. 4).

Fra denne grafen blir det klart at det kan være 6 forskjellige sett med søtsaker, og derfor kan det være 6 barn.

Konklusjon: Grafproblemer har en rekke fordeler som gjør at de kan brukes til å utvikle resonnement og forbedre den logiske tenkningen til barn, fra barnehage til videregående skole. videregående skole. Språket i grafene er enkelt, klart og visuelt. Grafproblemer kan presenteres i en underholdende, leken form. På den annen side er grafproblemer vanskeligere å formalisere enn f.eks. skoleoppgaver i algebra krever det ofte ikke dyp kunnskap å løse dem, men det krever bruk av oppfinnsomhet.

Med deres hjelp kan du gi studentene ny kunnskap som vil gjøre det lettere for dem å studere informatikk i fremtiden; øke den logiske og mentale utviklingen til skolebarn; venne dem til selvstendig arbeid; utvikle sin fantasi og forbedre kommunikasjonskulturen.

Ved løsning av kombinatoriske problemer opprettholdes en nær sammenheng mellom tenkning og praktiske handlinger, en gradvis overgang til handlinger i sinnet sikres, og bidrar til utvikling av tenkningens kvalitet, som for eksempel variabilitet.

KONKLUSJON
Mens jeg gjorde dette arbeidet, studerte jeg en av de mest interessante problemene innen grafteori, jeg så på matematiske grafer, deres bruksområde, og løste flere problemer ved hjelp av grafer. Jeg lærte å bruke "grafer" for å klargjøre familieforhold. Jeg studerte grafmetoden som en av metodene for å løse logiske problemer.

Grafteori studeres ikke i skolekurset, men problemer i diskret matematikk støtes på ganske ofte ved ulike matematiske olympiader og konkurranser. Grafer er mye brukt i matematikk, teknologi, økonomi og ledelse. Kunnskap om det grunnleggende innen grafteori er nødvendig på ulike områder knyttet til produksjon og forretningsledelse (for eksempel nettverksbyggingsplaner, postleveringsplaner), og etter å ha blitt kjent med elementene i grafteori, håper jeg at jeg vil være i stand til å lykkes med å løse ikke bare Olympiade-problemer.

I fremtiden skal jeg fortsette å studere grafteori, fordi jeg fant denne delen av matematikk interessant og nyttig. I tillegg, mens jeg jobbet med forskningsarbeidet mitt, mestret jeg arbeidet på en datamaskin i tekstredigeringsprogrammet Word og Power Point. Jeg mener at jeg oppfylte målene for forskningsarbeidet.

Litteratur.

1. 
   Berezina L.Yu. Grafer og deres anvendelse. – M., 1979.
2. 
   Vilenkin N.Ya. Matematikk. – M.: Russisk ord, 1997.
3. 
   Gardner M. "Matematisk fritid" M.: Mir, 1972
4. 
   Gnedenko B.V. Sannsynlighetsteorikurs. - M.: URSS, 2005.
5. 
   Konnova L.P. Møt grevene. – Samara, 2001.
6. 
   Lykova I.A. Logiske gåter – M.: Karapuz, 2000.
7. 
   Savin A.V. encyklopedisk ordbok ung matematiker. 2. utgave, - M.: Pedagogy, 1989
8. 
   Shadrinova V.D. Kognitive prosesser og evner i læring - M.: Education, 1980
9. 
   Chistyakov V.P. Kurs i sannsynlighetsteori. M., utdanning, 1982.

Applikasjoner.
Vedlegg 1.
Loburets Victoria Vladimirovna, født i 1994.

Loburets V. N

1962
.

Orlovskaya L.V.

Side 1

Studentenes vitenskapelige forening

"Søk"

Informatikkseksjonen

Vitenskapelig arbeid om emnet:

"Hans Majestet greven"

Utført: Sapozhnikova Svetlana,

7. klasse elev

Kommunal utdanningsinstitusjon "Sergeevskaya Secondary School"

Okoneshnikovsky MR

Veileder: Garms Elena Anatolyevna,

IT-lærer

Kommunal utdanningsinstitusjon "Sergeevskaya Secondary School"

Omsk - 2010
Innhold

Studentvitenskapelig samfunn 1

"Søk" 1

Vitenskapelig arbeid om emnet: 1

Innledning 3

GRAFTEORI 4

1.2. Euleriske grafer 7

1.3. Broproblemet, Leonhard Euler og Graph Theory 8

2.1. Løse problemer ved hjelp av grafer "En dag i grevens liv" 11

Bibliografi 16

Introduksjon

Forskningens relevans. Dette er andre året nå jeg har vært interessert i sjakk og har studert på skolen i sjakklubben «Sjakkmatt». I en av klassene som hjemmelekser En oppgave ble foreslått der det var nødvendig å beregne omorganiseringen av brikker i et mindre antall trekk. Hvordan gjøre det? Jeg begynte å lete etter løsninger, og det viste seg at dette kan gjøres ved hjelp av grafer. Tidligere kom jeg over konseptet "telle" bare i historietimen når jeg studerte emnet adel.

Grafer interesserte meg på grunn av deres evne til å hjelpe til med å løse ulike gåter, matematiske og logiske problemer. Grafteori er for tiden en intensivt utviklende gren av diskret matematikk. Dette forklares med det faktum at mange objekter og situasjoner er beskrevet i form av grafmodeller: kommunikasjonsnettverk, kretsløp av elektriske og elektroniske enheter, kjemiske molekyler, relasjoner mellom mennesker, alle slags transportopplegg og mye, mye mer. Svært viktig for det sosiale livets normale funksjon. Det er denne faktoren som bestemmer relevansen av deres mer detaljerte studie. Jeg bestemte meg for å finne ut hvilken rolle grafer spiller i hverdagen.

Studieobjekt: konsept for graf
Studieemne: grad av prevalens av grafbruk
Hensikten med studien: Utforsk rollen til grafer i livene våre.
Forskningsmål:

1. bli kjent med historien om fremveksten av grafer;

2. bli kjent med de grunnleggende konseptene for en graf, typer, elementer;

3.lære å løse problemer ved hjelp av grafer;

4. lag ditt eget slektstre.
Forskningsmetoder: delvis - søk, analytisk.

Kapittel 1

GRAFTEORI

1. 
   Konseptet med en graf

Ordet "graf" i matematikk betyr et bilde med flere punkter tegnet, hvorav noen er forbundet med linjer. De er forbundet med den adelige tittelen "greve" av en vanlig opprinnelse fra det latinske ordet "graphio" - jeg skriver.

I matematikk er definisjonen av en graf gitt som følger: "en graf er et begrenset sett med punkter, hvorav noen er forbundet med linjer."

I informatikk forstås en graf som et middel for visuelt å representere sammensetningen og strukturen til et system.

Grafen består av toppunkter og forbindelseslinjer. Topppunkter kan avbildes som sirkler, ovaler, prikker eller rektangler. Topppunkter kan kobles sammen med buer eller kanter.

Forbindelser mellom hjørner er representert med linjer. Hvis linjen er rettet (dvs. med en pil), kalles den en bue; hvis den ikke er rettet (dvs. uten pil), kalles den en kant. Det er generelt akseptert at en kant erstatter to buer rettet i motsatte retninger.

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

Alle hjørner forbundet med en bue eller kant kalles tilstøtende.

selv om begrepet "graf" først ble laget i 1936 av den ungarske matematikeren Dénes König.

Ved hjelp av grafer ble løsningen av problemer formulert i ulike kunnskapsfelt ofte forenklet: innen automasjon, elektronikk, fysikk, kjemi osv. Grafer hjelper til med å løse matematiske og økonomiske problemer.

Et grafoppsett som består av "isolerte" hjørner kalles en nullgraf. (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)

Grader av toppunkter og telling av antall kanter.

Antall kanter som forlater et toppunkt av grafen kalles graden av toppunktet. Et toppunkt på en graf som har en oddetallsgrad kalles oddetall, og et toppunkt som har en partallsgrad kalles partall.

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 var det som trengte å bli bevist.

TEOREM.

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.
Merk at hvis en komplett graf har n toppunkter, vil antallet kanter være lik

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.

1.2. Euleriske grafer

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

Disse grafene er oppkalt etter vitenskapsmannen Leonhard Euler.

Regularitet 3 (følger av teoremet vi vurderte).
Det er umulig å tegne en graf med et oddetall odde hjørner.
Mønster 4.

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 5.

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 6.

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.

Fig. 6 (Eulerian grafer)

Sammenkoblede grafer.

En graf kalles koblet hvis to av dens toppunkter kan forbindes med en bane, det vil si en sekvens av kanter, som hver begynner på slutten av den forrige.

En graf sies å være frakoblet hvis 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 går fra tilkoblet til frakoblet) en 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 de sammenkoblede komponentene i grafen. Hver tilkoblet komponent er selvfølgelig en tilkoblet graf. Merk at en tilkoblet graf har én tilkoblet komponent.

1.3. Broproblemet, Leonhard Euler og grafteori

Tidligere Koenigsberg (nå Kaliningrad) ligger ved elven Pregel. Innenfor byen vasker elven to øyer. Det ble bygget broer fra kysten til øyene. De gamle broene har ikke overlevd, men et kart over byen står igjen, hvor de er avbildet.

Følgende gåte har lenge vært vanlig blant innbyggerne i Königsberg: hvordan krysse alle broene uten å krysse noen av dem to ganger? Mange Königsbergere prøvde å løse dette problemet både teoretisk og praktisk under turer. Men ingen lyktes, men de klarte heller ikke å bevise at det til og med var teoretisk umulig.

Dette spørsmålet har tiltrukket seg oppmerksomheten til forskere forskjellige land. I 1736 interesserte problemet med syv broer den fremragende matematikeren, medlem av St. Petersburgs vitenskapsakademi, Leonhard Euler, som han skrev om i et brev til den italienske matematikeren og ingeniøren Marioni datert 13. mars 1736. I dette brevet skriver Euler at han var i stand til å finne en regel, ved hjelp av hvilken det er lett å finne ut om det er mulig å gå over alle broene uten å passere noen av dem to ganger (i tilfellet med de syv broene i Königsberg, dette er umulig).

Dessuten løste han ikke bare dette spesifikke problemet, men kom opp med en generell metode for å løse lignende problemer. Euler handlet som følger: han "komprimerte" landet til punkter, og "strakte" broene til linjer, som vist i figur 9 a, b.

Figur 9

I et forenklet diagram av deler av en by (graf), tilsvarer broer linjer (kanter av grafen), og deler av byen tilsvarer punkter som forbinder linjer (hjørnepunkter på grafen). Under sin resonnement kom Euler til følgende konklusjoner:

Antall odde hjørner (hjørner som et oddetall kanter fører til) i en graf er alltid partall. Det er umulig å tegne en graf som har et oddetall oddepunkt.

Hvis alle toppunktene på grafen er jevne, kan du tegne en graf uten å løfte blyanten fra papiret, og du kan starte fra hvilket som helst toppunkt på grafen og avslutte den på samme toppunkt.

En graf med mer enn to odde hjørner kan ikke tegnes med ett slag.

La oss formulere oppgaven tydelig. Under hvilke forhold er det mulig å krysse alle kantene på en graf, passere hver enkelt nøyaktig én gang? Løsningen viste seg å være veldig enkel. La oss telle hvor mange kanter som kommer ut av hvert toppunkt. Noen av disse tallene vil være partall og andre vil være oddetall. Vi vil kalle toppunktene selv om de har et partall av kanter, og ellers oddetall. Som vi allerede vet: antall kanter som kommer ut av et gitt toppunkt kalles graden av toppunktet. Et toppunkt av en graf som har merkelig grad, kalles oddetall, og en partallsgrad kalles partall.
Grafen til Königsberg-broene hadde fire odde hjørner, derfor er det umulig å gå over alle broene uten å passere en av dem to ganger.
Mens han løste problemet med Königsberg-broene, etablerte Euler spesielt egenskapene til grafen:

• 
  Hvis alle toppunktene i grafen er jevne, kan du tegne en graf med ett slag (det vil si uten å løfte blyanten fra papiret og uten å tegne to ganger langs samme linje). I dette tilfellet kan bevegelsen starte fra hvilket som helst toppunkt og ende ved samme toppunkt.
• 
  En graf med to odde hjørner kan også tegnes med ett slag. Bevegelsen må begynne fra et hvilket som helst oddetall og ende ved et annet oddetall.
• 
  En graf med mer enn to odde hjørner kan ikke tegnes med ett slag.

I Königsberg-broene-problemet er alle fire toppunktene i den tilsvarende grafen odde, det vil si at det er umulig å gå over alle broene én gang og avslutte stien der den ble startet.
Trær.

Et tre er en hvilken som helst tilkoblet graf som ikke har noen sykluser. Vi ble enige om å betrakte enhver graf som består av ett (isolert) toppunkt som et "tre".

En syklus er en vei der begynnelsen og slutten faller sammen.

Hvis alle toppunktene i en syklus er forskjellige, kalles en slik syklus en elementær (eller enkel) syklus. Hvis en syklus inkluderer alle kantene på grafen én gang, kalles en slik syklus en Euler-linje (fig. 10a). Grafen i fig. 10b har to sykluser: 1-2-3-4-1 og 5-6-7-5.

En bane i en graf fra et toppunkt til et annet er en sekvens av kanter langs hvilke en rute kan legges mellom disse toppunktene. I dette tilfellet skal ingen kant av ruten vises mer enn én gang. Toppen som ruten legges fra kalles begynnelsen av stien, toppen på slutten av ruten er slutten av stien.

Et hengende toppunkt er et toppunkt hvorfra nøyaktig en kant kommer ut. (Fig. 12)

Fig. 10 a;b
Eiendom 1.

For hvert par tretopp er det en unik sti som forbinder dem.

Denne egenskapen brukes når du finner alle forfedrene i et slektstre, for eksempel i den mannlige linjen, til enhver person hvis stamtavle er representert i form av et slektstre, som er et "tre" i betydningen grafteori.

Eiendom 2.

Hver kant i et tre er en bro.

Faktisk, etter å ha fjernet en hvilken som helst kant av et tre, "deler det" seg i to trær.

Fig. 12 (hengende topper er omringet)
En graf der hvilke som helst to hjørner er forbundet med nøyaktig én enkel bane, er et tre.

Bevis:

Det er åpenbart at denne grafen henger sammen. La oss anta at den har en løkke. Da er alle to hjørner i denne syklusen forbundet med minst to enkle baner. Vi mottok en selvmotsigelse, som betyr at antagelsen vår er feil.

Et tre er en graf der alle to hjørner er forbundet med nøyaktig én enkel bane.

LEMMA (om det hengende toppunktet)

Hvert tre har en hengende topp.

Bevis:

La oss vurdere et vilkårlig toppunkt av treet og følge en hvilken som helst kant og forlate det til et annet toppunkt. Hvis det ikke kommer flere kanter ut av det nye toppunktet, forblir vi i det, og ellers beveger vi oss langs en hvilken som helst annen kant lenger. Det er klart at på denne reisen vil vi aldri kunne nå en topp som vi allerede har besøkt: dette ville bety tilstedeværelsen av en syklus. Siden grafen har et begrenset antall hjørner, må reisen vår avsluttes. Men det kan bare ende på en hengende topp. Lemmaet er bevist.

Hva kan beskrives ved hjelp av grafer? La oss angi bruksområdene for denne beskrivelsen.

Grafer brukes på mange områder av praktisk og vitenskapelig aktivitet av folk.

For eksempel:

Kartet over T-banelinjer kan tenkes som en graf;

I kjemi kan en graf betraktes som en måte å representere strukturen til et molekyl på;

I medisin - spørsmålet om blodtype;

Et slektstre kan representeres som en graf;

Klassifikasjonssystemer i naturfag.

Hierarkisk struktur for administrativ ledelse av et foretak, universitet, etc.

I informatikk: diskfilsystem, Internett-domeneadressesystem, blokkdiagrammer av algoritmer.
Og mange flere forskjellige eksempler kan gis...

Kapittel 2

2.1. Løse problemer ved hjelp av grafer "En dag i en greves liv"

La oss se på å løse problemer ved hjelp av grafer fra skolehverdagen.

Oppgave 1. Om morgenen ble elever fra skolen vår brakt fra de omkringliggende landsbyene Volchino, Olkhovka, Kochkovatoe og Pavlovka til klassene. Figuren viser en graf som representerer informasjon om veier mellom fire landsbyer: Volchino, Olkhovka, Kochkovatoe, Pavlovka. Vektene på hjørnene er navnene på landsbyene, vektene på linjene er lengden på veiene i kilometer.

Bussruten er en graf.

Oppgave 2. Da vi møttes, håndhilste hver av klassekameratene den andre (hver ristet på hverandre). Hvor mange håndtrykk ble gjort hvis det var: 1) tre venner; 2) fire; 3) fem?

Løsning.

Problemet løses ved hjelp av komplette grafer.

1) Tre personer møtte:

Antall håndtrykk er lik antall kanter, dvs. 3.

2) Fire personer møtte:

Antall ribber 6; 6 håndtrykk mulig.

3) Fem personer møtte:

Det er 10 kanter i grafen; kanskje 10 håndtrykk.

Svar: 1)3; 2)6; 3)10.
I henhold til timeplanen har vi seks timer: geometri, historie, informatikk, geografi, russisk språk og fysikk.
Oppgave 3. I en geometritime ble det foreslått å konstruere en klassifiseringsgraf av geometriske objekter. Dette viste seg å være enkelt å gjøre ved å bruke konseptet med en graf.


Oppgave 4. Og i historietimen måtte vi lage et slektstre. Familietre. Bruker grever og adel. For eksempel, i et slektstre er hjørnene medlemmer av klanen, og segmentene som forbinder dem er slektskapsforhold.

Alle vet at ordet "greve" betyr en adelig tittel, for eksempel grev Lev Nikolaevich Tolstoy. Det er en annen graf i figuren - en del av slektstreet til grev L.N. Tolstoj. Her er hjørnene forfatterens forfedre, og kantene viser familieforbindelsene mellom dem.

Oppgave 5. I informatikkklassen møttes vi nytt emne"Algorithmer". Og til min overraskelse viste det seg at et blokkdiagram er en rettet graf.Et blokkdiagram av en algoritme er en graf over kontrollprosessen til en eller annen eksekutør. Blokkene - toppunktene i denne grafen - indikerer individuelle kommandoer, og buene indikerer sekvensen av overganger fra en kommando til en annen. I algoritmen starter en hvilken som helst bane fra startpunktet og slutter med en utgang til sluttpunktet. Innvendig kan banen være forskjellig avhengig av kildedataene.

Oppgave 6. I geografitimen så vi på et avsnitt. Og for å finne det raskere, åpnet jeg innholdet på slutten av læreboken. Og til min overraskelse la jeg merke til at strukturen til delene av læreboken gjenspeiles i form av et tre.

Oppgave 7. Under den russiske språktimen var temaet "Tall", og læreren foreslo at vi skulle lage en støttende oppsummering.

Tall i det russiske språket er klassifisert i henhold til sammensetning og betydning. Basert på deres sammensetning er de delt inn i enkle, komplekse og sammensatte. Eksempel på enkle tall: fire, fem. Eksempel på komplekse tall: seksti, fem hundre. Et eksempel på sammensatte tall: 35, 154. Basert på betydningen deles tall inn i ordinær og kardinal. Eksempel på ordenstall: andre, niende. Eksempel på kardinaltall: seks, to.

Etter timen løp vi alle til kafeteriaen, hvor det ble servert en fast lunsj. Jeg elsker borsjtsj, og naboen min ved pulten er rassolnik.

Oppgave 8. Spisestuen tilbyr to førsteretter: borsjtsj, rassolnik, samt fire andreretter: gulasj, koteletter, pølser, dumplings. List opp alle to-retters måltider som en middag kan bestille. Illustrer svaret ditt ved å konstruere et tre med mulige alternativer.

Løsning.

For å indikere alle to-retters måltider vil vi resonnere slik.

La oss velge en førsterett (borsjtsj) og legge til forskjellige andreretter en etter en

Svar: 8 forskjellige to-retters måltider.

Kommentar. I oppgaven er det gjort to valg, men hvert valg er fra sitt eget sett med alternativer.

Svar: 6 kombinasjoner.

Da jeg kom hjem, fullførte jeg raskt alle leksene mine. Og det semantiske nettverket, en kunnskapsmodell i form av en graf, hjalp meg med dette. Den er basert på ideen om at all kunnskap kan representeres som et sett med objekter (konsepter) og forbindelser (relasjoner) mellom dem.

Etter skolen, i klassene til klubbene "Underholdende informatikk" og "Sjekk og MAT", takket være grafteori, løste vi enkelt logiske problemer.

Om kvelden ba mamma meg gå på butikken for å kjøpe brød. "Brødbutikk"-systemet består av følgende elementer: brød, selger, kjøper, skranke, bil, sjåfør, laster, penger, sjekk. Toppunktene på grafen er de listede objektene, og buene er relasjonene mellom dem. Da jeg kom hjem fra butikken, tok jeg ufrivillig meg selv i å tenke på Counts: Counts omgir meg overalt.

Så grevene ble mine beste venner. Klassekamerater og lærere la merke til at prestasjonene mine i fag hadde blitt bedre. Men jeg vet at dette er takket være "Hans Majestet Greven"!

Konklusjon

Grafer er fantastiske matematiske objekter som kan brukes til å løse matematiske, økonomiske og logiske problemer. Du kan også løse ulike gåter og forenkle forholdene for problemer innen fysikk, kjemi, elektronikk og automatisering. Grafer brukes i sammenstilling av kart og familietrær.

Det er til og med en spesiell seksjon i matematikk kalt "Graph Theory". Grafer presenterer fakta som studeres i en visuell form. Teknikker for å løse logiske problemer ved hjelp av grafer er fengslende med sin naturlighet og enkelhet, og eliminerer unødvendig resonnement, som i mange tilfeller reduserer belastningen på minnet.

Grafteori er for tiden en intensivt utviklende gren av diskret matematikk. Dette forklares av det faktum at mange objekter og situasjoner er beskrevet i form av grafmodeller: kommunikasjonsnettverk, kretser av elektriske og elektroniske enheter, kjemiske molekyler, forhold mellom mennesker og mye mer.

Grafproblemer har en rekke fordeler som gjør at de kan brukes til å utvikle fantasi og forbedre logisk tenkning, og kan brukes til å løse mange geometriske problemer.

Bibliografi

1. Genkin, S. A., Itenberg I. V. Leningrad matematiske sirkler: en manual for

fritidsaktiviteter.-Kirov, 1994.

2. Gorbatsjov, V.G. Samling av Olympiade-oppgaver i matematikk. - M., 2004.

3. Ignatiev E.I. Matematisk kunnskapsrik. - Moskva, 1994

4. Ore, O. Grafer og deres anvendelse. - Moskva, 1979.

5. Perelman, Ya.I. Morsomme oppgaver. - Moskva, 2003

6. Fysikk- og matematikktidsskrift “Kvant”, A. Savin, nr. 6, 1994.

Side 1

Tredje by vitenskapelig

studentkonferanse

Informatikk og matematikk

Forskning

Euler-sirkler og grafteori i problemløsning

skolematematikk og informatikk

Valiev Airat

Kommunal utdanningsinstitusjon

«Ungdomsskole nr. 10 med fordypning

enkeltfag", 10 B klasse, Nizhnekamsk

Vitenskapelige veiledere:

Khalilova Nafise Zinnyatullovna, matematikklærer

IT-lærer

Naberezhnye Chelny

Introduksjon. 3

Kapittel 1. Euler sirkler. 4

1.1. Teoretisk grunnlag om Euler-sirkler. 4

1.2. Løse problemer ved hjelp av Euler-sirkler. 9

Kapittel 2. Om kolonner 13

2.1.Graf-teori. 1. 3

2.2. Løse problemer ved hjelp av grafer. 19

Konklusjon. 22

Bibliografi. 22

Introduksjon

«All vår verdighet ligger i tanken.

Det er ikke plass, det er ikke tid vi ikke kan fylle,

løfter oss, nemlig det, vår tanke.

La oss lære å tenke godt."

B. Pascal,

Relevans. Skolens hovedoppgave er ikke å gi barn en stor mengde kunnskap, men å lære elevene å tilegne seg kunnskap selv, evnen til å bearbeide denne kunnskapen og anvende den i hverdagen. De gitte oppgavene kan løses av en elev som ikke bare har evnen til å jobbe godt og hardt, men også en elev med utviklet logisk tenkning. I denne forbindelse, mange skoleartikler Ulike typer oppgaver er inkludert, som utvikler logisk tenkning hos barn. Når vi løser disse problemene, bruker vi ulike løsningsteknikker. En av løsningsmetodene er bruk av Euler-sirkler og grafer.

Hensikten med studien: studie av materiale brukt i matematikk- og informatikktimer, hvor Euler-sirkler og grafteori brukes som en av metodene for å løse problemer.

Forskningsmål:

1. Studer det teoretiske grunnlaget for begrepene: "Euleriske sirkler", "Graphs".

2. Løs problemene med skolekurset ved å bruke metodene ovenfor.

3. Sett sammen et utvalg materiell til bruk for elever og lærere i matematikk- og informatikktimer.

Forskningshypotese: bruk av Euler-sirkler og grafer øker klarheten når du løser problemer.

Studieemne: konsepter: "Euler-sirkler", "Graffer", problemer med et skolekurs i matematikk og informatikk.

Kapittel 1. Euler sirkler.

1.1. Teoretisk grunnlag om Euler-sirkler.

Euler-sirkler (Euler-sirkler) er en metode for modellering som er akseptert i logikk, en visuell representasjon av forholdet mellom volumer av konsepter ved bruk av sirkler, foreslått av den berømte matematikeren L. Euler (1707–1783).

Betegnelsen på forhold mellom volumene av konsepter ved hjelp av sirkler ble brukt av en representant for den athenske nyplatoniske skolen - Philoponus (VI århundre), som skrev kommentarer til Aristoteles' første analyse.

Det er konvensjonelt akseptert at en sirkel visuelt viser volumet til ett konsept. Omfanget av et konsept gjenspeiler helheten av objekter av en eller annen klasse av objekter. Derfor kan hvert objekt i en klasse av objekter representeres av et punkt plassert inne i en sirkel, som vist i figuren:

Gruppen av objekter som utgjør utseendet til en gitt klasse objekter er avbildet som en mindre sirkel tegnet inne i en større sirkel, slik det er gjort i figuren.

https://pandia.ru/text/78/128/images/image003_74.gif" alt="overlappende klasser" width="200" height="100 id=">!}

Dette er nettopp forholdet som eksisterer mellom omfanget av begrepene "student" og "Komsomol-medlem". Noen (men ikke alle) studenter er Komsomol-medlemmer; noen (men ikke alle) Komsomol-medlemmer er studenter. Den uskyggelagte delen av sirkel A gjenspeiler den delen av omfanget av begrepet «student» som ikke sammenfaller med omfanget av konseptet «Komsomol-medlem»; Den uskyggelagte delen av sirkel B gjenspeiler den delen av omfanget av konseptet «Komsomol-medlem» som ikke sammenfaller med omfanget av konseptet «student». Den skraverte delen, som er felles for begge kretser, angir studenter som er Komsomol-medlemmer og Komsomol-medlemmer som er studenter.

Når ikke et eneste objekt som vises i volumet av konsept A samtidig kan vises i volumet til konsept B, er i dette tilfellet forholdet mellom volumene av konsepter avbildet ved hjelp av to sirkler tegnet utenfor hverandre. Ikke et eneste punkt som ligger på overflaten av en sirkel kan være på overflaten av en annen sirkel.

https://pandia.ru/text/78/128/images/image005_53.gif" alt=" konsepter med samme volum - sammenfallende sirkler" width="200" height="100 id=">!}

Et slikt forhold eksisterer for eksempel mellom begrepene «grunnleggeren av engelsk materialisme» og «forfatteren av New Organon». Omfanget av disse konseptene er det samme, de gjenspeiler den samme historiske figuren - den engelske filosofen F. Bacon.

Det skjer ofte slik: ett begrep (generisk) er underordnet flere spesifikke begreper på en gang, som i dette tilfellet kalles underordnet. Forholdet mellom slike konsepter er avbildet visuelt av en stor sirkel og flere mindre sirkler, som er tegnet på overflaten av den større sirkelen:

https://pandia.ru/text/78/128/images/image007_46.gif" alt="motsatte begreper" width="200" height="100 id=">!}

Samtidig er det klart at mellom motsatte begreper er en tredje, gjennomsnittlig, mulig, siden de ikke fullstendig uttømmer omfanget av det generiske begrepet. Dette er akkurat forholdet som eksisterer mellom begrepene «lett» og «tungt». De utelukker hverandre. Det er umulig å si om det samme objektet, tatt på samme tid og i samme relasjon, at det er både lett og tungt. Men mellom disse konseptene er det en mellomting, en tredje: gjenstander er ikke bare lette og tunge, men også middels vekt.

Når det er et motstridende forhold mellom konsepter, blir forholdet mellom volumene av konsepter avbildet annerledes: sirkelen er delt inn i to deler som følger: A er et generisk konsept, B og ikke-B (betegnet som B) er motstridende konsepter . Motstridende konsepter utelukker hverandre og tilhører samme slekt, som kan uttrykkes ved følgende diagram:

https://pandia.ru/text/78/128/images/image009_38.gif" alt="definisjonsemne og predikat" width="200" height="100 id=">!}

Diagrammet over forholdet mellom volumene av emnet og predikatet i en generell bekreftende dom, som ikke er en definisjon av et begrep, ser annerledes ut. I en slik dom er omfanget av predikatet større enn omfanget av subjektet; omfanget av subjektet er helt inkludert i predikatets omfang. Derfor er forholdet mellom dem avbildet ved hjelp av store og små sirkler, som vist på figuren:

Skolebiblioteker" href="/text/category/shkolmznie_biblioteki/" rel="bookmark">skolebibliotek, 20 - i distriktet. Hvor mange av femteklassingene:

a) ikke er lesere av skolebiblioteket;

b) ikke er lesere av distriktsbiblioteket;

c) er kun lesere av skolebiblioteket;

d) er kun lesere av det regionale biblioteket;

e) er lesere av begge bibliotekene?

3. Hver elev i klassen lærer enten engelsk eller fransk, eller begge deler. engelske språk 25 personer studerer fransk, 27 personer studerer fransk, og 18 personer studerer begge deler. Hvor mange elever er det i klassen?

4. På et ark tegner du en sirkel med et areal på 78 cm2 og en firkant med et areal på 55 cm2. Skjæringsområdet mellom en sirkel og en firkant er 30 cm2. Den delen av arket som ikke er okkupert av sirkelen og firkanten har et areal på 150 cm2. Finn arealet av arket.

5. B barnehage 52 barn. Hver av dem elsker enten kake eller is, eller begge deler. Halvparten av barna liker kake, og 20 personer liker kake og is. Hvor mange barn elsker is?

6. Det er 86 elever i videregående skole i elevproduksjonsteamet. 8 av dem vet ikke hvordan de skal betjene verken traktor eller skurtresker. 54 elever mestret traktoren godt, 62 - skurtreskeren. Hvor mange personer fra dette teamet kan jobbe på både traktor og skurtresker?

7. Det er 36 elever i klassen. Mange av dem går på klubber: fysikk (14 personer), matematikk (18 personer), kjemi (10 personer). I tillegg er det kjent at 2 personer deltar på alle tre kretsene; Av de som går i to kretser er 8 personer involvert i matematiske og fysiske kretser, 5 er i matematiske og kjemiske kretser, 3 er i fysiske og kjemiske kretser. Hvor mange deltar ikke på noen klubber?

8. 100 sjetteklassinger på skolen vår deltok i en undersøkelse for å finne ut hvilke dataspill de likte best: simulatorer, oppdrag eller strategier. Som et resultat nevnte 20 respondenter simulatorer, 28 - oppdrag, 12 - strategier. Det viste seg at 13 skoleelever gir samme preferanse til simulatorer og oppdrag, 6 elever - til simulatorer og strategier, 4 elever - til oppdrag og strategier, og 9 elever er fullstendig likegyldige til de nevnte. dataspill. Noen av skoleelevene svarte at de var like interessert i simulatorer, oppdrag og strategier. Hvor mange av disse gutta er det?

Svar

https://pandia.ru/text/78/128/images/image012_31.gif" alt="Oval: A" width="105" height="105">1.!}

A – sjakk 25-5=20 – personer. vet hvordan man spiller

B – dam 20+18-20=18 – folk spiller både dam og sjakk

2. Ш – mange besøkende på skolebiblioteket

P – mange besøkende på distriktsbiblioteket

https://pandia.ru/text/78/128/images/image015_29.gif" width="36" height="90">.jpg" width="122 height=110" height="110">

5. 46. P – kake, M – is

6 – barn elsker kake

6. 38. T – traktor, K – skurtresker

54+62-(86-8)=38 – kan jobbe på både traktor og skurtresker

grafer" og systematisk studere egenskapene deres.

Enkle konsepter.

Det første av de grunnleggende konseptene for grafteori er konseptet om et toppunkt. I grafteori tas det som primær og er ikke definert. Det er ikke vanskelig å forestille seg det på ditt eget intuitive nivå. Vanligvis er toppene på grafen visuelt avbildet i form av sirkler, rektangler og andre figurer (fig. 1). Minst ett toppunkt må være til stede i hver graf.

Et annet grunnleggende konsept innen grafteori er buer. Vanligvis er buer rette eller buede segmenter som forbinder hjørner. Hver av de to endene av buen må falle sammen med et eller annet toppunkt. Tilfellet når begge ender av buen faller sammen med samme toppunkt er ikke utelukket. For eksempel, i fig. 2 er det akseptable bilder av buer, og i fig. 3 er de uakseptable:

I grafteori brukes to typer buer - urettet eller rettet (orientert). En graf som bare inneholder rettede buer kalles en rettet graf eller digraf.

Buer kan være ensrettet, der hver bue har bare én retning, eller toveis.

I de fleste applikasjoner er det mulig uten tap av mening å erstatte en rundstrålende bue med en toveis bue, og en toveis bue med to ensrettede buer. For eksempel, som vist i fig. 4.

Som regel er grafen enten umiddelbart konstruert på en slik måte at alle buer har samme retningskarakteristikk (for eksempel er alle ensrettet), eller bringes til denne formen gjennom transformasjoner. Hvis buen AB er rettet, betyr dette at av de to ender, regnes en (A) som begynnelsen, og den andre (B) er slutten. I dette tilfellet sier de at begynnelsen av buen AB er toppunkt A, og slutten er toppunkt B, hvis buen er rettet fra A til B, eller at buen AB kommer fra toppunkt A og går inn i B (fig. 5 ).

To toppunkter i en graf som er forbundet med en eller annen bue (noen ganger, uavhengig av buens orientering) kalles tilstøtende toppunkter.

Et viktig begrep i studiet av grafer er begrepet bane. En bane A1,A2,...An er definert som en endelig sekvens (tuppel) av toppunktene A1,A2,...An og buene A1, 2,A2,3,...,An-1, n som kobles sekvensielt sammen disse hjørnene.

Et viktig konsept i grafteori er begrepet tilkobling. Hvis det for noen av to hjørner av en graf er minst én bane som forbinder dem, kalles grafen koblet.

For eksempel, hvis du skildrer det menneskelige sirkulasjonssystemet som en graf, hvor toppunktene tilsvarer indre organer og buene tilsvarer blodkapillærer, så er en slik graf åpenbart koblet. Er det mulig å si at sirkulasjonssystemet til to vilkårlige personer er en frakoblet graf? Åpenbart ikke, siden de såkalte er observert i naturen. "Siamesiske tvillinger".

Tilknytning kan ikke bare være en kvalitativ egenskap ved en graf (tilkoblet/frakoblet), men også en kvantitativ.

En graf kalles K-koblet hvis hver av dens toppunkter er koblet til K andre toppunkter. Noen ganger snakker de om svake og sterkt sammenhengende grafer. Disse begrepene er subjektive. En forsker kaller en graf sterkt forbundet hvis antallet tilstøtende toppunkter, etter forskerens mening, er stort for hvert av dens toppunkter.

Noen ganger er tilkobling definert som en egenskap, ikke for hver, men for ett (vilkårlig) toppunkt. Da dukker det opp typedefinisjoner: en graf kalles K-koblet hvis minst en av dens toppunkter er koblet til K andre toppunkter.

Noen forfattere definerer tilkobling som den ekstreme verdien av en kvantitativ egenskap. For eksempel er en graf K-koblet hvis det er minst ett toppunkt i grafen som er koblet til K tilstøtende toppunkter og ingen toppunkt som er koblet til mer enn K tilstøtende toppunkter.

For eksempel, barnas tegning person (fig. 6) er en graf med maksimal tilkobling lik 4.

En annen grafkarakteristikk som er studert i en rekke problemer kalles ofte grafkardinalitet. Denne egenskapen er definert som antall buer som forbinder to toppunkter. I dette tilfellet vurderes ofte buer med motsatt retning separat.

For eksempel, hvis toppunktene på grafen representerer informasjonsbehandlingsnoder, og buene er ensrettede kanaler for overføring av informasjon mellom dem, bestemmes påliteligheten til systemet ikke av det totale antallet kanaler, men av det minste antallet kanaler i hvilken som helst retning.

Kardinalitet, som tilkobling, kan bestemmes både for hvert par av toppunkter i grafen, og for noen (vilkårlige) par.

Et vesentlig kjennetegn ved en graf er dens dimensjon. Dette konseptet forstås vanligvis som antall toppunkter og buer som eksisterer i en graf. Noen ganger er denne mengden definert som summen av mengdene av elementer av begge typer, noen ganger som et produkt, noen ganger som antall elementer av bare en (en eller annen) type.

Typer grafer.

Objekter som er modellert ved hjelp av grafer, er av svært mangfoldig karakter. Ønsket om å reflektere denne spesifisiteten førte til beskrivelsen stor kvantitet typer grafer. Denne prosessen fortsetter til i dag. Mange forskere, for deres spesifikke formål, introduserer nye varianter og utfører sine matematiske studier med større eller mindre suksess.

I hjertet av alt dette mangfoldet er flere ganske enkle ideer, som vi vil snakke om her.

Fargelegging

Graffarging er en veldig populær måte å endre grafer på.

Denne teknikken lar deg øke klarheten til modellen og øke den matematiske arbeidsmengden. Metoder for å introdusere farge kan være forskjellige. Både buer og hjørner er farget i henhold til visse regler. Fargen kan bestemmes én gang eller endres over tid (det vil si når grafen får noen egenskaper); farger kan konverteres etter visse regler osv.

La for eksempel grafen representere en modell av menneskelig blodsirkulasjon, der toppunktene tilsvarer indre organer, og buene tilsvarer blodkapillærer. La oss farge arteriene røde og venene blå. Da er det følgende utsagn åpenbart sant - i grafen under vurdering (fig. 8) er det, og bare to, toppunkter med utgående røde buer (den røde fargen er vist med fet skrift i figuren).

Lengde

Noen ganger har objektelementene som er modellert av toppunkter betydelig forskjellige karakterer. Eller, under formaliseringsprosessen, viser det seg å være nyttig å legge til noen fiktive elementer til elementene som faktisk finnes i objektet. I dette og noen andre tilfeller er det naturlig å dele opp grafens toppunkter i klasser (aksjer). En graf som inneholder toppunkter av to typer kalles todelt osv. I dette tilfellet er regler om forholdet mellom toppunkt inkludert i grafrestriksjonene forskjellige typer. For eksempel: "det er ingen bue som vil forbinde hjørner av samme type." En av variantene av grafer av denne typen kalles et "Petri-nett" (fig. 9) og er ganske utbredt. Petri garn vil bli diskutert mer detaljert i neste artikkel i denne serien.

Konseptet med daler kan brukes ikke bare på hjørner, men også på buer.

2.2. Løse problemer ved hjelp av grafer.

1. Problem om Königsberg-broene. I fig. 1 viser en skjematisk plan av den sentrale delen av byen Koenigsberg (nå Kaliningrad), inkludert to bredder av Pergola-elven, to øyer i den og syv forbindelsesbroer. Oppgaven er å gå rundt alle fire deler av landet, krysse hver bro én gang, og gå tilbake til utgangspunktet. Dette problemet ble løst (det ble vist at det ikke fantes noen løsning) av Euler i 1736. (Fig. 10).

2. Problemet med tre hus og tre brønner. Det er tre hus og tre brønner, på en eller annen måte plassert på et fly. Tegn en sti fra hvert hus til hver brønn slik at stiene ikke krysser hverandre (fig. 2). Dette problemet ble løst (det ble vist at det ikke er noen løsning) av Kuratovsky i 1930. (Fig. 11).

3. Problemet med fire farger. En inndeling av et plan i ikke-overlappende områder kalles et kart. Områder på et kart kalles tilstøtende hvis de har en felles grense. Oppgaven er å fargelegge kartet på en slik måte at ikke to tilstøtende områder males med samme farge (fig. 12). Siden slutten av århundret før sist har hypotesen vært kjent om at fire farger er nok til dette. I 1976 publiserte Appel og Heiken en løsning på firefargeproblemet, som var basert på et datasøk. Løsningen på dette problemet «programmessig» var en presedens som ga opphav til en heftig debatt, som på ingen måte er over. Essensen av den publiserte løsningen er å prøve et stort, men begrenset antall (ca. 2000) typer potensielle moteksempler til firefargesteoremet og vise at ikke et enkelt tilfelle er et moteksempel. Dette søket ble fullført av programmet på rundt tusen timer med superdatamaskindrift. Det er umulig å sjekke den resulterende løsningen "manuelt" - omfanget av oppregning går langt utover menneskelige evner. Mange matematikere reiser spørsmålet: kan et slikt "programbevis" betraktes som et gyldig bevis? Tross alt kan det være feil i programmet... Metoder for formelt å bevise riktigheten av programmer er ikke aktuelt for programmer av så kompleksitet som det som diskuteres. Testing kan ikke garantere fravær av feil og er i dette tilfellet generelt umulig. Dermed kan vi bare stole på programmeringsferdighetene til forfatterne og tro at de gjorde alt riktig.

4.

Dudeneys oppgaver.

1. Smith, Jones og Robinson jobber på samme togmannskap som sjåfør, konduktør og brannmann. Yrkene deres er ikke nødvendigvis navngitt i samme rekkefølge som etternavnene deres. Det er tre passasjerer med samme etternavn på toget som betjenes av brigaden. I fremtiden vil vi med respekt kalle hver passasjer "Mr."

2. Mr. Robinson bor i Los Angeles.

3. Konduktøren bor i Omaha.

4. Mr. Jones har lenge glemt all algebraen som han ble undervist på college.

5. Passasjeren, konduktørens navnebror, bor i Chicago.

6. Konduktøren og en av passasjerene, en kjent ekspert i matematisk fysikk, selv om de går til samme kirke.

7. Smith vinner alltid over brannmannen når de tilfeldigvis møtes på et slag biljard.

Hva er sjåførens etternavn? (Fig. 13)

Her er 1-5 antall trekk, i parentes er antall punkter for oppgaven som trekkene (konklusjonene) ble gjort på grunnlag av. Det følger videre av paragraf 7 at brannmannen ikke er Smith, derfor er Smith maskinisten.

Konklusjon

Analyse av teoretisk og praktisk materiale om emnet som studeres lar oss trekke konklusjoner om suksessen med å bruke Euler-sirkler og grafer for utvikling av logisk tenkning hos barn, skape interesse for materialet som studeres, bruke visuelle hjelpemidler i leksjonene, også som å redusere vanskelige problemer til enkle å forstå og løse.

Bibliografi

1. "Underholdende oppgaver i informatikk", Moskva, 2005

2. "Scenarioer for skoleferier" av E. Vladimirova, Rostov-on-Don, 2001

3. Oppgaver for nysgjerrige. , M., Education, 1992,

4. Ekstrafagarbeid i matematikk, Saratov, Lyceum, 2002.

5. Tallenes vidunderlige verden. , ., M., Education, 1986,

6. Algebra: lærebok for 9. klasse. , og andre, red. , - M.: Enlightenment, 2008