Grafteori är ett av underavsnitten.matematik, vars huvudsakliga kännetecken är den geometriska metoden för att studera objekt. Grundaren av det anses vara den berömda matematikern L. Euler.
Tillämpning av grafteori fram till slutet av 1800-taletkom till att lösa underhållande problem och väckte inte betydande allmän uppmärksamhet. Från 1900-talet, när grafteori bildades till en oberoende matematisk disciplin, fann den bred tillämpning inom sådana vetenskapsområden som cybernetik, fysik, logistik, programmering, biologi, elektronik, transport och kommunikationssystem.
Grundläggande begrepp i grafteori
Basen är en graf.I terminologin kan man stöta på ett sådant koncept som ett nätverk som är identiskt med en graf. Det senare är ett icke-tomt antal punkter, det vill säga vertikaler och segment, det vill säga kanter, vars båda ändar motsvarar ett givet antal punkter. Grafteori ger ingen mening i värdena på kanter och vertikaler. Till exempel städer och vägar som förbinder dem, där de förstnämnda är vertikorna i diagrammet, och de senare är revbenen. Bågarna ges större vikt i teorin. Om en kant har en riktning, har den namnet på en båge, om en graf med orienterade kanter kallas den en digraph.
I terminologin i teorin skiljs följande begrepp också:
En subgraf är ett diagram vars alla kanter och toppar är bland topp- och kanterna.
En ansluten graf är en med en kedja som förbinder dem för två olika vertikaler.
En viktad ansluten graf är en med en viktfunktion.
Ett träd är en ansluten graf utan cykler.
Ett skelett är en subgraf som är ett träd.
När du plottar en graf på ett planen viss notation: det valda toppmaterialet motsvarar en punkt på den enklaste ytan, och om det finns en kant mellan topparna, kopplas motsvarande punkter till av ett segment. Om grafen är orienterad ersätts dessa segment av pilar.
Men jämför inte bilden på grafen med denav oss själva, dvs med en abstrakt struktur, eftersom mer än en grafisk representation kan ges till en graf. Ritningen på planet ges för att se vilka par av toppar som är förenade med kanter och vilka inte.
Bland några problem med grafteori finns det:
- Uppgiften för den kortaste kedjan (utbyte av utrustning, placering av ambulanser och telefonväxlar).
- Problemet med maximalt flöde (effektivisering av trafik i ett dynamiskt nätverk, arbetsdistribution, bandbreddorganisation).
- Problemet med beläggningar och förpackningar (placering av kontrollcentra).
- Färgning i diagram (minnesallokering på elektroniska datorer).
- Kommunikationsnätverk och diagram (skapa ett kommunikationsnätverk, analys av kommunikationsnätverk).
Det är för närvarande omöjligt att programmera de flesta uppgifter utan kunskap om grafteori. Detta underlättar och förenklar arbetet med datorer.
Programmering använder många strukturer ochuniversella metoder för att lösa problem, och en av dem är grafteori. Dess värde är svårt att överskatta. Grafteori i programmering låter dig förenkla sökningen efter information, optimera program, konvertera och distribuera data. Tack vare algoritmerna i teorin blir det möjligt att använda och utvärdera dem för att lösa specifika problem, för att modifiera algoritmen utan att minska graden av matematisk tillförlitlighet för den slutliga versionen av programmet.
En viktig egenskap hos ett styrsystem eller modellär en uppsättning binära relationer i en uppsättning åtgärder och dataenheter. Dessa strukturer är de enda delarna av programmen och den information som de transformerar. Därför är grafer grunden för konstruktionen för programmeraren.
