B - P + G = 1, (*)

där B är det totala antalet hörn, P är det totala antalet kanter, G är antalet polygoner (ytor).

Bevis. Låt oss bevisa att likheten inte förändras om en diagonal ritas i någon polygon av en given partition (Fig. 2, a).

a) b)

Fig.2

Efter att ha ritat en sådan diagonal kommer den nya partitionen att ha B-hörn, P+1-kanter, och antalet polygoner kommer att öka med en. Därför har vi

B - (P + 1) + (G+1) = B – P + G.

Med den här egenskapen ritar vi diagonaler som delar upp de inkommande polygonerna i trianglar, och för den resulterande partitionen visar vi genomförbarheten av relationen.

För att göra detta kommer vi sekventiellt att ta bort yttre kanter, vilket minskar antalet trianglar. I det här fallet är två fall möjliga:

för att ta bort triangel ABC måste du ta bort två kanter, i vårt fall AB och BC;

För att ta bort triangel MKN måste du ta bort ena kanten, i vårt fall MN.

I båda fallen kommer jämställdheten inte att förändras. Till exempel, i det första fallet, efter att ha tagit bort triangeln, kommer grafen att bestå av B-1 hörn, P-2 kanter och G-1 polygon:

(B - 1) - (P + 2) + (G -1) = B – P + G.

Att ta bort en triangel förändrar alltså inte likheten.

Om vi ​​fortsätter med denna process att ta bort trianglar kommer vi så småningom fram till en partition som består av en enda triangel. För en sådan partition B = 3, P = 3, G = 1 och därför,

B - P + G = 1.

Det betyder att likheten även gäller för den ursprungliga partitionen, varifrån vi slutligen får fram att relationen är giltig för denna partition av polygonen.

Observera att Eulers relation inte beror på formen på polygonerna. Polygoner kan deformeras, förstoras, förminskas eller till och med kröka sina sidor, så länge det inte finns några luckor i sidorna. Eulers relation kommer inte att förändras.

Låt oss nu gå vidare till att lösa problemet med tre hus och tre brunnar.

Lösning . Låt oss anta att detta kan göras. Låt oss markera husen med punkterna D1, D2, D3 och brunnarna med punkterna K1, K2, K3 (Fig. 1). Vi kopplar ihop varje huspunkt med varje brunnspunkt. Vi får nio kanter som inte skär varandra i par.

Dessa kanter bildar en polygon på planet, uppdelad i mindre polygoner. Därför måste Euler-relationen B - P + G = 1 vara uppfylld för denna partition.

Låt oss lägga till ytterligare ett ansikte till de övervägda ytorna - den yttre delen av planet i förhållande till polygonen. Då kommer Euler-relationen att ha formen B - P + G = 2, med B = 6 och P = 9.

Därför är Г = 5. Var och en av de fem ytorna har minst fyra kanter, eftersom, enligt problemets villkor, ingen av vägarna direkt ska ansluta två hus eller två brunnar. Eftersom varje kant ligger på exakt två ytor måste antalet kanter vara minst (5 4)/2 = 10, vilket motsäger villkoret att deras antal är 9.

Den resulterande motsägelsen visar att svaret på problemet är negativt - det är omöjligt att dra icke-korsande stigar från varje hus till varje by

Grafteori i kemi

Tillämpning av grafteori för konstruktion och analys av olika klasser av kemiska och kemisk-teknologiska grafer, som även kallas topologi, modeller, d.v.s. modeller som endast tar hänsyn till arten av kopplingarna mellan hörnen. Bågarna (kanterna) och hörn av dessa grafer återspeglar kemiska och kemisk-teknologiska koncept, fenomen, processer eller objekt och följaktligen kvalitativa och kvantitativa samband eller vissa samband mellan dem.

Teoretiska problem. Kemiska grafer gör det möjligt att förutsäga kemiska transformationer, förklara essensen och systematisera några grundläggande begrepp inom kemi: struktur, konfiguration, bekräftelser, kvantmekaniska och statistisk-mekaniska interaktioner mellan molekyler, isomerism, etc. Kemiska grafer inkluderar molekylära, bipartita och signalgrafer av kinetiska reaktionsekvationer. Molekylära grafer, som används i stereokemi och strukturell topologi, kemi av kluster, polymerer, etc., är oriktade grafer som visar strukturen hos molekyler. Topparna och kanterna på dessa grafer motsvarar motsvarande atomer och kemiska bindningar mellan dem.

I stereokemi org. c-c de vanligaste är molekylära träd - spänner över träd av molekylära grafer som bara innehåller alla hörn som motsvarar atomer. Att sammanställa uppsättningar av molekylära träd och fastställa deras isomorfism gör det möjligt att bestämma molekylära strukturer och hitta det totala antalet isomerer av alkaner. alkener och alkyner. Molekylära grafer gör det möjligt att reducera problem relaterade till kodning, nomenklatur och strukturella egenskaper (förgrening, cyklicitet, etc.) av molekyler av olika föreningar till analys och jämförelse av rent matematiska egenskaper och egenskaper hos molekylära grafer och deras träd, samt deras motsvarande matriser. För att identifiera antalet korrelationer mellan molekylers struktur och föreningars fysikalisk-kemiska (inklusive farmakologiska) egenskaper har mer än 20 så kallade sådana utvecklats. Topologiska index för molekyler (Wiener, Balaban, Hosoya, Plata, Randic, etc.), som bestäms med hjälp av matriser och numeriska egenskaper hos molekylära träd. Till exempel, Wienerindex W = (m3 + m)/6, där m är antalet hörn som motsvarar C-atomer, korrelerar med molekylära volymer och brytningar, bildningsentalpier, viskositet, ytspänning, kromatografiska konstanter för föreningar, oktan. antal kolväten och till och med fysiologi. drogernas aktivitet. Viktiga parametrar för molekylära grafer som används för att bestämma de tautomera formerna av en given substans och deras reaktivitet, såväl som i klassificeringen av aminosyror, nukleinsyror, kolhydrater och andra komplexa naturliga föreningar, är den genomsnittliga och totala (H) informationskapaciteten. Analys av molekylära grafer av polymerer, vars hörn motsvarar monomerenheter, och kanterna motsvarar kemiska bindningar mellan dem, gör det möjligt att förklara till exempel effekterna av utesluten volym som leder till kvaliteter. förändringar i de förutsagda egenskaperna hos polymerer. Med hjälp av Graph Theory och principerna för artificiell intelligens har mjukvara för informationshämtningssystem inom kemi, samt automatiserade system för identifiering av molekylära strukturer och rationell planering av organisk syntes, utvecklats. För den praktiska implementeringen på en dator av operationer för att välja rationella kemiska vägar. transformationer baserade på retrosyntetiska och syntoniska principer använder grenade sökgrafer på flera nivåer för lösningsalternativ, vars hörn motsvarar de molekylära graferna för reagenser och produkter, och bågarna visar transformationer.

För att lösa flerdimensionella problem med analys och optimering av kemiska tekniska system (CTS) används följande kemiska tekniska grafer: flödes-, informationsflödes-, signal- och tillförlitlighetsgrafer. För studier i kemi. Fysiken för störningar i system som består av ett stort antal partiklar använder den sk. Feynman-diagram är grafer, vars hörn motsvarar de elementära interaktionerna mellan fysiska partiklar, kanterna på deras vägar efter kollisioner. I synnerhet gör dessa grafer det möjligt att studera mekanismerna för oscillerande reaktioner och bestämma stabiliteten hos reaktionssystem. Materialflödesdiagram visar förändringar i kemikalieflödet i kemiska system. Termiska flödesdiagram visar värmebalanser i CTS; kurvornas hörn motsvarar enheter där värmeförbrukningen av fysiska flöden förändras, och dessutom till källorna och sänkorna för termisk energi i systemet; bågar motsvarar fysiska och fiktiva (fysikalisk-kemisk energiomvandling i enheter) värmeflöden, och bågarnas vikter är lika med flödenas entalpier. Material- och termiska grafer används för att sammanställa program för automatiserad utveckling av algoritmer för att lösa ekvationssystem för material- och värmebalanser i komplexa kemiska system. Informationsflödesgrafer visar den logiska informationsstrukturen för system av matematiska ekvationer. XTS-modeller; används för att utveckla optimala algoritmer för att beräkna dessa system. En tvådelad informationsgraf är en oriktad eller riktad graf vars hörn motsvarar respektive. ekvationerna fl -f6 och variablerna q1 – V, och grenarna speglar deras förhållande. Informationsgraf – en digraf som visar ordningen för att lösa ekvationer; toppen av grafen motsvarar dessa ekvationer, källor och mottagare av XTS-information, och grenarna motsvarar information. variabler. Signalgrafer motsvarar linjära ekvationssystem av matematiska modeller av kemiska tekniska processer och system. Tillförlitlighetsgrafer används för att beräkna olika tillförlitlighetsindikatorer X.

