Grafteori er et af underafsnittene.matematik, hvis vigtigste kendetegn er den geometriske metode i studiet af objekter. Grundlæggeren af det betragtes som den berømte matematiker L. Euler.
Anvendelse af grafteori indtil slutningen af det 19. århundredekom ned til at løse underholdende problemer og tiltrak ikke betydelig generel opmærksomhed. Fra det 20. århundrede, da grafteori blev dannet til en uafhængig matematisk disciplin, fandt den bred anvendelse inden for områder af videnskab som cybernetik, fysik, logistik, programmering, biologi, elektronik, transport og kommunikationssystemer.
Grundlæggende begreber i grafteori
Basen er en graf.I terminologi kan man støde på et sådant koncept som et netværk, der er identisk med en graf. Det sidstnævnte er et ikke-tomt antal point, det vil sige knudepunkter og segmenter, det vil sige kanter, hvor begge ender svarer til et givet antal point. Grafteori giver ingen mening i værdierne på kanter og hjørner. For eksempel er byer og veje, der forbinder dem, hvor de første er grafhjørnerne, og den anden er kanterne. Teorier får større betydning i teorien. Hvis en kant har en retning, har den navnet på en bue, hvis en graf med orienterede kanter, kaldes den en digraph.
I teoriens terminologi skelnes der også følgende begreber:
En undergraf er en graf, hvis alle kanter og hjørner er blandt toppunktene og kanterne.
En tilsluttet graf er en med en kæde, der forbinder dem til to forskellige hjørner.
En vægtet tilsluttet graf er en med en vægtfunktion.
Et træ er en tilsluttet graf uden cykler.
Et skelet er en undergraf, der er et træ.
Når der tegnes en graf på et planen bestemt notation: det valgte toppunkt svarer til et punkt på den enkleste overflade, og hvis der er en kant mellem toppunktene, forbindes de tilsvarende punkter af et segment. Hvis grafen er orienteret, erstattes disse segmenter med pile.
Men sammenlign ikke billedet af grafen med detaf os selv, dvs. med en abstrakt struktur, fordi mere end en grafisk repræsentation kan gives til en graf. Tegningen på planet er givet for at se, hvilke par af hjørner, der er forbundet med kanter, og hvilke der ikke er.
Blandt nogle problemer med grafteori er der:
- Opgaven med den korteste kæde (udskiftning af udstyr, placering af ambulancer og telefoncentraler).
- Problemet med maksimal flow (strømlining af trafik i et dynamisk netværk, arbejdsdistribution, båndbreddeorganisation).
- Problemet med overtræk og emballering (placering af kontrolcentre).
- Farve i grafer (hukommelsesallokering på elektroniske computere).
- Kommunikationsnetværk og grafer (oprettelse af et kommunikationsnetværk, analyse af kommunikationsnetværk).
Det er i øjeblikket umuligt at programmere de fleste opgaver uden kendskab til grafteori. Dette letter og forenkler arbejde med computere.
Programmering bruger mange strukturer oguniverselle metoder til løsning af problemer, og en af dem er grafteori. Dets værdi er vanskelig at overvurdere. Grafteori i programmering giver dig mulighed for at forenkle søgningen efter information, optimere programmer, konvertere og distribuere data. Takket være algoritmerne i teorien bliver det muligt at bruge og evaluere dem til brug for at løse specifikke problemer, til at ændre algoritmen uden at reducere graden af matematisk pålidelighed af den endelige version af programmet.
En vigtig egenskab ved et kontrolsystem eller modeler et sæt binære relationer i et sæt handlinger og dataenheder. Disse strukturer er de eneste dele af programmer og den information, de transformerer. Derfor er grafer grundlaget for konstruktionen for programmereren.
