Graph teori - det er en af de underafdelinger af matematik, den vigtigste funktion, som er den geometriske metode i studiet af objekter.Det anses for at være grundlæggeren af den berømte matematiker Euler.
Anvendelse af grafteori til slutningen af det 19. århundrede, blev reduceret til løsning af underholdende problemer og ikke tiltrække stor opmærksomhed.Siden det 20. århundrede, da grafteori blev dannet som en selvstændig matematisk disciplin, det har været meget anvendt inden for videnskab, Kybernetik, fysik, logistik, programmering, biologi, elektronik, transport og kommunikationssystemer.
Grundlæggende begreber grafteori
Base er Earl.Terminologien kan findes sådan noget som et netværk af identisk graf.Sidst - er en ikke-tom antal point, dvs. knuder og segmenter, dvs. kanter, begge ender svarer til et givet antal point.Grafteori ikke sætte en bestemt betydning til værdierne af kanter og hjørner.For eksempel byen og vejene forbinder dem, hvor det første - det er toppen af grafen, og den anden - ribbenene.Større betydning er givet til teorien om buerne.Hvis kanterne har en retning, kaldes den bue, hvis graf med orienterede kanter, kaldes det en digraf.
I terminologi af teorien om de samme begreber er følgende:
delgraf er en graf, alle kanter og hjørner er blandt de knudepunkter og kanter.
forbundet graf - en, der har to forskellige toppe eksisterer kæde forbinde dem.
vægtet forbundet graf - en, der indstilles vægtningen funktion.
træet - en tilsluttet graf uden cykler.
skelet - delgraf, som er et træ.
Når billedet af grafen på flyet ved hjælp af et specifikt notation: top svarer til det valgte punkt på overfladen af de enkleste, og hvis der er en kant mellem knudepunkter, er de tilsvarende punkter kombineret segment.Hvis grafen-orienterede, er disse segmenter erstattes med pilene.
Men det er ikke nødvendigt at sammenligne billedet af grafen med ham, dvs med en abstrakt struktur, fordi en optælling kan gives mere end en grafisk repræsentation.Tegning på flyet er givet med henblik på at se, hvilke par knuder kanter sammen, og hvilke ikke.
Blandt nogle problemer i teorien om grafer publicering:
- problem af den korteste kreds (udskiftning af udstyr, indkvartering steder ambulancer og telefoncentraler).
- maksimale flow problemet (bestilt bevægelse i et dynamisk netværk, arbejdsdeling, organisering af kapacitet).
- dækker problemet og pakker (indkvartering ekspeditionscentre).
- farvelægning i kolonner (allokering af hukommelse på elektroniske computere).
- Kommunikationsnet og grafer (et kommunikationsnet, analyse af kommunikationsnetværk).
er i øjeblikket ikke muligt at programmere de fleste opgaver uden kendskab til grafteori.Dette letter og forenkler arbejdet med en computer.
Program anvender en række strukturer og universelle metoder til at løse problemer og en af dem er teorien om grafer.Dens betydning er svært at overvurdere.Grafteori i programmeringen forenkler søgningen efter oplysninger, at optimere programmet, konvertere og distribuere dataene.Gennem teorien om algoritmer, der er mulighed for anvendelse og vurdering til brug for særlige opgaver, at foretage en ændring af algoritmen, uden at reducere graden af matematisk sikkerhed af den endelige version af programmet.
vigtigt træk af kontrolsystemet eller model er et sæt af binære forbindelser med det sæt af handlinger og dataenheder.Disse strukturer er den eneste del af programmet og konverterer dem information.Derfor graferne er grundlaget for design for programmøren.