Litteratur som används:

1.Berge K., T. g. och dess tillämpning, översättning från franska, M., 1962;

2. Kemeny J., Snell J., Thompson J., Introduction to Finite Mathematics, övers. från engelska, 2:a uppl., M., 1963;

3.Ope O., Grafer och deras tillämpning, övers. från English, M., 1965;

4. Belykh O.V., Belyaev E.V., Possibilities of use technology in sociology, i: Man and Society, vol. 1, [L.], 1966;

5. Kvantitativa metoder i sociologisk forskning, M., 1966; Belyaev E.V., Problems of sociological measurements, "VF", 1967, nr 7; Bavelas. Kommunikationsmönster i uppgiftsorienterade grupper, i boken. Lerner D., Lass well H., Political sciences, Stanford, 1951;

KOMMUNAL SJÄLVSTÄNDIG UTBILDNINGSINSTITUTION GYMNASIESKOLA Nr 2

Beredd

Legkokonets Vladislav, elev i klass 10A

Praktisk tillämpning av grafteori

Handledare

L.I. Noskova, matematiklärare

Konst Bryukhovetskaya

2011

1.Inledning……………………………………………………………………………………………………………….………….3

2. Historien om framväxten av grafteorin……………………………………………….………..4

3. Grundläggande definitioner och satser för grafteorin………………………………….………6

4. Problem lösta med hjälp av grafer…………………………………..………………………..8

4.1 Kända problem……………………………………….………………………...8

4.2 Flera intressanta problem………………………………….…………………..9

5. Tillämpning av grafer inom olika områden av människors liv…………………………………...11

6. Lösa problem………………………………………………………………………………...12

7. Slutsats……………………….………………………………………………………………………….13

8. Lista över referenser………….………………………………………………………………………………14

9.Bilaga……………………………………………………………………………………………….…………15

Introduktion

Född från att lösa pussel och underhållande spel, har grafteori nu blivit ett enkelt, tillgängligt och kraftfullt verktyg för att lösa frågor relaterade till ett brett spektrum av problem. Grafer är bokstavligen allestädes närvarande. I form av grafer kan man till exempel tolka vägkartor och elektriska kretsar, geografiska kartor och molekyler av kemiska föreningar, samband mellan människor och grupper av människor. Under de senaste fyra decennierna har grafteori blivit en av matematikens snabbast utvecklande grenar. Detta drivs av kraven från ett snabbt växande applikationsområde. Det används i designen av integrerade kretsar och styrkretsar, i studiet av automater, logiska kretsar, programblockdiagram, inom ekonomi och statistik, kemi och biologi, i schemaläggningsteori. Det är därför relevansÄmnet bestäms, å ena sidan, av populariteten för grafer och relaterade forskningsmetoder, och å andra sidan, ett outvecklat, holistiskt system för dess implementering.

Att lösa många problem i livet kräver långa beräkningar, och ibland ger inte ens dessa beräkningar framgång. Detta är vad forskningsproblem. Frågan uppstår: är det möjligt att hitta en enkel, rationell, kort och elegant lösning för att lösa dem. Är problemlösning lättare om du använder grafer? Detta bestämde ämnet för min forskning: "Praktisk tillämpning av grafteori"

Ändamål Forskningen gick ut på att använda grafer för att lära sig hur man snabbt löser praktiska problem.

Forskningshypotes. Grafmetoden är mycket viktig och används flitigt inom olika områden av vetenskap och mänsklig aktivitet.

Forskningsmål:

1. Studera litteratur och Internetresurser om denna fråga.

2. Kontrollera grafmetodens effektivitet för att lösa praktiska problem.

3. Dra en slutsats.

Studiens praktiska betydelseär att resultaten utan tvekan kommer att väcka många människors intresse. Har ingen av er försökt bygga ert släktträd? Hur gör man detta korrekt? Chefen för ett transportföretag måste sannolikt lösa problemet med mer lönsam användning av transporter vid transport av varor från en destination till flera bosättningar. Varje skolbarn har stött på logiska transfusionsproblem. Det visar sig att de enkelt kan lösas med hjälp av grafer.

Följande metoder används i arbetet: observation, sökning, urval, analys.

Grafteorins historia

Grundaren av grafteorin anses vara matematikern Leonhard Euler (1707-1783). Historien om denna teori kan spåras genom korrespondensen från den store vetenskapsmannen. Här är en översättning av den latinska texten, som är hämtad från Eulers brev till den italienske matematikern och ingenjören Marinoni, skickat från St. Petersburg den 13 mars 1736.

”Jag fick en gång ett problem om en ö som ligger i staden Königsberg och omgiven av en flod med sju broar över den.

[Bilaga Fig.1] Frågan är om någon kan gå runt dem kontinuerligt och bara passera en gång över varje bro. Och så fick jag beskedet att ingen ännu hade kunnat göra detta, men ingen hade bevisat att det var omöjligt. Denna fråga, även om den var trivial, föreföll mig dock värd att uppmärksammas eftersom varken geometri, algebra eller kombinatorisk konst är tillräckliga för att lösa den. Efter mycket funderande hittade jag en enkel regel, baserad på ett fullständigt övertygande bevis, med vars hjälp det i alla problem av detta slag är möjligt att omedelbart avgöra om en sådan omväg kan göras genom valfritt antal och hur många broar som helst. eller inte. Koenigsberg-broarna är placerade på ett sådant sätt att de kan representeras i följande figur [Bilaga Fig.2], där A betecknar en ö, och B, C och D - delar av kontinenten separerade från varandra av flodgrenar

Angående metoden han upptäckte för att lösa problem av detta slag, skrev Euler:

"Denna lösning, till sin natur, har tydligen lite med matematik att göra, och jag förstår inte varför man ska förvänta sig den här lösningen från en matematiker snarare än från någon annan person, för detta beslut stöds enbart av resonemang, och det finns ingen behöver involvera för att hitta den här lösningen, det finns några lagar som är inneboende i matematik. Så jag vet inte hur det visar sig att frågor som har väldigt lite med matematik att göra är mer benägna att lösas av matematiker än av andra.

Så är det möjligt att ta sig runt Königsbergsbroarna genom att bara passera en gång över var och en av dessa broar? För att hitta svaret, låt oss fortsätta Eulers brev till Marinoni:

"Frågan är att avgöra om det är möjligt att kringgå alla dessa sju broar, passera genom var och en endast en gång eller inte. Min regel leder till följande lösning på denna fråga. Först och främst måste du titta på hur många områden det finns är, åtskilda av vatten - sådana , som inte har någon annan övergång från en till en annan, utom genom en bro I det här exemplet finns det fyra sådana sektioner - A, B, C, D. Därefter måste du särskilja om antalet. av broar som leder till dessa individuella sektioner är jämnt eller udda Så i vårt fall leder fem broar till sektion A, och tre broar leder vardera till resten, dvs. antalet broar som leder till individuella sektioner är udda, och bara detta är. tillräckligt för att lösa problemet När detta är fastställt, tillämpar vi följande regel: om antalet broar som leder till varje enskild sektion var jämnt, skulle den aktuella omvägen vara möjlig, och samtidigt skulle det vara möjligt. starta denna omväg från vilken sektion som helst Om två av dessa nummer var udda, eftersom endast ett inte kan vara udda, så kan övergången slutföras, som föreskrivet, men endast början av omvägen måste säkert tas från. en av de två sektionerna som ett udda antal broar leder till. Om det slutligen fanns mer än två sektioner till vilka ett udda antal broar leder, så är en sådan rörelse i allmänhet omöjlig ... om andra, allvarligare problem kunde föras hit, skulle denna metod kunna vara till ännu större nytta och borde inte försummas." .

