A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/220px-6n-graf.svg.png)
Teorie grafů je obor diskrétní matematiky, který zkoumá vlastnosti takzvaných grafů.
Graf je matematická struktura, definovaná množinou vrcholů a množinou hran, kde každá hrana je určena povinně dvěma vrcholy a volitelně směrem nebo váhou („cenou“); váha může odrážet např. délku, náklady na přesun nebo průchodnost. Graf si lze dobře představit jako mapu, na které vrcholy představují města a hrany představují dálnice, přičemž každá z těchto dálnic přímo spojuje dvě města. Grafy, jimiž se demonstruje smysl teorie grafů, se znázorňují zpravidla jako kroužky (reprezentace vrcholů) a úsečky (reprezentace hran) mezi těmito kroužky v rovině. Formálně je graf uspořádanou dvojicí množiny vrcholů a množiny hran :
- .
Původ teorie grafů sahá až do 18. století, kdy její zakladatel Leonhard Euler řešil úlohu sedm mostů města Královce.
Jedním z hlavních cílů teorie grafů je poskytnout aparát, jímž je možné vyjadřovat vzájemné „vzdálenosti“ (vzdálenosti v širším slova smyslu) jednotlivých dvojic vrcholů. Výsledkem je model reálné sítě.
Na problém teorie grafů lze formalizovat problémy z nejrůznějších vědních oborů i praktického života. Příkladem z první kategorie je analýza dopravy [1] nebo provozu v počítačových sítích, z druhéhou soudku lze uvést kupř. strukturu vzájemného propojení článků Wikipedie – jednotlivé články jsou vrcholy grafu a odkaz z článku A na článek B je orientovanou hranou mezi vrcholy A a B.
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 Královci (každý z nich právě jednou) a vrátit se do výchozího místa. To v moderní teorii odpovídá pojmu nazvaném podle zakladatele oboru 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 politickou 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).
Práce Pála Turána, Pála Erdőse a dalších maďarských matematiků ve čtyřicátých a padesátých letech dvacátého století vedly ke vzniku extremální teorie grafů. S extremální teorií grafů úzce souvisí Ramseyova teorie.
Úlohy
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d8/Euler_Circuit_K5.gif/220px-Euler_Circuit_K5.gif)
Mezi nejpopulárnější úlohy patří jednotažky eulerovského grafu.
Velké množství úloh z teorie grafů je NP-úplných, mezi nimi např.:
- hledání největšího úplného podgrafu – tzv. problém kliky,
- hledání největší nezávislé množiny,
- problém obchodního cestujícího.
Z dalších je to například
- problém čtyř barev,
- hledání minimální kostry grafu.
Úlohy z teorie grafů lze využít i v průmyslové logistice [2], technologii obrábění (řešení pořadí operačních úseků), či technologii montáže (pořadí činností při montáži, vyvažování montážních linek, optimalizace montáže).
Reference
- ↑ Preclík Vratislav: Průmyslová logistika, 359 s., ISBN 80-01-03449-6, Nakladatelství ČVUT v Praze, 2006
- ↑ Preclík Vratislav: Průmyslová logistika, 359 s., ISBN 80-01-03449-6, Nakladatelství ČVUT v Praze, 2006, str.63 - 73, 75 - 85, 298 - 349
Externí odkazy
Obrázky, zvuky či videa k tématu teorie grafů na Wikimedia Commons
- Java applety demonstrující některé algoritmy z teorie grafů
- Teorie grafů – bakalářská práce z MFF UK zabývající se historií teorie grafů a úvodem, obsahuje základní definice, vybrané problémy a algoritmy včetně animací a kódů v Pascalu
- Graph Theory with Applications – J. A. Bondy, U.S.R. Murty: Graph Theory with Applications, Springer 2008 – monografie
- Graph Theory – R. Diestel: Graph Theory, Springer 2005 – monografie
- Graph Theory Software Archivováno 13. 3. 2013 na Wayback Machine.
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antény
Chemické zdroje elektriny
Chladenie v elektrotechnike
Elektrická sústava automobilu
Elektrická trakcia
Elektrické prístroje
Elektrické súčiastky
Elektrické spotrebiče
Elektrické stroje
Čítanie (elektrotechnika)
Činný výkon
Štatistická dynamika
Živý vodič
Admitancia
Antiparalelné zapojenie
Asynchrónny motor
Blúdivý prúd
Bočník (elektrotechnika)
Diak (polovodičový prvok)
Displej s kvapalnými kryštálmi
Elektrická inštalácia
Elektrická rezonancia
Elektrická sila
Elektrická vodivosť
Elektrické zariadenie
Elektrický obvod
Elektrický zvonec
Elektroenergetika
Elektromer
Elektrometer
Elektromobil
Elektromotor
Elektromotorické napätie
Elektrotechnický náučný slovník
Elektrotechnika
Elektrotechnológia
Fázor
Faradayova klietka
Frekvencia (fyzika)
Graetzov mostík
Impedancia
Indukčnosť
Induktancia
Istič
Izolácia (elektrotechnika)
Izolant
Jadro vodiča
Jednobran
Jednosmerný prúd
Joulovo teplo
Katóda
Koaxiálny kábel
Kompenzácia účinníka
Konduktometria
Konektor (elektrotechnika)
Korónový výboj
Lanko (elektrotechnika)
Leptanie
Logické hradlo
Magnetická susceptibilita
Magnetizácia (veličina)
Merný elektrický odpor
Mobilné zariadenie
Napájací zdroj
Napäťový chránič
Napäťový násobič
Nortonova veta
Odpínač
Odpojovač
OLED
Olovený akumulátor
Paralelné zapojenie
Peltierov článok
Plošná hustota elektrického prúdu
Poistka (elektrotechnika)
Posuvný prúd
Prúdový chránič
Prenosové médium
Prieletový klystrón
Primárny elektrochemický článok
Reaktancia
Rekuperácia (dopravný prostriedok)
Relé
Reproduktorová výhybka
Rezistancia
Rozhranie (interface)
Sériové zapojenie
Seebeckov jav
Sekundárny elektrochemický článok
Settopbox
Skrat
Sonar
Spínač
Spínaný zdroj
Straty v mikropásikových vedeniach
Striedavý prúd
Stupeň ochrany krytom
Svetelná výbojka
Symetrizačný člen
Technická normalizácia
Tepelné relé
Tepelne vodivostný detektor
Termočlánok
Théveninova veta
Transformátor
Transformátor s fázovou reguláciou
Trojfázová sústava
Tuhá fáza (elektronika)
Tyratrón
Usmerňovač (elektrotechnika)
Uzemnenie
Uzol (vodiče)
Vírivý prúd
Výbojka
Varistor
Ventilátor
Vodič (elektrotechnika)
Voltov stĺp
Vstavaný systém
Zásuvka (elektrotechnika)
Zdroj (elektrotechnika)
Zisk antény
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk