Skip to main content

Teorie grafů Historie | Úlohy | Externí odkazy | Navigační menuJava appletyTeorie grafůGraph Theory with ApplicationsGraph TheoryGraph Theory Software4113782-67164sh85056471lccn-sh85056471

Multi tool use
Multi tool use

Teorie grafůDiskrétní matematikaSíťová analýza


diskrétní matematikymnožinouvrcholůmnožinouhrandélkumapudálnicekroužkyúsečkyroviněuspořádanou dvojicí18. stoletíLeonhard Eulersedm mostů města Královcevědních oborůdopravypočítačových sítíchorientovanou hranouLeonhard Euler1736jak projít přes sedm mostůKrálovcieulerovský graf1845Gustav Kirchhofftoků v sítích1852Francis Guthrieproblém čtyř barevpolitickou mapurovinný grafPála TuránaPála Erdőseextremální teorie grafůRamseyova teorieeulerovského grafuNP-úplných












Teorie grafů




Z Wikipedie, otevřené encyklopedie






Skočit na navigaci
Skočit na vyhledávání



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 Gdisplaystyle G uspořádanou dvojicí množiny vrcholů Vdisplaystyle V a množiny hran Edisplaystyle E:



G=(V,E)displaystyle G=left(V,Eright).

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ů 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 |




Eulerovský uzavřený tah dle Fleuryho algoritmu. Začneme v kterémkoliv vrcholu a do tahu postupně přidáváme hrany tak, aby se podgraf dosud nevybraných hran nerozpadl na dvě části.


Mezi nejpopulárnější úlohy patří jednotažk 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.


Externí odkazy |



  • Logo Wikimedia Commons Obrázky, zvuky či videa k tématu teorie grafů ve 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


.mw-parser-output div/**/#portallinks afont-weight:bold









Citováno z „https://cs.wikipedia.org/w/index.php?title=Teorie_grafů&oldid=17117812“










Navigační menu


























(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.260","walltime":"0.375","ppvisitednodes":"value":982,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":18378,"limit":2097152,"templateargumentsize":"value":3563,"limit":2097152,"expansiondepth":"value":10,"limit":40,"expensivefunctioncount":"value":0,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":483,"limit":5000000,"entityaccesscount":"value":1,"limit":400,"timingprofile":["100.00% 289.823 1 -total"," 38.09% 110.388 1 Šablona:Informatika"," 36.62% 106.119 1 Šablona:Soubox"," 26.54% 76.920 1 Šablona:Autoritní_data"," 22.60% 65.506 13 Šablona:Vseznam"," 20.96% 60.740 1 Šablona:Commonscat"," 10.84% 31.405 1 Šablona:Operační_výzkum"," 9.62% 27.869 1 Šablona:Navbox"," 3.13% 9.063 1 Šablona:Portály"," 2.99% 8.665 1 Šablona:Velké"],"scribunto":"limitreport-timeusage":"value":"0.069","limit":"10.000","limitreport-memusage":"value":1596945,"limit":52428800,"cachereport":"origin":"mw1238","timestamp":"20190416181317","ttl":2592000,"transientcontent":false););"@context":"https://schema.org","@type":"Article","name":"Teorie grafu016f","url":"https://cs.wikipedia.org/wiki/Teorie_graf%C5%AF","sameAs":"http://www.wikidata.org/entity/Q131476","mainEntity":"http://www.wikidata.org/entity/Q131476","author":"@type":"Organization","name":"Pu0159ispu011bvatelu00e9 projektu016f Wikimedia","publisher":"@type":"Organization","name":"nadace Wikimedia","logo":"@type":"ImageObject","url":"https://www.wikimedia.org/static/images/wmf-hor-googpub.png","datePublished":"2004-09-21T20:32:48Z","dateModified":"2019-04-06T05:07:54Z","image":"https://upload.wikimedia.org/wikipedia/commons/5/5b/6n-graf.svg"(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgBackendResponseTime":133,"wgHostname":"mw1250"););irIR bSPRFtfoim4PndhM5RDW,c,eXfLH8a,LgUQ2lTp2qK1,PaRRFS6EZ1lBI 6FgwC
7CAC UNxtmB8eQ9OtiVw2S0LzqKPBEhlonhNjlm,65eG96iQAVYOUYKNDn03yAad4yGi58y

Popular posts from this blog

Creating centerline of river in QGIS? The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Finding centrelines from polygons in QGIS?Splitting line into two lines with GRASS GIS?Centroid of the equator and a pointpostgis: problems creating flow direction polyline; not all needed connections are drawnhow to make decent sense from scattered river depth measurementsQGIS Interpolation on Curved Grid (River DEMs)How to create automatic parking baysShortest path creation between two linesclipping layer using query builder in QGISFinding which side of closest polyline point lies on in QGIS?Create centerline from multi-digitized roadway lines Qgis 2.18Getting bathymetric contours confined only within river banks using QGIS?

What is the result of assigning to std::vector::begin()? The Next CEO of Stack OverflowWhat are the differences between a pointer variable and a reference variable in C++?What does the explicit keyword mean?Concatenating two std::vectorsHow to find out if an item is present in a std::vector?Why is “using namespace std” considered bad practice?What is the “-->” operator in C++?What is the easiest way to initialize a std::vector with hardcoded elements?What is The Rule of Three?What are the basic rules and idioms for operator overloading?Why are std::begin and std::end “not memory safe”?

Typsetting diagram chases (with TikZ?) Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)How to define the default vertical distance between nodes?Draw edge on arcNumerical conditional within tikz keys?TikZ: Drawing an arc from an intersection to an intersectionDrawing rectilinear curves in Tikz, aka an Etch-a-Sketch drawingLine up nested tikz enviroments or how to get rid of themHow to place nodes in an absolute coordinate system in tikzCommutative diagram with curve connecting between nodesTikz with standalone: pinning tikz coordinates to page cmDrawing a Decision Diagram with Tikz and layout manager