Teorie grafů

Informatika
Obory informatiky
Programování
Matematická informatika
Teoretická informatika
Teorie složitosti
Umělá inteligence
Teorie grafů
Teorie informace
Informační technologie
Bioinformatika
Chemoinformatika
Geoinformatika
Lékařská informatika
Neuroinformatika
Sociální informatika
Informatici
Charles Babbage
Alan Turing
Donald Knuth
další...
Dějiny informatiky
Graf se šesti vrcholy

Teorie grafů je obor diskrétní matematiky, který zkoumá vlastnosti takzvaných grafů.

Graf je matematická struktura, definovaných 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 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 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ů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.

Jiné Jazyky
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
dansk: Grafteori
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
Bahasa Indonesia: Teori graf
íslenska: Netafræði
日本語: グラフ理論
한국어: 그래프 이론
lietuvių: Grafų teorija
latviešu: Grafu teorija
монгол: Графын онол
Bahasa Melayu: Teori graf
Nederlands: Grafentheorie
norsk nynorsk: Grafteori
norsk: Grafteori
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
srpskohrvatski / српскохрватски: Teorija grafova
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
svenska: Grafteori
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
中文: 图论
粵語: 圖論