Teória grafov - Eulerovský graf

Autor: dispersus | 20.5.2011 o 16:51 | (upravené 20.5.2011 o 17:11) Karma článku: 9,25 | Prečítané:  3513x

Nebojte se, nebudu vás nudit žádnou nudnou teorií ani složitými definicemi, pokusím se vám jen ukázat, že teorie grafů je především velmi zajímavou disciplínou s mnoha možnostmi využití, a to nejen ve vědě, ale i v praktickém životě.

Jistě jste se v minulosti pokoušeli řešit různé úkoly, kde bylo cílem nakreslit obrázek jedním tahem. Většina z nás takové úkoly řešila metodou „pokus - omyl", tedy zkoušeli jsme různé možnosti, dokud se nám nepovedlo obrázek nakreslit nebo dokud jsme v záchvatu zuřivosti nezahodili zmuchlaný počmáraný papír do kouta. Přitom by stačilo pouze znát pojem Eulerovský graf a vědět, jak takový graf poznat. Tak bychom mohli hned po prohlédnutí zadaného obrázku určit, zda je možné jej nakreslit jedním tahem nebo jestli se raději máme zabavit jinak. Pro správné pochopení pojmu si neodpustím jednu jednoduchou definici:

„Eulerovským grafem nazýváme každý graf, který je souvislý (to znamená, že z každého vrcholu lze po hranách dojít do libovolného jiného vrcholu) a platí pro něj, že z každého vrcholu vychází sudý počet hran, nebo že existují právě dva vrcholy, z nichž vychází lichý počet hran."

Vyzkoušejte si, jestli už umíte poznat, které grafy jsou Eulerovské a je možné je nakreslit jedním tahem. Pro usnadnění jsou vrcholy označeny červeně:

1.JPG

 

(správné řešení: 1. ano, 2. ne, 3. ano, 4. ne)

Eulerovské grafy, u nichž z každého vrcholu vychází sudý počet hran, můžete začít kreslit odkudkoliv, ale grafy, které mají dva vrcholy s lichým počtem hran, musíte začít kreslit od jednoho z těchto vrcholů.

S tímto tématem souvisí velmi zajímavý problém, který se nazývá Sedm mostů města Královce. Problém je inspirován skutečným městem, které se nyní nazývá Kaliningrad a leží v Rusku. Máme zadánu mapu města, na níž je zakresleno sedm mostů. Úkolem je projít všechny mosty a přitom vstoupit na každý právě jednou.

 

2.JPG

 

První obrázek znázorňuje zjednodušenou mapu města, která je na druhém obrázku překreslena do grafu. Díky pojmu eulerovský graf jste nyní schopni sami během chvilky spočítat hrany vycházející z jednotlivých vrcholů a rozluštit tak hádanku, se kterou si spousta matematiků lámala hlavu řadu let, a vyřešil ji až Leonhard Euler, který je považován za jednoho z nejlepších matematiků na světě - právě po něm je pojmenován eulerovský graf.

Další zajímavý problém z teorie grafů se nazývá problém čtyř barev. Zadání je následující: „Stačí čtyři barvy na obarvení libovolné politické mapy tak, aby žádné dva sousedící státy nebyly obarveny stejnou barvou?" Tento problém je mnohem složitější než předchozí. K jeho důkazu, který byl podán až roku 1976 Američany Kennethem Apelem a Wolfgangem Hakenem, bylo potřeba vytvořit počítačový program, který vygeneroval všechny možné konfigurace mapy, dokázal, že tyto vygenerované konfigurace pokrývají opravdu všechny případy, a potom jednotlivě pro každý případ dokázal, že čtyři barvy stačí. Problémem tohoto důkazu je to, že některými matematiky nebyl přijat, protože není v lidských silách zkontrolovat jeho správnost. Jiný důkaz, který by byl matematik schopen zkontrolovat, ještě nalezen nebyl, proto musíme věřit pouze počítačovým programům (nebo se můžete pokusit tento důkaz nalézt sami). Do teorie grafů se tento problém snadno převede tak, že státy převedeme na vrcholy a ty státy, které spolu sousedí, spojíme hranou (státy, které spolu sousedí pouze v jednom bodě, nepovažujeme za sousedy). V praxi je na tomto principu založeno například rozhodování telefonních operátorů, kolik frekvencí budou používat, nebo se s jeho pomocí vyrábějí elektronické součástky (mezi uzly obarvenými stejnou barvou nevzniká žádné spojení) a uplatňuje se i v chemii.

Na následující mapě si můžete vyzkoušet obarvení evropských států. Ostrovní státy můžete zanedbat, protože nejsou součástí souvislého grafu.

3.JPG

Martina_Horakova.JPG

 

 

 

 

 

 

Martina Horáková

Step Out of Range

Informácie a perličky zo sveta analytiky a vedy  - facebook- klub dispersus

 


 

Literatúra:

http://cs.wikipedia.org/wiki/Eulerovsk%C3%BD_graf

http://cs.wikipedia.org/wiki/Eulerovsk%C3%BD_tah

http://en.wikipedia.org/wiki/Eulerian_path

http://www.austincc.edu/powens/+Topics/HTML/05-6/05-6.html

http://mathworld.wolfram.com/EulerGraph.html

Páčil sa Vám tento článok? Pridajte si blogera medzi obľúbených a my Vám pošleme email keď napíše ďalší článok
Pridaj k obľúbeným

Hlavné správy

DOMOV

Minúta po minúte: Fico na sneme opäť útočil aj na médiá

Vo funkcii podpredsedov skončia Dušan Čaplovič a Pavol Paška.

DOMOV

Odhalila kauzu predsedníctva. Odkiaľ prišla Zuzana Hlávková?

Gymnázium, ktoré navštevovala, jej plánuje vyjadriť verejnú podporu.

EKONOMIKA

RegioJet skracuje svoje vlaky do Košíc, na prevádzku má málo vozňov

Jazdiť bude len so siedmimi vozňami.


Už ste čítali?