Grafentheorie - is een van de subsecties van wiskunde, het belangrijkste kenmerk waarvan de geometrische methode in de studie van objecten.Het wordt beschouwd als de grondlegger van de beroemde wiskundige Euler zijn.
Toepassing van grafentheorie aan het eind van de 19e eeuw, werd gereduceerd tot de oplossing van problemen en onderhoudende niet veel aandacht trekken.Sinds de 20e eeuw, toen de grafentheorie werd opgericht als een onafhankelijke wiskundige discipline, het is op grote schaal gebruikt in het gebied van wetenschap, cybernetica, fysica, logistiek, programmering, biologie, elektronica, transport en communicatie systemen.
basisbegrippen van grafentheorie
Base is Earl.De terminologie kan worden gevonden zoiets als een netwerk van identieke grafiek.Last - een niet-lege aantal punten, namelijk hoekpunten en segmenten, dat wil zeggen randen beide uiteinden die overeenkomen met een bepaald aantal punten.Grafentheorie geen definitieve betekenis zet de waarden van randen en hoekpunten.Bijvoorbeeld, de stad en de wegen te verbinden, waarbij de eerste - is de top van de grafiek en de tweede - de ribben.Meer belang wordt gegeven aan de theorie van de bogen.Als de randen hebben een richting, wordt het genoemd de boog, als de grafiek met gerichte randen, is het een digraph genoemd.
In de terminologie van de theorie van dezelfde concepten zijn:
subgraaf is een grafiek, alle randen en hoekpunten tussen de hoekpunten en randen.
verbonden grafiek - een die heeft twee verschillende pieken bestaan keten te verbinden.
gewogen verbonden grafiek - een die de weging functie in te stellen.
boom - een aangesloten grafiek zonder cycli.
skelet - subgraaf dat is een boom.
Wanneer het beeld van de grafiek op het vliegtuig met een specifieke notatie: hoogste overeenkomt met het geselecteerde punt op het oppervlak van de eenvoudigste, en als er een rand tussen hoek, worden de overeenkomstige punten gecombineerde segment.Als de grafiek gericht, worden deze segmenten vervangen door de pijlen.
Het is niet nodig de afbeelding van de grafiek met hem, dwz een abstracte structuur te vergelijken, omdat een telling kan worden gegeven meerdere grafische weergave.Tekening op het vliegtuig wordt gegeven om te zien welk paar van hoekpunten samen randen en welke niet.
Bij sommige problemen in de theorie grafieken vrijgeven:
- probleem van de kortste circuit (vervanging van apparatuur, opvangplaatsen ambulances en telefooncentrales).
- maximale stroom probleem (besteld beweging in een dynamisch netwerk, de verdeling van het werk, de organisatie van de capaciteit).
- die probleem en arrangementen (accommodatie verzendingscentra).
- kleuring in de kolommen (toewijzing geheugen op elektronische computers).
- Communicatie netwerken en grafieken (een communicatienetwerk, de analyse van de communicatienetwerken).
is momenteel niet mogelijk om de meeste taken te programmeren zonder de kennis van de grafentheorie.Dit vergemakkelijkt en vereenvoudigt het werken met een computer.
programma gebruikt verschillende structuren en algemene methoden voor het oplossen van problemen en een daarvan is de theorie van grafieken.Het belang ervan is moeilijk te overschatten.Grafentheorie in de programmering vereenvoudigt het zoeken naar informatie, om het programma te optimaliseren, converteren en distribueren van de data.Door de theorie van algoritmen, is er een mogelijkheid van toepassing en beoordeling te gebruiken voor specifieke taken uitvoeren van een modificatie van het algoritme, zonder verminderen van de mate van wiskundige zekerheid van de laatste versie van het programma.
belangrijk kenmerk van het controlesysteem of model is een set van binaire relaties met de set van acties en data-eenheden.Deze structuren zijn het enige deel van het programma en zet deze informatie.Daarom zijn de grafieken zijn de basis van het ontwerp voor de programmeur.