Grundläggande definitioner och satser inom grafteorin

Grafteori är en matematisk disciplin skapad av matematikers ansträngningar, därför innehåller presentationen de nödvändiga strikta definitionerna. Så låt oss gå vidare till en organiserad introduktion av de grundläggande begreppen i denna teori.

Definition 1. En graf är en samling av ett ändligt antal punkter, som kallas grafens hörn, och parvisa linjer som förbinder några av dessa hörn, som kallas grafens kanter eller bågar.

Denna definition kan formuleras på olika sätt: en graf är en icke-tom uppsättning punkter (hörn) och segment (kanter), vars båda ändar tillhör en given uppsättning punkter

I det följande kommer vi att beteckna grafens hörn med latinska bokstäver A, B, C, D. Ibland kommer grafen som helhet att betecknas med en stor bokstav.

Definition 2. Vertices i en graf som inte tillhör någon kant kallas isolerade.

Definition 3. En graf som endast består av isolerade hörn kallas null - räkna .

Notation: O "– en graf med hörn som inte har några kanter

Definition 4. En graf där varje par av hörn är förbundna med en kant kallas komplett.

Beteckning: U" – en graf som består av n hörn och kanter som förbinder alla möjliga par av dessa hörn. En sådan graf kan representeras som en n-gon där alla diagonaler är ritade

Definition 5. Graden av ett vertex är antalet kanter som vertexet tillhör.

Definition 6. En graf vars grader av alla k hörn är samma kallas en homogen gradgraf .

Definition 7. Komplementet till en given graf är en graf som består av alla kanter och deras ändar som måste läggas till den ursprungliga grafen för att få en komplett graf.

Definition 8. En graf som kan representeras på ett plan på ett sådant sätt att dess kanter skär varandra endast vid hörnen kallas plan.

Definition 9. En polygon i en plan graf som inte innehåller några hörn eller kanter på grafen kallas dess yta.

Begreppen en plan graf och en grafyta används när man löser problem med "korrekt" färgläggning av olika kartor.

Definition 10. En bana A till X är en sekvens av kanter som leder från A till X så att varannan angränsande kanter har en gemensam vertex och ingen kant förekommer mer än en gång.

Definition 11. En cykel är en väg där start- och slutpunkten sammanfaller.

Definition 12. En enkel cykel är en cykel som inte passerar genom någon av grafens hörn mer än en gång.

Definition 13. Banans längd , läggs på en slinga , antalet kanter på denna väg kallas.

Definition 14. Två hörn A och B i en graf kallas sammankopplade (bortkopplade) om det finns (finns inte) en väg som leder från A till B.

Definition 15. En graf kallas sammankopplad om varannan av dess hörn är sammankopplade; om grafen innehåller minst ett par frånkopplade hörn, kallas grafen frånkopplad.

Definition 16. Ett träd är en sammankopplad graf som inte innehåller cykler.

En tredimensionell modell av en trädgraf är till exempel ett riktigt träd med sin intrikat grenade krona; floden och dess bifloder bildar också ett träd, men redan platt - på jordens yta.

Definition 17. En frånkopplad graf som helt består av träd kallas en skog.

Definition 18. Ett träd där alla n hörn är numrerade från 1 till n kallas ett träd med omnumrerade hörn.

Så vi har undersökt de grundläggande definitionerna av grafteori, utan vilka det skulle vara omöjligt att bevisa teorem, och följaktligen lösa problem.

Problem lösta med hjälp av grafer

Kända problem

Resande säljare problem

Problemet med resande försäljare är ett av de berömda problemen i teorin om kombinatorik. Den lades fram 1934 och de bästa matematikerna bröt tänderna på den.

Problemformuleringen är som följer.
En resande säljare (vandrande köpman) måste lämna den första staden, besöka städer 2,1,3..n en gång i en okänd ordning och återvända till den första staden. Avstånden mellan städer är kända. I vilken ordning ska man gå runt i städerna så att den stängda vägen (rundturen) för en resande försäljare blir kortast?

Metod för att lösa resandeförsäljarproblemet

Girig algoritm "gå till närmaste (som du ännu inte har kommit in i) stad."
Denna algoritm kallas "girig" eftersom du i de sista stegen måste betala hårt för girighet.
Betrakta till exempel nätverket i figuren [Bilaga Fig.3], som representerar en smal romb. Låt en resande säljare börja från stad 1. Algoritmen "gå till närmaste stad" tar honom till stad 2, sedan 3, sedan 4; i det sista steget måste du betala för din girighet och återvända längs diamantens långa diagonal. Resultatet blir inte den kortaste utan den längsta turnén.

Problem om Königsbergsbroarna.

Problemet är formulerat enligt följande.
Staden Koenigsberg ligger på stranden av floden Pregel och två öar. De olika delarna av staden var sammankopplade med sju broar. På söndagar tog stadsborna promenader runt i staden. Fråga: är det möjligt att ta en promenad på ett sådant sätt att man, när man lämnar huset, återvänder tillbaka genom att gå exakt en gång över varje bro?
Broar över Pregelfloden ligger som på bilden[Bilaga Fig.1].

Betrakta grafen som motsvarar brodiagrammet [Bilaga Fig. 2].

För att svara på frågan om problemet räcker det att ta reda på om grafen är Eulerian. (Ett jämnt antal broar måste sträcka sig från minst en vertex). Du kan inte gå runt i staden och korsa alla broar en gång och komma tillbaka.

Flera intressanta uppgifter

1. "Rutter".

Problem 1

Som ni minns besökte jägaren efter döda själar Chichikov kända markägare en gång var. Han besökte dem i följande ordning: Manilov, Korobochka, Nozdryov, Sobakevich, Plyushkin, Tentetnikov, General Betrishchev, Petukh, Konstanzholgo, Överste Koshkarev. Ett diagram hittades på vilket Chichikov skissade de relativa positionerna för godsen och landsvägarna som förbinder dem. Bestäm vilken egendom som tillhör vem, om Chichikov inte körde någon av vägarna mer än en gång [Bilaga Fig. 4].

Lösning:

Vägkartan visar att Chichikov började sin resa från gods E, och slutade med gods O. Vi noterar att endast två vägar leder till gods B och C, så Chichikov var tvungen att resa längs dessa vägar. Låt oss markera dem med en fet linje. Sektioner av sträckan som går genom A har identifierats: AC och AB. Chichikov reste inte på vägarna AE, AK och AM. Låt oss stryka över dem. Låt oss markera med en fet linje ED; Låt oss stryka över DK. Låt oss stryka över MO och MN; Låt oss markera MF med en fet linje; stryk över FO; Låt oss markera FH, NK och KO med en fet linje. Låt oss hitta den enda möjliga vägen under detta villkor. Och vi får: egendom E - tillhör Manilov, D - Korobochka, C - Nozdrev, A - Sobakevich, B - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [Bilaga Fig.5].

Problem 2

Bilden visar en karta över området [Bilaga Fig. 6].

Du kan bara röra dig i pilarnas riktning. Du kan inte besöka varje punkt mer än en gång. På hur många sätt kan du ta dig från punkt 1 till punkt 9? Vilken väg är kortast och vilken är längst.

Lösning:

Vi "stratifierar" kretsen sekventiellt till ett träd, med början från vertex 1 [Bilaga Fig.7]. Låt oss hämta ett träd. Antalet möjliga sätt att komma från 1 till 9 är lika med antalet "hängande" hörn på trädet (det finns 14 av dem). Uppenbarligen är den kortaste vägen 1-5-9; den längsta är 1-2-3-6-5-7-8-9.

2 "Grupper, dejting"

Problem 1

Musikfestivalens deltagare, efter att ha träffats, bytte kuvert med adresser. Bevisa att:

a) ett jämnt antal kuvert överlämnades;

b) antalet deltagare som bytt kuvert ett udda antal gånger är jämnt.

