Teorie grafů

Teorie grafů je jedním z podsekcí matematiky, jehož hlavní charakteristickou vlastností je geometrická metoda ve studiu předmětů. Jeho zakladatel je považován za slavný matematik L. Euler.

Použití teorie grafů až do konce 19. století bylo omezeno na řešení zábavných problémů a nepřineslo významnou obecnou pozornost. Od 20. století, kdy se teorie grafů vyvinula do nezávislé matematické disciplíny, se v širokých oblastech vědy nacházela jako kybernetika, fyzika, logistika, programování, biologie, elektronika, dopravní a komunikační systémy.

Základní pojmy teorie grafů

Graf je základní. V terminologii se člověk může setkat s takovouto koncepcí jako se sítí shodnou s grafem. Posledním z nich je neprázdný počet bodů, tj. Vrcholy a segmenty, tj. Okraje, jejichž oba konce odpovídají danému počtu bodů. Teorie grafů nedělá určitý smysl pro hodnoty okrajů a vrcholů. Například města a silnice, které je spojují, kde první jsou vrcholy grafu a druhý - okraje. Teoretická důležitost je dána obloukům. Pokud má okraj směr, pak má název oblouku, pokud je graf s orientovanými okraji, nazývá se digraph.

V terminologii teorie vyniká také následující koncepce:

Subgraph je graf, všechny hrany a vrcholy patří mezi vrcholy a hrany.

Připojený graf je ten, který má řetězec spojující je pro dva různé vrcholy.

Vážený připojený graf je graf, jehož hmotnostní funkce je dána.

Strom je připojený graf bez cyklů.

Kostra je subgraf, který je strom.

Když je graf nakreslen na rovině, použije se určitá notace: vybraný vrchol odpovídá bodu na nejjednodušším povrchu a pokud je mezi vrcholy hranou, příslušné body jsou spojeny segmentem. Pokud je graf orientován, jsou tyto segmenty nahrazeny šipkami.

Ale nemají porovnat graf obraz s ním, tedy s abstraktní struktury, protože jeden graf lze podávat více než jednu grafickou reprezentaci. Kreslení v rovině je uvedeno, aby bylo vidět, které dvojice vrcholů jsou spojeny okraji a které nejsou.

Mezi některé problémy teorie grafů patří:

1. Úloha nejkratšího řetězce (výměna zařízení, umístění ambulance a telefonních stanic).
2. Problém maximálního průtoku (objednávání pohybu v dynamické síti, distribuce práce, organizace kapacity).
3. Úloha povlaků a balení (umístění dispečinků).
4. Barvení grafů (umístění paměti v elektronických počítačích).
5. Komunikace sítí a grafů (vytváření komunikační sítě, analýza komunikačních sítí).

V současné době není možné programovat většinu problémů bez znalosti teorie grafů. To usnadňuje a usnadňuje práci s počítačem.

Programování využívá spoustu struktur a univerzálních metod pro řešení problémů a jedna z nich je teorie grafů. Jeho hodnota je obtížně přeceňována. Teorie grafů v programování usnadňuje hledání informací, optimalizaci programů, konverzi a distribuci dat. Díky algoritmům teorie je možné je aplikovat a vyhodnotit při jejich použití pro řešení konkrétních problémů, modifikovat algoritmus bez snížení stupně matematické jistoty finální verze programu.

Důležitou vlastností řídícího systému nebo modelu je kolekce binární vztahy při psaní akcí a datových jednotek. Tyto struktury jsou jedinou součástí programů a informace, které převádějí. Grafy jsou proto základem konstrukce pro programátora.