Grafteori - det är en av de underavdelningar i matematik, som är den viktigaste funktionen den geometriska metoden i studien av objekt.Det anses vara grundaren av den berömda matematikern Euler.
Tillämpning av grafteori till slutet av 19-talet, minskades till lösningen av underhållande problem och inte dra till sig betydande uppmärksamhet.Sedan 20-talet, när grafteori bildades som en oberoende matematisk disciplin, det har använts i stor utsträckning inom områdena vetenskap, cybernetik, fysik, logistik, programmering, biologi, elektronik, transport- och kommunikationssystem.
Grundläggande begrepp av grafteori
Base är Earl.Terminologin kan hittas en sådan sak som ett nätverk av samma graf.Sista - är en icke-tom antal poäng, det vill säga hörn och segment, dvs kanter, båda ändar som motsvarar ett visst antal poäng.Grafteori inte sätta en definitiv mening till värdena för kanter och hörn.Till exempel, staden och vägarna ansluter dem, där den första - det är den övre delen av grafen, och den andra - revbenen.Större vikt läggs vid teorin om bågarna.Om kanterna har en riktning, det kallas bågen, om grafen med orienterade kanter, kallas det en digraph.
I terminologi teorin om samma koncept är följande:
subgraf är en graf, alla kanter och hörn är bland de hörn och kanter.
anslutna grafen - en som har två olika toppar finns kedja som förbinder dem.
vägda anslutna grafen - en som sätter viktningsfunktionen.
träd - en ansluten graf utan cykler.
skelett - subgraf som är ett träd.
När bilden av grafen på planet med hjälp av en särskild notation: topp motsvarar den valda punkten på ytan av de enklaste, och om det finns en kant mellan hörnen är motsvarande punkter kombinerad segment.Om grafen-orienterade, är dessa segment ersätts av pilarna.
Men det är inte nödvändigt att jämföra bilden av grafen med honom, dvs med en abstrakt struktur, eftersom en starkare kan ges mer än en grafisk representation.Rita på planet ges för att se vilka par hörn kanter tillsammans och som inte är det.
Bland vissa problem i teorin om grafer Tillstånd:
- problemet med kortaste kretsen (byte av utrustning, boende platser ambulanser och telefonväxlar).
- maximalt flöde problem (ordnade rörelse i ett dynamiskt nätverk, arbetsfördelning, organisation av kapaciteten).
- täcker problem och paket (boende leveransanläggningar).
- färg i kolumnerna (minnesallokering för elektroniska datorer).
- Kommunikationsnät och grafer (ett kommunikationsnätverk, den analys av kommunikationsnät).
är för tillfället inte möjligt att programmera de flesta uppgifter utan kunskap om grafteori.Detta underlättar och förenklar arbetet med en dator.
Programmet använder en rad olika strukturer och universella metoder för att lösa problem och en av dem är teorin om grafer.Dess betydelse är svårt att överskatta.Grafteori i programmering förenklar sökandet efter information för att optimera programmet, konvertera och distribuera data.Genom teorin för algoritmer, finns det en möjlighet till applicering och bedömning som ska användas för specifika uppgifter, för att utföra en modifiering av algoritmen, utan att minska graden av matematisk säkerhet av den slutliga versionen av programmet.
viktigt inslag i styrsystemet eller modell är en uppsättning av binära förbindelser med rad åtgärder och dataenheter.Dessa strukturer är den enda delen av programmet och omvandlar dem information.Därför diagrammen är grunden för designen för programmeraren.