Lösning: Låt festivaldeltagarna vara A 1, A 2, A 3. . . , Och n är toppen av grafen, och kanterna förbinder par av hörn som representerar killarna som byter kuvert [Bilaga Fig.8]

Lösning:

a) graden av varje vertex A i visar antalet kuvert som deltagare A i gav till sina vänner. Det totala antalet sända envelopp N är lika med summan av graderna av alla hörn i grafen N = grad. Ett 1+ steg. A 2++. . . + steg. A n -1 + grad. Och n, N =2p, där p är antalet kanter på grafen, dvs. N – jämnt. Följaktligen överlämnades ett jämnt antal kuvert;

b) i jämställdheten N = grad. Ett 1+ steg. A 2++. . . + steg. A n -1 + grad. Och n summan av udda termer måste vara jämn, och detta kan bara vara om antalet udda termer är jämnt. Det betyder att antalet deltagare som bytt kuvert ett udda antal gånger är jämnt.

Problem 2

En dag kom Andrei, Boris, Volodya, Dasha och Galya överens om att gå på bio på kvällen. De bestämde sig för att samordna valet av biograf och show över telefon. Det beslutades också att om det inte gick att kontakta någon per telefon så skulle bioresan ställas in. På kvällen samlades inte alla på bio och därför ställdes filmbesöket in. Dagen efter började de ta reda på vem som ringde vem. Det visade sig att Andrey kallade Boris och Volodya, Volodya kallade Boris och Dasha, Boris kallade Andrey och Dasha, Dasha kallade Andrey och Volodya, och Galya kallade Andrey, Volodya och Boris. Vem kunde inte ta sig via telefon och därför inte kom till mötet?

Lösning:

Låt oss rita fem punkter och märka dem med bokstäverna A, B, C, D, D. Det här är de första bokstäverna i namnen. Låt oss koppla ihop prickarna som motsvarar namnen på killarna som ringde.

[Bilaga Fig.9]

Från bilden är det tydligt att var och en av killarna - Andrey, Boris och Volodya - ringde alla andra. Det var därför de här killarna kom på bio. Men Galya och Dasha kunde inte komma i telefon med varandra (punkterna G och E är inte anslutna till ett linjesegment) och kom därför, i enlighet med avtalet, inte på bio.

Tillämpning av grafer inom olika områden av människors liv

Utöver de givna exemplen används grafer i stor utsträckning inom konstruktion, elektroteknik, management, logistik, geografi, maskinteknik, sociologi, programmering, automatisering av tekniska processer och produktion, psykologi och reklam.

Inom alla områden inom vetenskap och teknik möter du grafer. Grafer är underbara matematiska objekt med vilka du kan lösa matematiska, ekonomiska och logiska problem, olika pussel och förenkla villkoren för problem inom fysik, kemi, elektronik och automation. Många matematiska fakta kan enkelt formuleras på grafernas språk. Grafteori är en del av många vetenskaper. Grafteori är en av de vackraste och mest visuella matematiska teorierna. På senare tid har grafteori hittat fler och fler tillämpningar i tillämpade frågor. Även beräkningskemi har vuxit fram - ett relativt ungt kemiområde baserat på tillämpning av grafteori.

Molekylära grafer, som används i stereokemi och strukturell topologi, kemi av kluster, polymerer, etc., är oriktade grafer som visar strukturen hos molekyler [Bilaga Fig. 10]. Topparna och kanterna på dessa grafer motsvarar motsvarande atomer och kemiska bindningar mellan dem.

Molekylära grafer och träd: [Bilaga Fig. 10] a, b - multigrafer, respektive. eten och formaldehyd; man säger pentanisomerer (träd 4, 5 är isomorfa till träd 2).

I stereokemin av organismer mest. Molekylära träd används ofta - huvudträden av molekylära grafer, som bara innehåller alla hörn som motsvarar C-atomerna Sammanställning av uppsättningar av mol. träd och etableringen av deras isomorfism gör det möjligt att fastställa att de säger. strukturer och hitta det totala antalet isomerer av alkaner, alkener och alkyner

Proteinnätverk

Proteinnätverk är grupper av fysiskt interagerande proteiner som fungerar i en cell tillsammans och på ett koordinerat sätt, och kontrollerar sammankopplade processer som sker i kroppen [bilaga fig. 11].

Hierarkisk systemgraf kallas ett träd. Ett särdrag hos ett träd är att det bara finns en väg mellan två av dess hörn. Trädet innehåller inte cykler eller loopar.

Vanligtvis har ett träd som representerar ett hierarkiskt system en huvudpunkt, som kallas trädets rot. Varje vertex på trädet (förutom roten) har bara en förfader - objektet som utsetts av det ingår i en toppnivåklass. Varje vertex av ett träd kan generera flera avkomlingar - hörn som motsvarar klasser på lägre nivå.

För varje par av trädens hörn finns det en unik väg som förbinder dem. Den här egenskapen används för att hitta alla förfäder, till exempel i den manliga linjen, till varje person vars stamtavla representeras i form av ett släktträd, vilket är ett "träd" i betydelsen grafteorin.

Exempel på mitt släktträd [Bilaga Fig. 12].

Ett annat exempel. Bilden visar det bibliska släktträdet [Bilaga Fig. 13].

Problemlösning

1. Transportuppgift. Låt det finnas en bas i staden Krasnodar med råvaror som måste distribueras till städerna Krymsk, Temryuk, Slavyansk-on-Kuban och Timashevsk på en resa, spendera så lite tid och bränsle som möjligt och återvända tillbaka till Krasnodar .

Lösning:

Låt oss först göra en graf över alla möjliga resvägar [Bilaga Fig.14], med hänsyn till de verkliga vägarna mellan dessa bosättningar och avståndet mellan dem. För att lösa detta problem måste vi skapa en annan graf, en trädliknande [Bilaga Fig.15].

För att underlätta lösningen utser vi städerna med nummer: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

Resultatet är 24 lösningar, men vi behöver bara de kortaste vägarna. Av alla lösningar är bara två tillfredsställande, detta är 35 mil.

På samma sätt är det möjligt och, tror jag, nödvändigt att beräkna faktiska transporter från en ort till en annan.

Logiskt problem som involverar transfusion. Hinken innehåller 8 liter vatten, och det finns två kastruller med en kapacitet på 5 och 3 liter. du behöver hälla 4 liter vatten i en fem-liters panna och lämna kvar 4 liter i hinken, d.v.s. häll vattnet lika i hinken och en stor panna.

Lösning:

Situationen vid varje ögonblick kan beskrivas med tre siffror [Bilaga Fig. 16].

Som ett resultat får vi två lösningar: en i 7 drag, den andra i 8 drag.

Slutsats

Så för att lära dig hur man löser problem måste du förstå vad de är, hur de är uppbyggda, vilka komponenter de består av, vilka verktyg är det för att lösa problem.

Genom att lösa praktiska problem med hjälp av grafteori blev det klart att i varje steg, i varje steg av deras lösning, är det nödvändigt att tillämpa kreativitet.

Redan från början, i det första skedet, ligger det i det faktum att du måste kunna analysera och koda problemets tillstånd. Det andra steget är en schematisk notation, som består av en geometrisk representation av graferna, och i detta skede är elementet kreativitet mycket viktigt eftersom det är långt ifrån lätt att hitta överensstämmelse mellan elementen i villkoret och motsvarande element i villkoret. graf.

När jag löste ett transportproblem eller en uppgift att upprätta ett släktträd kom jag fram till att grafmetoden verkligen är intressant, vacker och visuell.

Jag blev övertygad om att grafer används i stor utsträckning inom ekonomi, management och teknik. Grafteori används också i programmering. Detta diskuterades inte i detta arbete, men jag tror att det bara är en tidsfråga.

Detta vetenskapliga arbete undersöker matematiska grafer, deras användningsområden och löser flera problem med hjälp av grafer. Kunskaper om grunderna i grafteori är nödvändiga inom olika områden relaterade till produktion och företagsledning (till exempel nätverksbyggnadsschema, postleveransscheman). Dessutom, medan jag arbetade med en vetenskaplig artikel, behärskade jag att arbeta på en dator med hjälp av WORD-textredigeraren. Därmed har målen för det vetenskapliga arbetet fullbordats.

