Hledej Zobraz: Univerzity Kategorie Rozšířené vyhledávání

11 917   projektů
25 nových

Teorie grafů - poznámky

«»
Přípona
.doc
Typ
poznámky
Stažené
0 x
Velikost
0,4 MB
Jazyk
český
ID projektu
4579
Poslední úprava
18.11.2014
Zobrazeno
522 x
Autor:
northfinder
Facebook icon
Detaily projektu
Popis:
Teorie grafů
Historie
Tradičně se za zakladatele teorie grafů považuje Leonhard Euler, který roku 1736 řešil úlohu, jak projít přes sedm mostů v Königsbergu (každý z nich právě jednou) a vrátit se do výchozího místa. To v moderní teorii odpovídá pojmu eulerovský graf.
V roce 1845 publikoval Gustav Kirchhoff zákony, které platí v elektrických obvodech a slouží k výpočtu napětí a proudu v jednotlivých větvích obvodu. V teorii grafů našly své uplatnění při studiu tzv. toků v sítích.

V roce 1852 předložil Francis Guthrie takzvaný problém čtyř barev - tedy otázku, zda je možné obarvit libovolnou mapu pomocí nejvýše čtyř barev tak, aby každé dvě sousední země (které mají společnou hranici delší než jediný bod) měly odlišnou barvu. Byl vyřešen až o více než sto let později, přičemž pro jeho řešení bylo zavedeno mnoho zásadních konceptů teorie grafů (viz rovinný graf).

Klíčová slova:

graf

užití

vlastnosti

isomorfismus

reprezentace grafu

symetrizace

strom



Obsah:
  • Historie
    Základní pojmy
    Užití
    Vlastnosti grafů
    Rozdělení grafů
    Důležité typy grafů
    Reprezentace grafu
    Isomorfismus grafů
    Symetrizace
    Strom
    Rovinný graf
    Kostra grafu
    Úlohy