VLADIMIR STATSPEDAGOGISKE UNIVERSITET
ABSTRAKT
"GRAFTEORI"
Utført:
Zudina T.V.
Vladimir 2001
1. Introduksjon
2. Historie om fremveksten av grafteori
3. Grunnleggende definisjoner av grafteori
4. Grunnleggende teoremer for grafteori
5. Oppgaver om anvendelse av grafteori
6. Anvendelse av grafteori i et skolematematikkkurs
7. Anvendelse av grafteori på ulike felt innen vitenskap og teknologi
8. Nylige fremskritt innen grafteori
§1. HISTORIE OM UTSEENDEET AV GRAFTEORIEN.
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 [se. s. 41-42]:
"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 har vært i stand til å 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 det... Etter mye omtanke fant jeg en enkel regel, basert på et fullstendig overbevisende bevis, ved hjelp av hvilken det er mulig å umiddelbart avgjøre i alle problemer av denne typen om en slik omvei kan gjøres gjennom evt. antall broer plassert på noen måte eller ikke, slik at de kan representeres i følgende figur[Figur 1] , hvorpå EN betegner en øy, og B , C og D - deler av kontinentet atskilt fra hverandre av elvegrener. De syv broene er angitt med bokstaver en , b , c , d , e , f , g ".
(FIGUR 1.1)
Angående metoden han oppdaget for å løse problemer av denne typen, skrev Euler [se. s. 102-104]:
"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, adskilt av vann - slike , som ikke har noen annen overgang fra en til en annen bortsett fra gjennom en bro. I dette eksemplet er det fire slike seksjoner - EN , B , C , D . Den neste tingen å skille er om antallet 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 fører hver til resten, det vil si at antallet broer som fører til individuelle seksjoner er oddetall, og dette alene er nok til å løse problemet. Når dette er bestemt, bruker vi følgende regel: hvis antallet broer som fører til hver enkelt strekning var jevnt, ville den aktuelle omkjøringen vært mulig, og samtidig ville det være mulig å starte denne omkjøringen fra en hvilken som helst strekning . Hvis to av disse tallene var oddetall, for bare ett kan ikke være oddetall, kan også da overgangen finne sted, som foreskrevet, men bare begynnelsen av kretsen må absolutt tas fra en av de to seksjonene som oddetallet fører til broer. Hvis det til slutt var mer enn to seksjoner som et oddetall broer fører til, så er en slik bevegelse generelt 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. La oss for eksempel åpne en skolelærebok i matematikk redigert av N.Ya. Vilenkina for sjette klasse. I den, på side 98, under overskriften utvikling av oppmerksomhet og intelligens, vil vi finne et problem som er direkte relatert til det som Euler en gang løste.
Oppgave nr. 569. Det er sju øyer på innsjøen, som er forbundet med hverandre som vist i figur 1.2. Hvilken øy bør en båt ta reisende til slik at de kan krysse hver bro og bare én gang? Hvorfor kan ikke reisende transporteres til øya? EN ?
(FIGUR 1.2)
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 skal levere reisende til øya 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 øya EN .
Avslutningsvis merker vi oss at problemet med Königsberg-broene og lignende problemer, sammen med et sett med metoder for deres studier, utgjør en svært viktig gren av matematikken i praktiske termer, kalt grafteori. Det første arbeidet med grafer tilhørte L. Euler og dukket opp i 1736. Deretter arbeidet Koenig (1774-1833), Hamilton (1805-1865) og moderne matematikere C. Berge, O. Ore, A. Zykov med grafer.
§2. GRUNNLEGGENDE TEOREMER I GRAFTEORIEN
Grafteori, som nevnt ovenfor, er en matematisk disiplin skapt av matematikeres innsats, derfor inkluderer presentasjonen de nødvendige strenge definisjonene. Så la oss fortsette til en organisert introduksjon av de grunnleggende konseptene i denne teorien.
Definisjon 2.01. Telle er en samling av et begrenset antall punkter kalt topper graf, og parvise linjer som forbinder noen av disse toppunktene, kalt ribbeina eller buer kurve.
Denne definisjonen kan formuleres annerledes: telle kalles et ikke-tomt sett med punkter ( topper) og segmenter ( ribbeina), som begge ender tilhører et gitt sett med punkter (se fig. 2.1).
(FIGUR 2.1)
I det følgende vil vi betegne toppunktene i grafen med latinske bokstaver EN , B ,C ,D. Noen ganger vil grafen som helhet betegnes med én stor bokstav.
Definisjon 2.02. Toppunktene til en graf som ikke tilhører noen kant kalles isolert .
Definisjon 2.03. En graf som bare består av isolerte hjørner kalles null - telle .
Betegnelse: O " – en graf med hjørner som ikke har noen kanter (fig. 2.2).
(FIGUR 2.2)
Definisjon 2.04. En graf der hvert par av hjørner er forbundet med en kant kalles fullstendig .
Betegnelse: U " – graf som består av n toppunkter og kanter som forbinder alle mulige par av disse toppunktene. En slik graf kan representeres som n– en trekant der alle diagonaler er tegnet (fig. 2.3).
(FIGUR 2.3)
Definisjon 2.05. Grad topper er antall kanter som et toppunkt tilhører.
Betegnelse: s (EN) – toppunkt grad EN . For eksempel, i figur 2.1: s (EN)=2, s (B)=2, s (C)=2, s (D)=1, s (E)=1.
Definisjon 2.06. Tell, grader av alle k hvis toppunkter er identiske kalles homogen telle grader k .
Figur 2.4 og 2.5 viser homogene grafer av andre og tredje grad.
(FIGUR 2.4 og 2.5)
Definisjon 2.07. Supplement gitt kurve er en graf som består av alle kantene og deres ender som må legges til den originale grafen for å få en fullstendig graf.
Figur 2.6 viser den opprinnelige grafen G , bestående av fire hjørner og tre segmenter, og i figur 2.7 - komplementet til denne grafen - grafen G " .
(FIGUR 2.6 og 2.7)
Vi ser at i figur 2.5 er det ribber A.C. Og BD skjæres i et punkt som ikke er et toppunkt på grafen. Men det er tilfeller når en gitt graf må representeres på et plan på en slik måte at kantene bare krysser hverandre ved toppunktene (dette spørsmålet vil bli diskutert i detalj i avsnitt 5).
Definisjon 2.08. En graf som kan representeres på et plan på en slik måte at kantene bare skjærer hverandre ved hjørnene kalles flat .
For eksempel viser figur 2.8 en plan graf som er isomorf (lik) med grafen i figur 2.5. Vær imidlertid oppmerksom på at ikke hver graf er plan, selv om det motsatte er sant, det vil si at enhver plan graf kan representeres i vanlig form.
(FIGUR 2.8)
Definisjon 2.09. En polygon i en plan graf som ikke inneholder noen toppunkter eller kanter på grafen kalles kant .
Uformelt kan en graf betraktes som et sett med punkter og linjer som forbinder disse punktene, med eller uten piler.
Det første arbeidet med grafteori som en matematisk disiplin anses å være Eulers papir (1736), som vurderte problemet med Köningsberg-broene. Euler viste at det er umulig å omgå de syv bybroene og gå tilbake til utgangspunktet ved å krysse hver bro nøyaktig én gang. Grafteori fikk sin neste drivkraft nesten 100 år senere med utviklingen av forskning innen elektriske nettverk, krystallografi, organisk kjemi og andre vitenskaper.
Uten engang å merke det, møter vi grafer hele tiden. For eksempel er en graf et diagram over T-banelinjer. Prikkene på den representerer stasjoner, og linjene representerer togruter. Ved å forske på våre aner og spore den tilbake til en fjern stamfar, bygger vi et såkalt slektstre. Og dette treet er en graf.
Grafer fungerer som et praktisk middel for å beskrive forhold mellom objekter. Vi har tidligere brukt grafer som en måte å visuelt representere endelige binære relasjoner.
Men grafen brukes ikke bare som en illustrasjon. For eksempel, ved å vurdere en graf som viser et nettverk av veier mellom befolkede områder, kan du bestemme ruten fra punkt A til punkt B. Hvis det er flere slike ruter, vil du gjerne velge den optimale i en viss forstand, f.eks. den korteste eller den sikreste. For å løse utvalgsproblemet er det nødvendig å utføre visse beregninger på grafer. Når du løser slike problemer, er det praktisk å bruke algebraiske teknikker, og selve konseptet med en graf må formaliseres.
Grafteoretiske metoder er mye brukt i diskret matematikk. Det er umulig å klare seg uten dem når du analyserer og syntetiserer forskjellige diskrete omformere: funksjonelle blokker av datamaskiner, programvarepakker, etc.
For tiden dekker grafteori mye materiale og utvikler seg aktivt. Når vi presenterer det, vil vi begrense oss til kun en del av resultatene og legge hovedvekten på beskrivelsen og begrunnelsen av noen utbredte grafanalysealgoritmer som brukes i teorien om formelle språk.
Grunnleggende definisjoner
Grafer, som allerede nevnt i eksemplene, er en måte å "visualisere" forbindelser mellom visse objekter. Disse forbindelsene kan være "rettet", som for eksempel i et slektstre, eller "urettet" (et nettverk av toveis veier). I samsvar med dette er det i grafteori to hovedtyper grafer: rettet (eller rettet) og urettet.
Presentasjonsmetoder
Så langt har vi definert dirigerte og urettede grafer, som viser dem ved hjelp av tegninger. Du kan definere en graf som et par sett, etter definisjonen, men denne metoden er ganske tungvint og er av teoretisk interesse. Utviklingen av algoritmiske tilnærminger for å analysere egenskapene til grafer krever andre måter å beskrive grafer på som er mer egnet for praktiske beregninger, inkludert bruk av datamaskin. La oss se på de tre vanligste måtene å representere grafer på.
Trær
Definisjon 5.5. Et urettet tre er en sammenhengende og asyklisk urettet graf. Definisjon 5.6. Et rettet tre er en ikke-konturrettet graf der halvgraden til et hvilket som helst toppunkt ikke er større enn 1 og det er nøyaktig ett toppunkt, kalt roten til det rettede treet, hvis halve grad er 0.
Minst vektspennende tre
Følgende oppgave er kjent i grafteorien som Steiner-problemet: n poeng er gitt på et plan; du må koble dem med rette segmenter på en slik måte at den totale lengden på segmentene er minimal.
Metoder for systematisk å krysse grafens toppunkter
Viktige problemer i grafteori er problemene med global analyse av både urettede og rettede grafer. Disse oppgavene inkluderer for eksempel oppgaven med å finne sykluser eller konturer, beregne lengden på stier mellom par av hjørner, liste opp stier med visse egenskaper, etc. Global grafanalyse bør skilles fra lokal analyse, et eksempel på dette er problemet med å bestemme settene med forgjengere og etterfølgere til et fast toppunkt av en rettet graf.
Baneproblem i veide rettet grafer
Grafisk isomorfisme
For en rettet graf (V, E) kan settet E av buer betraktes som en graf av en binær direkte nåbarhetsrelasjon definert på settet med toppunkter. I en urettet graf (V, E) er settet E av kanter settet med uordnede par. For hvert uordnede par (u, v) ∈ E kan vi anta at toppunktene u og v er forbundet med en symmetrisk binær relasjon p, dvs. (u, v) ∈ р og (v, u) ∈ р.
Topologisk sortering
Definisjon 5.17. Et rettet nettverk (eller ganske enkelt et nettverk) er en konturløs rettet graf*. Siden nettverket er en konturløs graf, kan det vises at det er toppunkter (noder) i nettverket med null ut-grad, samt toppunkter (noder) med null i-grad. Førstnevnte kalles synker eller utganger av nettverket, og sistnevnte kalles kilder eller innganger til nettverket.
Elementer av syklomatikk
Når man diskuterte dybde-første søkealgoritmen i en urettet graf, ble spørsmålet om å søke etter de såkalte fundamentale syklusene til grafen vurdert. I dette tilfellet ble en fundamental syklus forstått som en syklus som inneholder nøyaktig en omvendt kant, og en en-til-en korrespondanse ble etablert mellom grunnleggende sykluser og omvendte kanter; fundamentale sykluser oppstår når en vilkårlig partisjon av alle kanter av en urettet graf inn i trær (som danner en viss maksimal kantskog av den originale grafen) og invers, og i det generelle tilfellet kan denne partisjonen spesifiseres helt uavhengig av dybde-først-søkealgoritmen. Dybde-først-søk er bare én måte å implementere en slik partisjon.
Grafteori er en gren av diskret matematikk som studerer objekter representert som individuelle elementer (vertekser) og sammenhenger mellom dem (buer, kanter).
Grafteori stammer fra løsningen av problemet med Königsberg-broene i 1736 av den berømte matematikeren Leonard Euler(1707-1783: født i Sveits, bodde og arbeidet i Russland).
Problem om Königsberg-broene.
Det er syv broer i den prøyssiske byen Königsberg ved Pregal-elven. Er det mulig å finne en turvei som krysser hver bro nøyaktig én gang og starter og slutter på samme sted?
En graf der det er en rute som starter og slutter ved samme toppunkt og passerer langs alle kantene på grafen nøyaktig én gang kallesEuler graf.
Sekvensen av hjørner (kanskje gjentatt) som den ønskede ruten går gjennom, så vel som selve ruten, kallesEuler syklus .
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. Dette problemet ble løst (det ble vist at det ikke er noen løsning) av Kuratovsky (1896 - 1979) i 1930.
Problemet med fire farger. Å dele et fly i områder som ikke krysser hverandre kalles med kort. Kartområder kalles tilstøtende hvis de har felles grense. Oppgaven er å fargelegge kartet på en slik måte at ikke to tilstøtende områder males med samme farge. Siden slutten av 1800-tallet har det vært kjent en hypotese om at fire farger er nok til dette. Hypotesen er ennå ikke bevist.
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 er utenfor omfanget av 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...
Dermed kan vi bare stole på programmeringsferdighetene til forfatterne og tro at de gjorde alt riktig.
Definisjon 7.1. Telle G= G(V, E) er en samling av to endelige sett: V – kalt mange hjørner og settet E av par av elementer fra V, dvs. EÍV´V, kalt mange kanter, hvis parene er uordnede, eller mange buer, hvis parene er bestilt.
I det første tilfellet, grafen G(V, E) kalt uorientert, i den andre – orientert.
EKSEMPEL. En graf med et sett med toppunkter V = (a,b,c) og et sett med kanter E =((a, b), (b, c))
EKSEMPEL. En graf med V = (a,b,c,d,e) og E = ((a, b), (a, e), (b, e), (b, d), (b, c) , (c, d)),
Hvis e=(v 1 ,v 2), еОЕ, så sier de at kanten er e kobler til toppunktene v 1 og v 2.
To toppunkter v 1,v 2 kalles ved siden av, hvis det er en kant som forbinder dem. I denne situasjonen kalles hvert av toppunktene hendelse tilsvarende kant .
To forskjellige ribber ved siden av, hvis de har et felles toppunkt. I denne situasjonen kalles hver av kantene tilfeldig tilsvarende toppunkt .
Antall grafhjørner G la oss betegne v, og antall kanter er e:
.
Den geometriske representasjonen av grafene er som følger:
1) toppunktet på grafen er et punkt i rommet (på planet);
2) en kant av en urettet graf – et segment;
3) en bue av en rettet graf – et rettet segment.
Definisjon 7.2. Hvis i kanten e=(v 1 ,v 2) forekommer v 1 =v 2, så kalles kanten e Løkke. Hvis en graf tillater løkker, kalles den graf med løkker eller pseudograf .
Hvis en graf tillater mer enn én kant mellom to hjørner, kalles den multigraf .
Hvis hvert toppunkt av en graf og/eller kant er merket, kalles en slik graf merket (eller lastet ). Bokstaver eller heltall brukes vanligvis som merker.
Definisjon 7.3. Kurve G (V , E ) kalt subgraf (eller del ) kurve G(V,E), Hvis V V, E E. Hvis V = V, Det G kalt spennende undergraf G.
Eksempel 7 . 1 . Gitt en urettet graf.
Definisjon 7.4. Grafen kalles fullstendig , Hvis noen de to hjørnene er forbundet med en kant. Komplett graf med n toppunkter er betegnet med K n .
Teller K 2 , TIL 3, TIL 4 og K 5 .
Definisjon 7.5. Kurve G=G(V, E) er kalt tofrøbladede , Hvis V kan representeres som en forening av usammenhengende sett, for eksempel V=ENB, så hver kant har formen ( v Jeg , v j), Hvor v Jeg EN Og v j B.
Hver kant forbinder et toppunkt fra A til et toppunkt fra B, men ingen to toppunkter fra A eller to toppunkter fra B er koblet sammen.
En todelt graf kalles komplett tofrøblad telle K m , n, Hvis EN inneholder m topper, B inneholder n hjørner og for hver v Jeg EN, v j B vi har ( v Jeg , v j)E.
Altså for alle v Jeg EN, Og v j B det er en kant som forbinder dem.
K 12 K 23 K 22 K 33
Eksempel 7 . 2 . Konstruer en komplett todelt graf K 2.4 og hele grafen K 4 .
Enhetsgrafn-dimensjonal kubeI n .
Toppunktene til grafen er n-dimensjonale binære sett. Kanter forbinder hjørner som er forskjellige i en koordinat.
Eksempel: 
Grafteori- en av de mest omfattende delene av diskret matematikk, mye brukt i å løse økonomiske og ledelsesproblemer, i programmering, kjemi, design og studier av elektriske kretser, kommunikasjon, psykologi, psykologi, sosiologi, lingvistikk og andre kunnskapsfelt. Grafteori studerer systematisk og konsekvent egenskapene til grafer, som kan sies å bestå av sett med punkter og sett med linjer som representerer sammenhengene mellom disse punktene. Grunnleggeren av grafteorien anses å være Leonhard Euler (1707-1882), som løste det da velkjente problemet med Königsberg-broene i 1736.
Grafer bygges for å vise relasjoner på sett. La for eksempel være et sett EN = {en1 , en 2 , ... en n)- mange mennesker, og hvert element vil vises som en prikk. En haug med B = {b1 , b 2 , ... b m)- mange forbindelser (rette linjer, buer, segmenter - det spiller ingen rolle ennå). På settet EN bekjentskapsforholdet mellom personer fra dette settet er gitt. Bygge en graf fra punkter og koblinger. Linker vil koble sammen par av mennesker som kjenner hverandre. Naturligvis kan antallet bekjentskaper til noen mennesker avvike fra antallet bekjentskaper til andre mennesker, og noen kjenner kanskje ikke noen (slike elementer vil være punkter som ikke er knyttet til noen andre). Så vi har en graf!
Det vi først kalte "punkter" skal kalles toppunktene til grafen, og det vi kalte "forbindelser" skal kalles kantene på grafen.
Grafteori tar ikke hensyn til settenes spesifikke natur EN Og B. Det er et stort antall svært forskjellige spesifikke problemer, når man løser hvilke man midlertidig kan glemme det spesifikke innholdet i sett og deres elementer. Denne spesifisiteten påvirker ikke på noen måte fremdriften for å løse problemet, uavhengig av vanskelighetsgraden! For eksempel når man skal avgjøre om det er mulig fra et punkt en kom til poenget e, bare beveger seg langs linjene som forbinder punktene, spiller det ingen rolle om vi har å gjøre med mennesker, byer, tall osv. Men når problemet er løst, får vi en løsning som er sann for alt innhold som ble modellert som en graf. Det er derfor ikke overraskende at grafteori er et av de mest populære verktøyene for å skape kunstig intelligens: tross alt kan kunstig intelligens diskutere spørsmål om kjærlighet, spørsmål om musikk eller sport, og spørsmål om å løse ulike problemer med en samtalepartner. , og gjør dette uten noen overgang (switching) , uten som en person ikke kan klare seg uten i slike tilfeller.
Og nå de strenge matematiske definisjonene av en graf.
Definisjon 1.Det kalles en graf et system av objekter av vilkårlig natur (vertekser) og lenker (kanter) som forbinder noen par av disse objektene.
Definisjon 2. La V– (ikke-tomt) sett med hjørner, elementer v∈V- topper. Kurve G = G(V) med mange hjørner V det er en viss familie av par av formen: e = (en, b) , Hvor en,b∈V , som indikerer hvilke toppunkter som forblir tilkoblet. Hvert par e = (en, b) - kanten av grafen. En haug med U- mange kanter e kurve. Topper en Og b– endepunkter på kanten e .
Grafer som en datastruktur. Den utbredte bruken av grafteori i informatikk og informasjonsteknologi skyldes tilføyelsen av konseptet med en graf som en datastruktur til definisjonene ovenfor. I informatikk og informasjonsteknologi er en graf definert som en ikke-lineær datastruktur. Hva er da en lineær datastruktur og hvordan skiller grafer seg fra dem? Lineære datastrukturer kjennetegnes ved at de forbinder elementer gjennom relasjoner av typen "enkle nabolag". Lineære datastrukturer er for eksempel arrays, tabeller, lister, køer, stabler, strenger. I motsetning til dette er ikke-lineære datastrukturer de der elementer er plassert på forskjellige nivåer i hierarkiet og er delt inn i tre typer: original, generert og lignende. Så en graf er en ikke-lineær datastruktur.
Ordet graf er av gresk opprinnelse, fra ordene "jeg skriver", "jeg beskriver". Fra begynnelsen av denne artikkelen vet vi nøyaktig hva grafen beskriver: den beskriver sammenhenger. Det vil si at enhver graf beskriver sammenhenger. Og omvendt: ethvert forhold kan beskrives som en graf.
Grunnleggende begreper i grafteori
Konseptet forekomst er også nødvendig når man utvikler algoritmer for å løse mange praktiske problemer med grafer. Du kan for eksempel gjøre deg kjent med programvareimplementeringen dybde-første traversering av grafen representert av insidensmatrisen. Ideen er enkel: du kan bare bevege deg gjennom hjørner forbundet med kanter. Og hvis noen verdier er tilordnet kantene ("skalaer", oftest i form av tall, kalles slike grafer vektet eller merket), kan komplekse anvendte problemer løses, hvorav noen er nevnt i siste avsnitt av denne leksjonen.
Klassiske problemer med grafteori og deres løsninger
Et av de første publiserte eksemplene på arbeid med grafteori og bruk av grafer er arbeidet med "Königsberg Bridges Problem" (1736), forfattet av den fremtredende 1700-tallsmatematikeren Leonhard Euler. Problemet inneholder en elv, øyer som vaskes av denne elven, og flere broer. Spørsmål om problemet: er det mulig, etter å ha forlatt et bestemt punkt, å krysse hver bro bare én gang og gå tilbake til utgangspunktet? (bilde under)
Problemet kan modelleres som følger: ett punkt er festet til hvert landområde, og to punkter er forbundet med en linje hvis og bare hvis de tilsvarende landområdene er forbundet med en bro (figur nedenfor, forbindelseslinjer er tegnet med stiplede linjer) . Dermed er grafen konstruert.
Eulers svar på problemspørsmålet er som følger. Hvis dette problemet hadde en positiv løsning, ville det i den resulterende grafen være en lukket bane som passerer langs kantene og inneholder hver kant bare én gang. Hvis en slik bane eksisterer, må hvert toppunkt bare ha et partall av kanter. Men den resulterende grafen har toppunkter som har et oddetall kanter. Derfor har ikke problemet en positiv løsning.
I følge etablert tradisjon er en Eulersk graf en graf der det er mulig å krysse alle toppunktene og samtidig krysse én kant bare én gang. I den må hvert toppunkt bare ha et jevnt antall kanter. Et problem med middels vanskelighetsgrad på Euler-grafer er i materialet "Grunnleggende grafer".
I 1847 utviklet Kirchhoff teorien om trær for å løse et samtidig system av lineære algebraiske ligninger, slik at man kunne finne verdien av strømmen i hver leder (bue) og i hver krets i en elektrisk krets. Abstrahere fra elektriske kretser og kretser som inneholder motstander, kondensatorer, induktanser, etc., vurderte han de tilsvarende kombinatoriske strukturene som bare inneholder toppunkter og forbindelser (kanter eller buer), og for tilkoblinger er det ikke nødvendig å ta hensyn til hvilke typer elektriske elementer de tilsvarer. Dermed erstattet Kirchhoff hver elektrisk krets med en tilsvarende graf og viste at for å løse et ligningssystem er det ikke nødvendig å vurdere hver syklus av den elektriske kretsgrafen separat.
Cayley oppdaget i 1858, mens han jobbet med rent praktiske problemer innen organisk kjemi, en viktig klasse grafer kalt trær. Han forsøkte å liste isomerene til mettede hydrokarboner, med et gitt antall karbonatomer. Cayley formulerte først problemet abstrakt: finn antallet på alle trær med s toppunkter, som hver har toppunkter med grader 1 og 4. Han klarte ikke umiddelbart å løse dette problemet, og han begynte å endre formuleringen på en slik måte at et nytt oppregningsproblem kunne løses:
- rotede trær (hvor en av toppunktene er valgt);
- alle trær;
- trær hvis toppunktgrader ikke overstiger 4;
- trær hvis toppunktsgrader er 1 og 4 (utsagn om et problem fra kjemi).
Tegn problemer for å forsterke grunnleggende konsepter
Eksempel 1. La EN- sett med tall 1, 2, 3: EN= (1, 2, 3). Konstruer en graf for å vise forholdet "
Løsning. Det er klart at tallene 1, 2, 3 skal representeres som toppunktene i en graf. Deretter må hvert par av hjørner være forbundet med en kant. Ved å løse dette problemet kom vi til slike grunnleggende konsepter for grafteori som rettede og urettede grafer. Urettede grafer er de hvis kanter ikke har noen retning. Eller, som de sier enda oftere, rekkefølgen på de to endene av en kant er ikke signifikant. Faktisk trenger ikke grafen som ble konstruert helt i begynnelsen av denne leksjonen og som representerer bekjentskapsforholdet mellom mennesker, kantretninger, siden det kan hevdes at "person nummer 1" er kjent med "person nummer 2" i samme grad som "person nummer 2" med "person nummer 1". I vårt nåværende eksempel er ett tall mindre enn et annet, men ikke omvendt. Derfor må den tilsvarende kanten av grafen ha en retning som indikerer hvilket tall som er mindre enn det andre. Det vil si at rekkefølgen på kantendene er betydelig. En slik graf (med kanter som har en retning) kalles en rettet graf eller digraf.
Altså i vår mengde EN nummer 1 er mindre enn nummer 2 og nummer 3, og nummer 2 er mindre enn nummer 3. Vi viser dette faktum ved kanter som har en retning, som vises med piler. Vi får følgende graf:
Eksempel 2. La EN- sett med tall 2, 4, 6, 14: EN= (2, 4, 6, 14) . Lag en graf for å vise "delelig med"-relasjonen på dette settet.
Løsning. I dette eksemplet vil noen av kantene ha en retning, og noen vil ikke, det vil si at vi bygger blandet graf. La oss liste opp relasjonene på settet: 4 er delelig med 2, 6 er delelig med 2, 14 er delelig med 2, og hvert tall fra dette settet er delelig med seg selv. Denne relasjonen, det vil si når et tall er delbart med seg selv, vil vises i form av kanter som forbinder toppunktet med seg selv. Slike kanter kalles løkker. I dette tilfellet er det ikke nødvendig å gi retning til løkken. Så i vårt eksempel er det tre vanlige rettede kanter og fire løkker. Vi får følgende graf:
Eksempel 3. La gitte sett EN= (α, β, γ) og B= (a, b, c). Konstruer en graf for å vise forholdet "kartesisk produkt av sett."
Løsning. Som kjent fra definisjonen Kartesisk produkt av sett, er det ingen ordnede sett med elementer av samme sett. Det vil si at i vårt eksempel kan du ikke kombinere greske bokstaver med gresk og latin med latin. Dette faktum vises som todelt graf, det vil si en der toppunktene er delt i to deler slik at toppunktene som hører til samme del ikke er forbundet med hverandre. Vi får følgende graf:
Eksempel 4. Eiendomsmeglingen sysselsetter lederne Igor, Sergey og Peter. Objekter O1, O2, O3, O4, O5, O6, O7, O8 er betjent. Konstruer en graf for å vise relasjonene "Igor jobber med objektene O4, O7", "Sergey jobber med objektene O1, O2, O3, O5, O6", "Peter jobber med objektene O8".
Løsning. Grafen som viser disse relasjonene vil også være todelt, siden lederen ikke jobber med lederen og objektet ikke fungerer med objektet. Men i motsetning til det forrige eksemplet, vil grafen bli rettet. Faktisk, for eksempel, fungerer Igor med objekt O4, men objekt O4 fungerer ikke med Igor. Ofte, når en slik egenskap ved relasjoner er åpenbar, kan behovet for å gi retning til kantene virke som «matematisk dumhet». Men likevel, og dette følger av matematikkens strenge natur, hvis forholdet er ensidig, er det nødvendig å gi retninger til kantene. I relasjonelle applikasjoner lønner denne strengheten seg, for eksempel i programmer designet for planlegging, hvor også grafer brukes og ruten langs topper og kanter må passere strengt i en gitt retning. Så vi får følgende rettet todelt graf:
Og igjen til eksempler med tall.
Eksempel 5. La et sett bli gitt C = {2, 3, 5, 6, 15, 18} . Konstruer en graf som implementerer en relasjon som definerer alle tallpar en Og b fra mange C, der, når vi deler det andre elementet med det første, får vi en kvotient som er et heltall større enn 1.
Løsning. Grafen som viser disse relasjonene vil være orientert, siden betingelsen inneholder en omtale av det andre og det første elementet, det vil si at kanten vil bli rettet fra det første elementet til det andre. Av dette er det klart hvilket element som er det første og hvilket det andre. La oss også legge til litt terminologi: orienterte kanter kalles vanligvis buer. Det vil være 7 buer i grafen vår: e1 = (3, 15) , e2 = (3, 18) , e3 = (5, 15) , e4 = (3, 6) , e5 = (2, 18) , e6 = (6, 18) , e7 = (2, 6) . I dette eksemplet er kantene (buene) på grafen ganske enkelt nummerert, men serienummer er ikke det eneste som kan tildeles en bue. Buen kan også tildeles skalaer som betyr for eksempel kostnadene ved å sende last fra ett punkt til et annet. Men vi vil bli kjent med buevekter senere og mer detaljert. Så vi får følgende rettet graf:
Som vi allerede vet fra den teoretiske innledende delen, tar ikke grafteori hensyn til mengdenes spesifikke natur og ved hjelp av samme graf er det mulig å definere relasjoner på mengder med svært forskjellig innhold. Det vil si at nettopp dette innholdet kan abstraheres fra når man modellerer et problem. La oss gå videre til eksempler som illustrerer denne bemerkelsesverdige egenskapen til grafteori.
Eksempel 6. På en brikke av et sjakkbrett som måler 3 X 3, er to hvite riddere og to svarte riddere plassert som vist i figuren under.
Er det mulig å flytte ridderne til tilstanden vist i følgende figur, uten å glemme at to brikker ikke kan være på samme rute?
Løsning. I den konstruerte grafen vil par av hjørner være forbundet med "riddertrekk"-relasjonen. Det vil si at en toppunkt er den som ridderen dro fra, og den andre er den den kom til, og den mellomliggende cellen til bokstaven "r" vil være utenfor dette forholdet. Vi får følgende graf:
Og likevel viste designet seg å være tungvint. Cellene på et sjakkbrett er synlige i det, og mange av kantene på grafen krysser hverandre. Er det mulig å abstrahere fra det fysiske utseendet til sjakkbrettet og forestille seg forholdet enklere? Det viser seg at det er mulig. I den nye grafen vil nabopunktene være de som er forbundet med forholdet «riddertrekk», og ikke de som ligger ved siden av sjakkbrettet (figuren nedenfor).
Nå er det lett å se at svaret på spørsmålet om dette problemet er negativt. I den opprinnelige tilstanden er det ingen svart ridder mellom to hvite riddere, men i den endelige tilstanden må det være denne svarte ridderen. Kantene på grafen er plassert slik at to tilstøtende riddere ikke kan hoppe over hverandre.
Eksempel 7. Problemet med ulven, geita og kålen. På den ene bredden av elven er det en mann (H), en båt, en ulv (V), en geit (Kz) og en kål (Kp). En person og ikke mer enn en av de transporterte gjenstandene kan være i båten samtidig. En person må transportere alle gjenstander til den andre siden, observere tilstanden: en ulv må ikke stå uten tilsyn med en geit og en geit med kål.
Løsning. I den konstruerte grafen er toppunktene konfigurasjoner, og kantene er forholdet "forbindelse med en båttur" mellom konfigurasjonene. Konfigurasjon refererer til arrangementet av objekter på den opprinnelige banken og på den motsatte bredden. Hver konfigurasjon vises som ( EN|B) , Hvor EN- gjenstander som ligger på den opprinnelige kysten, og B- gjenstander plassert på motsatt bredd. Den første konfigurasjonen er derfor - (PMCpKz| ) . For eksempel, etter å ha transportert en geit til den andre siden, vil konfigurasjonen være (VKp|ChKz) . Den endelige konfigurasjonen er alltid ( |PMCpKz) . Nå kan vi bygge en graf, allerede ved å vite hva toppunktene og kantene betyr:
La oss plassere toppunktene på grafen slik at kantene ikke krysser hverandre, og nabopunktene er de som er forbundet med et forhold på grafen. Da vil det være mye lettere å se forholdene (for å forstørre bildet, venstreklikk på det):
Som vi kan se, er det to forskjellige sammenhengende ruter fra den første konfigurasjonen til den endelige. Derfor har problemet to forskjellige løsninger (og begge er riktige).
Grafteori og de viktigste moderne anvendte problemene
Basert på grafteori er det utviklet metoder for å løse anvendte problemer der svært komplekse systemer er modellert i form av grafer. I disse modellene inneholder noder individuelle komponenter, og kanter representerer forbindelser mellom komponenter. Vanligvis brukes vektede grafer for å modellere transportnettverk, køsystemer og nettverksplanlegging. Vi har allerede snakket om dem; dette er grafer der vekter er tildelt buene.
Tregrafer brukes for eksempel til å konstruere beslutningstrær(tjener til risikoanalyse, analyse av mulige gevinster og tap under usikkerhetsforhold). Ved hjelp av grafteori utviklet og andre tallrike matematiske modellerå løse problemer innen bestemte fagområder.
Grafer og flytproblemet
Formulering av problemet. Det er et system av vannrør, representert ved grafen i figuren nedenfor.
Hver bue i grafen representerer et rør. Tallene over buene (skalaene) er rørkapasiteten. Noder er steder hvor rør kobles sammen. Vann strømmer gjennom rør i bare én retning. Knute S- vannkilde, node T- lager. Det er nødvendig for å maksimere volumet av vann som strømmer fra kilde til avløp.
For å løse strømningsproblemet kan du bruke Ford-Fulkerson-metoden. Ideen med metoden: søket etter maksimal flyt utføres i trinn. I begynnelsen av algoritmen settes flyten til null. Ved hvert påfølgende trinn øker verdien av strømmen, og det søkes etter en komplementær vei som den ekstra strømmen kommer gjennom. Disse trinnene gjentas så lenge det finnes flere baner. Problemet har blitt brukt i forskjellige distribuerte systemer: strømforsyningssystem, kommunikasjonsnettverk, jernbanesystem og andre.
Grafer og nettverksplanlegging
I planleggingsproblemer med komplekse prosesser som består av mange jobber, hvorav noen utføres parallelt og noen sekvensielt, har vektede grafer, kjent som PERT-nettverk, blitt mye brukt.
PERT - Program (Project) Evaluation and Review Technique - en teknikk for å evaluere og analysere programmer (prosjekter), som brukes i prosjektledelse.
PERT-nettverket er en vektet asyklisk rettet graf der hver bue representerer en jobb (handling, operasjon), og vekten av buen er tiden som kreves for å fullføre den.
Hvis det er buer i nettverket ( en, b) Og ( b, c), deretter verket representert av buen ( en, b) må fullføres før arbeidet representert av buen ( b, c). Hvert toppunkt ( vJeg) representerer tidspunktet for alt arbeid, definert av buer som slutter ved et toppunkt ( vJeg).
I en spalte som dette:
- ett toppunkt, som ikke har noen forgjengere, bestemmer starttidspunktet for arbeidet;
- ett toppunkt, som ikke har noen følgere, tilsvarer tidspunktet når settet med arbeider er fullført.
Banen med maksimal lengde mellom disse toppunktene i grafen (fra begynnelsen til slutten av arbeidsprosessen) kalles den kritiske banen. For å redusere tiden som kreves for å fullføre hele komplekset av arbeid, er det nødvendig å finne arbeid som ligger på den kritiske veien og redusere varigheten ved for eksempel å tiltrekke seg flere utøvere, mekanismer og nye teknologier.
Hele blokken "Graph Theory"
Grafteori er en gren av matematikk som brukes innen informatikk og programmering, økonomi, logistikk og kjemi.
Hva er en graf
Grafiske diagrammer brukes ofte for å beskrive strukturen til systemene. Elementer i dem er representert av sirkler, prikker, firkanter, etc., og forbindelser mellom elementer er representert med linjer eller piler. I dette tilfellet er verken hvordan elementene er avbildet eller lengden eller formen på linjene viktig - bare hvilke elementer som er koblet sammen, betyr noe. Så en graf er et par av formen (A, M), der A er et begrenset sett med toppunkter, og M er et sett med kanter - linjer som forbinder noen toppunkter.
Grunnleggende begreper i grafteori
En orientert graf eller digraf (se figuren nedenfor) har orienterte kanter, kalt buer, og avbildet med piler. En bue kan betegnes med et ordnet par hjørner som den forbinder, en start og en slutt.
En urettet graf (se figuren nedenfor) har kanter som er tegnet som linjer uten orientering. Følgelig er paret av toppunkter forbundet med en kant uordnet. Begge disse toppunktene er endene av kanten.
Hvis toppunktene a og b er endene av en kant (eller begynnelsen og slutten av en bue) av grafen, så sies toppunktene a og b å falle inn i denne kanten (buen), og kanten (buen) er også hendelse til hjørnene a og b. Hvis toppunktene a og b er endene på en kant, kalles de (a og b) tilstøtende.
Oftest vurderer vi grafer hvis kanter er av én type - enten de er rettet eller ikke.
Hvis kanter har samme begynnelse og slutt, kalles de flere kanter, og grafen de er til stede i kalles en multigraf.
Grafteori bruker også begrepet en "løkke" - en kant som går ut og går inn i samme toppunkt. En graf som har løkker kalles en pseudograf.
De vanligste er urettede grafer, som ikke har flere kanter og ingen løkker. Slike grafer kalles ordinære. De har ikke flere kanter, så vi kan identifisere en kant og det tilsvarende paret med hjørner.
Hvert toppunkt i digrafen er preget av:
- Halv grad av utfall. Dette er antallet buer som kommer ut av den.
- Halv grad av tilnærming. Dette er antallet buer som kommer inn i et gitt toppunkt.
Summen av halvgradene av oppføringen av en digraf, så vel som summen av halvgradene av utfallet, er lik det totale antallet buer i grafen.
I en urettet graf er hvert toppunkt preget av graden av toppunktet. Dette er antallet kanter som faller inn i et toppunkt. Den totale summen av gradene av toppunktene til grafen er antall kanter multiplisert med to: hver kant vil bidra med et bidrag som er lik to.
Et toppunkt med grad 0 kalles isolert.
Et hengende toppunkt er et toppunkt med grad 1.
Grafteori kaller en tom graf en der det ikke er noen kanter. En komplett graf er en vanlig graf der 2 hjørner er tilstøtende.
Vektede grafer er grafer hvis toppunkter eller kanter (buer), eller både toppunkter og kanter (buer) på en gang, er tildelt bestemte tall. De kalles vekter. Den andre figuren viser en urettet graf hvis kanter er vektet.
Grafer: isomorfisme
Begrepet isomorfisme brukes i matematikk. Spesielt definerer grafteori det som følger: to grafer U og V er isomorfe hvis det i disse grafene er en bijeksjon mellom settene av deres toppunkter: hver 2 toppunkt i grafen U er forbundet med en kant hvis og bare hvis i graf V de samme er forbundet med en kant toppunkter (som kan ha forskjellige navn). Figuren nedenfor viser to isomorfe grafer der bijeksjonen beskrevet ovenfor eksisterer mellom toppunktene farget i de samme fargene i både den første og andre grafen.
Stier og sykluser
En bane i en urettet eller rettet graf er en sekvens av kanter, der hver neste begynner ved toppunktet der den forrige slutter. En enkel bane er en der alle hjørnene, unntatt kanskje starten og slutten, og kantene er forskjellige. En syklus i en digraf er en bane hvis start- og sluttpunkt faller sammen og som inkluderer minst én kant. En syklus i en urettet graf er en bane som inneholder minst tre distinkte kanter. I den andre figuren er syklusen for eksempel banen (3, 1), (6, 3), (1, 6).
Grafteori i programmering brukes til å konstruere grafdiagrammer av algoritmer.