Så från allt ovan följer det praktiska värdet av grafteorin oemotsägligt, vilket bevis var målet med detta arbete.

Litteratur

Berge K. Grafteori och dess tillämpningar. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J. Introduktion till finit matematik. -M.: IIL, 1963.

Ore O. Grafer och deras tillämpning. -M.: Mir, 1965.

Harari F. Grafteori. -M.: Mir, 1973.

Zykov A.A. Finita grafteori. -Novosibirsk: Vetenskap, 1969.

Berezina L.Yu. Grafer och deras tillämpning. -M.: Utbildning, 1979. -144 sid.

"Soros Educational Journal" nr 11 1996 (artikel "Platta grafer");

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

Olehnik S. N., Nesterenko Yu V., Potapov M. K. "Gamla underhållande problem", M. "Science", 1988 (del 2, avsnitt 8; bilaga 4);

Ansökan

Ansökan

P

Ris. 6

Ris. 7

Ris. 8

Ansökan

Ansökan

Ansökan

P

Ris. 14

Ansökan

Sammanfattning om ämnet högre matematik på ämnet:

Tillämpning av grafteori i kemi

Utförs av en student från gruppen NH-202

Moskva 2011
Grafer är fältet för finit matematik som studerar diskreta strukturer; används för att lösa olika teoretiska och tillämpade problem.
Några grundläggande begrepp. En graf är en samling punkter (hörn) och en samling par av dessa punkter (inte nödvändigtvis alla) förbundna med linjer (fig. 1,a). Om linjerna i en graf är orienterade (det vill säga pilarna anger riktningen för anslutningen av hörnen), kallas de bågar, eller grenar; om oorienterad, - kanter. Följaktligen kallas en graf som endast innehåller bågar en riktad graf, eller en digraf; endast kant-oorienterad; bågar och revben - blandade. En graf med flera kanter kallas en multigraf; en graf som endast innehåller kanter som hör till två av dess disjunkta delmängder (delar) är tvådelad; bågar (kanter) och (eller) hörn som motsvarar vissa vikter eller numeriska värden för alla parametrar viktas. En bana i en graf är en alternerande sekvens av hörn och bågar där ingen av hörnen upprepas (till exempel a, b i fig. 1,a); kontur - en stängd bana där de första och sista hörnen sammanfaller (till exempel f, h); loop - en båge (kant) som börjar och slutar vid samma vertex. En grafkedja är en sekvens av kanter där ingen av hörnen upprepas (till exempel c, d, e); cykel - en sluten kedja där dess initiala och slutliga hörn sammanfaller. En graf kallas sammankopplad om något par av dess hörn är sammankopplade med en kedja eller bana; annars kallas grafen frånkopplad.
Ett träd är en sammankopplad oriktad graf som inte innehåller cykler eller konturer (Fig. 1, b). Spännande subgraf i en graf är en delmängd av den som innehåller alla hörn och endast vissa kanter. En grafs spännträd är dess spännande subgraf, vilket är ett träd. Grafer kallas isomorfa om det finns en en-till-en-överensstämmelse mellan uppsättningarna av deras hörn och kanter (bågar).
För att lösa problem med grafteori och dess tillämpningar representeras grafer med hjälp av matriser (angränsning, incidens, tvårads, etc.), såväl som speciella. numeriska egenskaper. Till exempel, i närliggande matris (fig. 1c) motsvarar raderna och kolumnerna numren på grafens hörn, och dess element tar värdena 0 och 1 (respektive frånvaron och närvaron av en båge mellan ett givet par av hörn); i incidensmatrisen (fig. 1d) motsvarar raderna numren på hörnen, kolumnerna motsvarar numren på bågarna och elementen tar värdena 0, + 1 och - 1 (respektive frånvaron) närvaron av en båge som går in i och lämnar vertexet). De vanligaste numeriska egenskaperna: antalet hörn (m), antalet bågar eller kanter (n), det cyklomatiska talet eller grafens rangordning (n - m + k, där k är antalet anslutna subgrafer i en frånkopplad graf till exempel, för grafen i fig. 1, kommer b rankningen att vara: 10-6+ 1 =5).
Tillämpningen av grafteori bygger på konstruktion och analys av olika klasser av kemiska och kemisk-teknologiska grafer, som också kallas topologiska modeller, d.v.s. modeller som endast tar hänsyn till arten av kopplingarna mellan hörnen. Bågarna (kanterna) och hörn på dessa grafer visar kemiska och kemisk-teknologiska begrepp, fenomen, processer eller objekt och följaktligen kvalitativa och kvantitativa samband eller vissa samband mellan dem.

Ris. 1. Illustration av några grundläggande begrepp: en blandad graf; b-spännande träd (heldragna bågar a, h, d, f, h) och en viss subgraf (streckade bågar c, e, g, k, l) av digrafen; c, r-matriser resp. angränsning och förekomst av en digraf.
Teoretiska problem. Kemiska grafer gör det möjligt att förutsäga kemiska transformationer, förklara essensen och systematisera några grundläggande begrepp inom kemi: struktur, konfiguration, konformationer, kvantmekaniska och statistisk-mekaniska interaktioner mellan molekyler, isomerism, etc. Kemiska grafer inkluderar molekylära, bipartita och signalgrafer av kinetiska reaktionsekvationer.
Molekylära grafer, som används i stereokemi och strukturell topologi, kemi av kluster, polymerer, etc., är oriktade grafer som visar strukturen av molekyler (Fig. 2). Topparna och kanterna på dessa grafer motsvarar respektive atomer och kemiska bindningar mellan dem.

Ris. 2. Molekylära grafer och träd: a, b - multigrafer, respektive. eten och formaldehyd; man säger pentanisomerer (träd 4, 5 är isomorfa till träd 2).
I stereokemin av organiska ämnen används oftast molekylära träd - spännande träd av molekylära grafer, som bara innehåller alla hörn som motsvarar C-atomer (fig. 2, a och b). Att sammanställa uppsättningar av molekylära träd och fastställa deras isomorfism gör det möjligt att bestämma molekylära strukturer och hitta det totala antalet isomerer av alkaner, alkener och alkyner (Fig. 2, c).
Molekylära grafer gör det möjligt att reducera problem relaterade till kodning, nomenklatur och strukturella egenskaper (förgrening, cyklicitet, etc.) av molekyler av olika föreningar till analys och jämförelse av rent matematiska egenskaper och egenskaper hos molekylära grafer och deras träd, samt deras motsvarande matriser. För att identifiera kvantitativa korrelationer mellan strukturen av molekyler och de fysikalisk-kemiska (inklusive farmakologiska) egenskaperna hos föreningar, har mer än 20 tusen namn på topologiska index för molekyler (Wiener, Balaban, Hosoya, Plat, Randic, etc.) utvecklats, som är bestäms med hjälp av matriser och numeriska egenskaper hos molekylära träd. Till exempel, Wiener-index W = (m 3 + m)/6, där m är antalet hörn som motsvarar C-atomer, korrelerar med molekylära volymer och brytningar, bildningsentalpier, viskositet, ytspänning, kromatografiska konstanter för föreningar, oktantal av kolväten och till och med fysiologisk aktivitet hos läkemedel.
Viktiga parametrar för molekylära grafer som används för att bestämma de tautomera formerna av en given substans och deras reaktivitet, såväl som i klassificeringen av aminosyror, nukleinsyror, kolhydrater och andra komplexa naturliga föreningar, är den genomsnittliga och totala (H) informationskapaciteten. Parametern beräknas med hjälp av Shannon-informationsentropiformeln: , där p t är sannolikheten för att grafens hörn m tillhör den i:te typen, eller ekvivalensklassen, k; i = , Parameter. Studiet av molekylära strukturer såsom oorganiska kluster eller Möbius-remsor handlar om att fastställa isomorfismen hos motsvarande molekylära grafer genom att placera dem (inbädda) i komplexa polyedrar (till exempel polyedrar i fallet med kluster) eller speciella. flerdimensionella ytor (till exempel Riemann-ytor). Analys av molekylära grafer för polymerer, vars hörn motsvarar monomerenheter, och kanterna till kemiska bindningar mellan dem, gör det möjligt att förklara till exempel effekterna av utesluten volym, vilket leder till kvalitativa förändringar i polymerernas förutspådda egenskaper .

Ris. 3. Reaktionsdiagram: a-bipartit; b-signalnivå för kinetik; ri, g2-r-tion; a1-a6-reagens; k-hastighetskonstanter p-tsny; s-komplex Laplace-transformvariabel.
Med hjälp av grafteori och principer för artificiell intelligens har mjukvara utvecklats för informationssökningssystem inom kemi, samt automatiserade system för identifiering av molekylära strukturer och rationell planering av organisk syntes. För den praktiska implementeringen på en dator av operationer för att välja rationella vägar för kemiska transformationer baserade på retrosyntetiska och syntoniska principer, används grenade sökgrafer på flera nivåer för lösningsalternativ, vars hörn motsvarar de molekylära graferna för reagenser och produkter, och bågarna skildrar omvandlingar av ämnen.

Ris. 4. Enkelkrets kemisk-teknologiskt system och motsvarande grafer: a-strukturdiagram; b, c-materialflödesgrafer, respektive. genom totala massflödeshastigheter och komponent A-flödeshastighet; r - termiskt flödesdiagram; d-fragment av ekvationssystemet (f 1 - f 6) av materialbalansen, erhållen från analysen av graferna i fig. 4, b och c; e-bipartit informationsdigraf; g-informationsgraf, I-mixer; II-reaktor; III-destillationskolonn; IV-kylskåp; I 1 -I 8 -teknik. bäckar; q-massflöde; H är flödets entalpi; i. s och i*, s* - resp. verkliga och fiktiva källor och sänkor av material och värmeflöden; c-koncentration av reagenset; V är reaktorns volym.
Matrisrepresentationer av molekylära grafer av olika föreningar är ekvivalenta (efter transformation av motsvarande matriselement) med matrismetoder inom kvantkemin. Därför används grafteori när man utför komplexa kvantkemiska beräkningar: för att bestämma antalet, egenskaperna och energierna hos molekylära orbitaler, förutsäga reaktiviteten hos konjugerade alternerande och icke-alternerande polyener, identifiera aromatiska och antiaromatiska egenskaper hos ämnen, etc.
För att studera störningar i system som består av ett stort antal partiklar inom kemisk fysik används så kallade Feynman-diagram - grafer vars hörn motsvarar fysiska partiklars elementära interaktioner, kanterna till deras vägar efter kollisioner. I synnerhet gör dessa grafer det möjligt att studera mekanismerna för oscillerande reaktioner och bestämma stabiliteten hos reaktionssystem.
För att välja rationella vägar för omvandlingen av reagensmolekyler för en given uppsättning kända interaktioner, används tvådelade reaktionsgrafer (högpunkterna motsvarar molekyler och dessa reaktioner, bågarna motsvarar interaktionerna mellan molekyler i reaktionen; Fig. 3,a ). Sådana grafer gör det möjligt att utveckla interaktiva algoritmer för att välja optimala vägar för kemiska omvandlingar som kräver det minsta antalet mellanreaktioner, det minsta antalet reagenser från listan över acceptabla, eller uppnå det högsta utbytet av produkter.
Signalgrafer av reaktionskinetiska ekvationer visar system av kinetiska ekvationer presenterade i algebraisk operatorform (Fig. 3b). Grafernas hörn motsvarar de så kallade informationsvariablerna, eller signalerna, i form av koncentrationer av reagens, bågar - till förhållandena mellan signaler, och bågarnas vikter bestäms av kinetiska konstanter. Sådana grafer används för att studera mekanismerna och kinetiken för komplexa katalytiska reaktioner, komplexa fasjämvikter vid bildningen av komplexa föreningar, såväl som för att beräkna parametrarna för lösningars additiva egenskaper.
Tillämpade problem. För att lösa flerdimensionella problem med analys och optimering av kemisk-teknologiska system (CTS) används följande kemisk-teknologiska grafer (Fig. 4): flödes-, informationsflödes-, signal- och tillförlitlighetsgrafer. Flödesdiagram, som är viktade digrafer, inkluderar parametriska material i termer av totala massflödeshastigheter för fysiska flöden och massflödeshastigheter för vissa kemiska komponenter eller element, såväl som termiska grafer. De listade graferna motsvarar de fysikaliska och kemiska omvandlingarna av ämnen och energi i ett givet kemiskt system.
Parametriska flödesdiagram visar omvandlingen av parametrar (massflöden, etc.) av fysiska flöden av CTS-element; kurvornas hörn motsvarar de matematiska modellerna av enheterna, såväl som källorna och sänkorna för de specificerade flödena, och bågarna motsvarar själva flödena, och bågarnas vikter är lika med antalet parametrar för motsvarande flöde. Parametriska grafer används för att utveckla algoritmer för att analysera teknologiska lägen för kemiska system med flera kretsar. Sådana algoritmer upprättar sekvensen av beräkningssystem av ekvationer av matematiska modeller av individuella enheter i vilket system som helst för att bestämma parametrarna för dess utflöden med kända värden för variabla ingångsflöden.
Materialflödesdiagram visar förändringar i förbrukningen av ämnen i kemiska ämnen. Topparna på graferna motsvarar anordningar där de totala massflödeshastigheterna för fysiska flöden och massflödeshastigheterna för vissa kemiska komponenter eller element omvandlas, såväl som källor och sänkor för flödesämnen eller dessa komponenter; Följaktligen motsvarar kurvornas bågar fysiska flöden eller fysiska och fiktiva (kemiska omvandlingar av ämnen i apparater) källor och sänkor för alla komponenter, och bågarnas vikter är lika med massflödeshastigheterna för båda typerna. Termiska flödesdiagram visar värmebalanser i CTS; kurvornas hörn motsvarar enheter där värmeförbrukningen av fysiska flöden förändras, och dessutom till källorna och sänkorna för termisk energi i systemet; bågar motsvarar fysiska och fiktiva (fysikalisk-kemisk energiomvandling i enheter) värmeflöden, och bågarnas vikter är lika med flödenas entalpier. Material- och termiska grafer används för att sammanställa program för automatiserad utveckling av algoritmer för att lösa ekvationssystem för material- och värmebalanser i komplexa kemiska system.
Informationsbeståndsdiagram visar den logiska informationsstrukturen för ekvationssystem av matematiska modeller av CTS; används för att utveckla optimala algoritmer för att beräkna dessa system. En tvådelad informationsgraf (fig. 4, e) är en oriktad eller orienterad graf, vars hörn motsvarar respektive ekvationerna fl - f 6 och variablerna q 1 - V, och grenarna återspeglar deras förhållande. Informationsgraf (fig. 4, g) - en digraf som visar ordningen för att lösa ekvationer; toppen av grafen motsvarar dessa ekvationer, källor och mottagare av XTS-information, och grenarna motsvarar informationsvariabler.
Signalgrafer motsvarar linjära ekvationssystem av matematiska modeller av kemiska tekniska processer och system. Grafernas hörn motsvarar signaler (till exempel temperatur), och grenarna motsvarar kopplingar mellan dem. Sådana grafer används för att analysera de statiska och dynamiska lägena för multiparameterprocesser och kemiska system, såväl som indikatorer för ett antal av deras viktigaste egenskaper (stabilitet, känslighet, kontrollerbarhet).
Tillförlitlighetsgrafer används för att beräkna olika indikatorer på tillförlitligheten hos kemisk utrustning. Bland de många grupperna av dessa grafer (till exempel parametriska, logiskt-funktionella) är de så kallade felträden särskilt viktiga. Varje sådant träd är en viktad digraf som visar sambandet mellan många enkla fel i enskilda processer och CTS-enheter, vilket leder till många sekundära fel och det resulterande felet i systemet som helhet.
För att skapa komplex av program för automatiserad syntes av optimal mycket tillförlitlig produktion (inklusive resursbesparing), tillsammans med principerna för artificiell intelligens, orienterad semantik eller semantisk, används grafer över CTS-lösningsalternativ. Dessa grafer, som i ett särskilt fall är träd, visar procedurer för att generera en uppsättning rationella alternativa CTS-scheman (till exempel 14 möjliga när man separerar en femkomponentsblandning av målprodukter genom korrigering) och procedurer för det ordnade urvalet bland dem av ett schema som är optimalt enligt något kriterium för systemeffektivitet.
etc.............

Dessutom var Euler under de sista 12 åren av sitt liv allvarligt sjuk, blev blind och fortsatte, trots sin allvarliga sjukdom, att arbeta och skapa.

Statistiska beräkningar visar att Euler gjorde i genomsnitt en upptäckt per vecka.

Det är svårt att hitta ett matematiskt problem som inte togs upp i Eulers verk.

Alla matematiker av efterföljande generationer studerade med Euler på ett eller annat sätt, och det var inte utan anledning som den berömda franska vetenskapsmannen P.S. Laplace sa: "Läs Euler, han är oss allas lärare."

Lagrange säger: "Om du verkligen älskar matematik, läs Euler; presentationen av hans verk är anmärkningsvärd för dess fantastiska klarhet och noggrannhet." Faktum är att elegansen i hans beräkningar fördes till högsta grad. Condorcet avslutade sitt tal vid akademin till minne av Euler med följande ord: "Så Euler slutade leva och räkna!" Att leva för att räkna - vad tråkigt det verkar utifrån!

Det är brukligt att föreställa sig en matematiker som torr och döv för allt vardagligt, för det som intresserar vanliga människor.

Uppkallad efter Euler, är problemet med tre hus och tre brunnar.

En av topologins grenar. En graf är ett geometriskt diagram som är ett system av linjer som förbinder vissa punkter. Punkterna kallas hörn, och linjerna som förbinder dem kallas kanter (eller bågar). Alla grafteoretiska problem kan lösas i både grafisk och matrisform. Vid skrivning i matrisform betecknas möjligheten att sända ett meddelande från en given vertex till en annan med ett, och dess frånvaro betecknas med noll.

Ursprunget till grafteorin på 1700-talet. förknippas med matematiska pussel, men en särskilt stark drivkraft för dess utveckling gavs på 1800-talet. och främst på 1900-talet, när möjligheterna för dess praktiska tillämpningar upptäcktes: för beräkning av radioelektroniska kretsar, lösa den sk. transportuppgifter etc. Sedan 50-talet. Grafteori används alltmer inom socialpsykologi och sociologi.

Inom grafteorin bör man nämna verk av F. Harry, J. Kemeny, K. Flament, J. Snell, J. French, R. Norman, O. Oyser, A. Beivelas, R. Weiss, etc. I USSR, enligt T. g. M. Borodkin och andra.

Språket Graph Theory är väl lämpat för att analysera olika typer av strukturer och överföra tillstånd. I enlighet med detta kan vi urskilja följande typer av sociologiska och sociopsykologiska problem lösta med hjälp av grafteori.

Formalisering och konstruktion av en generell strukturell modell av ett socialt objekt på olika nivåer av dess komplexitet. Till exempel ett strukturdiagram över en organisation, sociogram, jämförelse av släktskapssystem i olika samhällen, analys av gruppers rollstruktur m.m.

Vi kan anse att rollstrukturen innefattar tre komponenter: personer, befattningar (i en förenklad version - befattningar) och uppgifter som utförs i en given befattning.

Varje komponent kan representeras som en graf:

Det är möjligt att kombinera alla tre graferna för alla positioner eller bara för en, och som ett resultat får vi en tydlig uppfattning om den specifika strukturen för c.l. denna roll. För rollen som position P5 har vi alltså en graf (Fig.). Att väva informella relationer i den specificerade formella strukturen kommer att komplicera grafen avsevärt, men det kommer att vara en mer exakt kopia av verkligheten.

a) kvantiteter. bedöma vikten (statusen) för en individ i en hierarkisk organisation. Ett av de möjliga alternativen för att bestämma status är formeln:

där r (p) är statusen för en viss person p, k är värdet på underordningsnivån, definierat som det minsta antalet steg från en given person till sin underordnade, nk är antalet personer på en given nivå k . Till exempel i den organisation som representeras av följande. Räkna:

vikt a=1,2+2,7+3,4=28; 6=1·3+2·3=9, etc.

b) fastställande av gruppledaren. Ledaren kännetecknas vanligtvis av större anknytning till resten av gruppen jämfört med andra. Liksom i föregående uppgift kan även här olika metoder användas för att identifiera ledaren.

Den enklaste metoden ges av formeln: r=Σdxy/Σdqx, dvs. kvoten av att dividera summan av alla avstånd för varje individ till alla andra med summan av avstånden för en given individ till alla andra.

4) Analys av effektiviteten av verksamheten i detta system, vilket också inkluderar sådana uppgifter som att söka efter den optimala strukturen för organisationen, öka gruppsammanhållningen, analysera det sociala systemet ur dess hållbarhetssynpunkt; studie av informationsflöden (överföring av meddelanden vid problemlösning, gruppmedlemmarnas inflytande på varandra i processen att förena gruppen); med hjälp av teknik löser de problemet med att hitta ett optimalt kommunikationsnät.

När det tillämpas på grafteori, såväl som på vilken matematisk apparat som helst, är det sant att de grundläggande principerna för att lösa ett problem bestäms av en substantiv teori (i detta fall sociologi).

Uppgift : Tre grannar har tre gemensamma brunnar. Är det möjligt att bygga icke-korsande stigar från varje hus till varje brunn? Stigarna kan inte passera genom brunnar och hus (Fig. 1).

Ris. 1. Till problemet med hus och brunnar.

För att lösa detta problem kommer vi att använda en sats som bevisades av Euler 1752, som är en av de viktigaste inom grafteorin. Det första arbetet med grafteori tillhör Leonhard Euler (1736), även om termen "graf" först introducerades 1936 av den ungerske matematikern Dénes König. Grafer kallades diagram som bestod av punkter och segment av räta linjer eller kurvor som förbinder dessa punkter.

Sats. Om en polygon är uppdelad i ett ändligt antal polygoner så att alla två polygoner i partitionen antingen inte har gemensamma punkter, eller har gemensamma hörn eller har gemensamma kanter, så gäller likheten

B - P + G = 1, (*)

där B är det totala antalet hörn, P är det totala antalet kanter, G är antalet polygoner (ytor).

Bevis. Låt oss bevisa att likheten inte förändras om en diagonal ritas i någon polygon av en given partition (Fig. 2, a).

A) b)

Efter att ha ritat en sådan diagonal kommer den nya partitionen att ha B-hörn, P+1-kanter, och antalet polygoner kommer att öka med en. Därför har vi

B - (P + 1) + (G+1) = B – P + G.

Med den här egenskapen ritar vi diagonaler som delar upp de inkommande polygonerna i trianglar, och för den resulterande partitionen visar vi genomförbarheten av relationen.

För att göra detta kommer vi sekventiellt att ta bort yttre kanter, vilket minskar antalet trianglar. I det här fallet är två fall möjliga:

för att ta bort triangel ABC måste du ta bort två kanter, i vårt fall AB och BC;

För att ta bort triangel MKN måste du ta bort ena kanten, i vårt fall MN.

I båda fallen kommer jämställdheten inte att förändras. Till exempel, i det första fallet, efter att ha tagit bort triangeln, kommer grafen att bestå av B-1 hörn, P-2 kanter och G-1 polygon:

(B - 1) - (P + 2) + (G -1) = B – P + G.

Att ta bort en triangel förändrar alltså inte likheten.

Om vi ​​fortsätter med denna process att ta bort trianglar kommer vi så småningom fram till en partition som består av en enda triangel. För en sådan partition B = 3, P = 3, G = 1 och därför,

Det betyder att likheten även gäller för den ursprungliga partitionen, varifrån vi slutligen får fram att relationen är giltig för denna partition av polygonen.

Observera att Eulers relation inte beror på formen på polygonerna. Polygoner kan deformeras, förstoras, förminskas eller till och med kröka sina sidor, så länge det inte finns några luckor i sidorna. Eulers relation kommer inte att förändras.

Låt oss nu gå vidare till att lösa problemet med tre hus och tre brunnar.

Lösning. Låt oss anta att detta kan göras. Låt oss markera husen med punkterna D1, D2, D3 och brunnarna med punkterna K1, K2, K3 (Fig. 1). Vi kopplar ihop varje huspunkt med varje brunnspunkt. Vi får nio kanter som inte skär varandra i par.

Dessa kanter bildar en polygon på planet, uppdelad i mindre polygoner. Därför måste Euler-relationen B - P + G = 1 vara uppfylld för denna partition.

Låt oss lägga till ytterligare ett ansikte till de övervägda ytorna - den yttre delen av planet i förhållande till polygonen. Då kommer Euler-relationen att ha formen B - P + G = 2, med B = 6 och P = 9.

Därför är Г = 5. Var och en av de fem ytorna har minst fyra kanter, eftersom, enligt problemets villkor, ingen av vägarna direkt ska ansluta två hus eller två brunnar. Eftersom varje kant ligger på exakt två ytor måste antalet kanter vara minst (5 4)/2 = 10, vilket motsäger villkoret att deras antal är 9.

Den resulterande motsägelsen visar att svaret på problemet är negativt - det är omöjligt att dra icke-korsande stigar från varje hus till varje by

Grafteori i kemi

Tillämpning av grafteori för konstruktion och analys av olika klasser av kemiska och kemisk-teknologiska grafer, som även kallas topologi, modeller, d.v.s. modeller som endast tar hänsyn till arten av kopplingarna mellan hörnen. Bågarna (kanterna) och hörn av dessa grafer återspeglar kemiska och kemisk-teknologiska koncept, fenomen, processer eller objekt och följaktligen kvalitativa och kvantitativa samband eller vissa samband mellan dem.

Teoretiska problem. Kemiska grafer gör det möjligt att förutsäga kemiska transformationer, förklara essensen och systematisera några grundläggande begrepp inom kemi: struktur, konfiguration, bekräftelser, kvantmekaniska och statistisk-mekaniska interaktioner mellan molekyler, isomerism, etc. Kemiska grafer inkluderar molekylära, bipartita och signalgrafer av kinetiska reaktionsekvationer. Molekylära grafer, som används i stereokemi och strukturell topologi, kemi av kluster, polymerer, etc., är oriktade grafer som visar strukturen hos molekyler. Topparna och kanterna på dessa grafer motsvarar motsvarande atomer och kemiska bindningar mellan dem.

I stereokemi org. c-c de vanligaste är molekylära träd - spänner över träd av molekylära grafer som bara innehåller alla hörn som motsvarar atomer. Att sammanställa uppsättningar av molekylära träd och fastställa deras isomorfism gör det möjligt att bestämma molekylära strukturer och hitta det totala antalet isomerer av alkaner. alkener och alkyner. Molekylära grafer gör det möjligt att reducera problem relaterade till kodning, nomenklatur och strukturella egenskaper (förgrening, cyklicitet, etc.) av molekyler av olika föreningar till analys och jämförelse av rent matematiska egenskaper och egenskaper hos molekylära grafer och deras träd, samt deras motsvarande matriser. För att identifiera antalet korrelationer mellan molekylers struktur och föreningars fysikalisk-kemiska (inklusive farmakologiska) egenskaper har mer än 20 så kallade sådana utvecklats. Topologiska index för molekyler (Wiener, Balaban, Hosoya, Plata, Randic, etc.), som bestäms med hjälp av matriser och numeriska egenskaper hos molekylära träd. Till exempel, Wienerindex W = (m3 + m)/6, där m är antalet hörn som motsvarar C-atomer, korrelerar med molekylära volymer och brytningar, bildningsentalpier, viskositet, ytspänning, kromatografiska konstanter för föreningar, oktan. antal kolväten och till och med fysiologi. drogernas aktivitet. Viktiga parametrar för molekylära grafer som används för att bestämma de tautomera formerna av en given substans och deras reaktivitet, såväl som i klassificeringen av aminosyror, nukleinsyror, kolhydrater och andra komplexa naturliga föreningar, är den genomsnittliga och totala (H) informationskapaciteten. Analys av molekylära grafer av polymerer, vars hörn motsvarar monomerenheter, och kanterna motsvarar kemiska bindningar mellan dem, gör det möjligt att förklara till exempel effekterna av utesluten volym som leder till kvaliteter. förändringar i de förutsagda egenskaperna hos polymerer. Med hjälp av Graph Theory och principerna för artificiell intelligens har mjukvara utvecklats för informationshämtningssystem inom kemi, samt automatiserade system för identifiering av molekylära strukturer och rationell planering av organisk syntes. För den praktiska implementeringen på en dator av operationer för att välja rationella kemiska vägar. transformationer baserade på retrosyntetiska och syntoniska principer använder grenade sökgrafer på flera nivåer för lösningsalternativ, vars hörn motsvarar de molekylära graferna för reagenser och produkter, och bågarna visar transformationer.

För att lösa flerdimensionella problem med analys och optimering av kemiska tekniska system (CTS) används följande kemiska tekniska grafer: flödes-, informationsflödes-, signal- och tillförlitlighetsgrafer. För studier i kemi. Fysiken för störningar i system som består av ett stort antal partiklar använder den sk. Feynman-diagram är grafer, vars hörn motsvarar de elementära interaktionerna mellan fysiska partiklar, kanterna på deras vägar efter kollisioner. I synnerhet gör dessa grafer det möjligt att studera mekanismerna för oscillerande reaktioner och bestämma stabiliteten hos reaktionssystem. Materialflödesgrafer visar förändringar i flödeshastigheter i kemiska värmesystem. kurvornas hörn motsvarar enheter där värmeförbrukningen av fysiska flöden förändras, och dessutom till källorna och sänkorna för termisk energi i systemet; bågar motsvarar fysiska och fiktiva (fysikalisk-kemisk energiomvandling i enheter) värmeflöden, och bågarnas vikter är lika med flödenas entalpier. Material- och termiska grafer används för att sammanställa program för automatiserad utveckling av algoritmer för att lösa ekvationssystem för material- och värmebalanser i komplexa kemiska system. Informationsflödesgrafer visar den logiska informationsstrukturen för system av matematiska ekvationer. XTS-modeller; används för att utveckla optimala algoritmer för att beräkna dessa system. En tvådelad informationsgraf är en oriktad eller riktad graf vars hörn motsvarar respektive. ekvationerna fl -f6 och variablerna q1 – V, och grenarna speglar deras förhållande. Informationsgraf – en digraf som visar ordningen för att lösa ekvationer; toppen av grafen motsvarar dessa ekvationer, källor och mottagare av XTS-information, och grenarna motsvarar information. variabler. Signalgrafer motsvarar linjära ekvationssystem av matematiska modeller av kemiska tekniska processer och system. Tillförlitlighetsgrafer används för att beräkna olika tillförlitlighetsindikatorer X.

Litteratur som används:

1.Berge K., T. g. och dess tillämpning, översättning från franska, M., 1962;

2. Kemeny J., Snell J., Thompson J., Introduction to Finite Mathematics, övers. från engelska, 2:a uppl., M., 1963;

3.Ope O., Grafer och deras tillämpning, övers. från English, M., 1965;

4. Belykh O.V., Belyaev E.V., Possibilities of use technology in sociology, i: Man and Society, vol. 1, [L.], 1966;

5. Kvantitativa metoder i sociologisk forskning, M., 1966; Belyaev E.V., Problems of sociological measurements, "VF", 1967, nr 7; Bavelas. Kommunikationsmönster i uppgiftsorienterade grupper, i boken. Lerner D., Lass well H., Political sciences, Stanford, 1951;

6. Kemeny J. G., Snell J., Mathematical models in the social sciences, N. Y., 1962; Filament C., Tillämpningar av grafteori på gruppstruktur, N. Y., 1963; Оeser Ο. A., Hararu F., Rollstrukturer och beskrivning i termer av grafteori, i boken: Biddle V., Thomas E. J., Rollteori: koncept och forskning, N. Y., 1966. E. Belyaev. Leningrad.