No title

INFORMATIKA GeoGebra { vce ne dynamick geometrie LUK HONZK { MIROSLAV TICH Fakulta pedagogick ZU v Plzni, Stedn kola aplikovan kybernetiky Hradec Kr lov

; vod

Pojem dynamick geometrie ) bv spojovn pedevm s programem Cabri Geometry pvodn vyvinutm ve Francii v Institutu pro aplikace informatiky a matematiky (IMAG), vzkumn m pracoviti Univerzity Josepha Fouriera v Grenoble. Mnoho kol zkladnch i stednch vlastn aspo jednu licenci pro uitele, mnoh z nich zakoupily multilicenci tak, aby tento program mohli pouvat i ci. V tomto lnku chceme pedstavit alternativu ke Cabri, program GeoGebra, a ukzat na jeho zajmav algebraick vlastnosti, kter v jinch prostedch dynamick geometrie nenajdete. ) Prosted dynamick geometrie (DGE, dynamical geometry environment), aplikace slou c k rychlmu a pesnmu r sov n geometrick ch gur podle z sad konstruk n geometrie. Obsahuj n stroje pro pohyb, umo uj manipulaci s hotovou gurou, m a v sledky v po t opt v konstrukcch pou vaj. Pedstaviteli jsou nap. software Cabri Laborde, 1994], Sketchpad Jackiw, 1991], Cinderella Richter-Gebert, 1999], Geonext Bauch, 2003], Geogebra, Euklides, Cabri 3D de Cotret, 2006]. (Van ek 7])

426

Matematika - fyzika - informatika 19 2009/2010

GeoGebra

Autorem a prvnm tvrcem tohoto programu je Rakuan Markus Hohenwarter, kter jej od potku vyvj jako Open Source program v jazyku Java. Zaal ho vyvjet jet jako student univerzity v Salzburku v roce 2001, pozd ji jako doktorand. Pracuje na n m dle i pi sv m psoben na americk univerzit , vvojov tm je dnes u pochopiteln ir. Program za dobu sv existence zskal adu ocen n a grant, kter napomhaj jeho dalmu vvoji. GeoGebra je zajmavou alternativou komernch program i proto, e stle rostouc komunita jejch pznivc vytv celou adu materil a aplikac pro rzn oblasti kolsk matematiky. M vlastn webov strnky http://www.geogebra.org, odkud je ada t chto materil dostupn, mnoho dalch strnek s pklady pro tento program vytv na Internetu jeho dal uivatel .

Pednosti a nedostatky programu

Prosted programu m, jak uvidme, n kolik vhod. Prvn vhodou ne nepodstatnou pro kolsk prosted je jeho dostupnost. Jak bylo uvedeno ve, program je od potku vyvjen jako Open Source. Je tedy zdarma dostupn uitelm, km i jejich rodim , komukoli, kdo m o program zjem. GeoGebra m bt, jak vyplv u z jejho nzvu, jakmsi spojovnkem mezi programy dynamick geometrie a programy typu CAS (Computer Algebra System). Sluuje n kter vhody obou typ program, umouje vyuvat jak grackou, tak i algebraickou reprezentaci geometrickch objekt, kombinovat pstupy k nim, i kdy samotn algebraick matematick programy (Derive, Mathematica a dal) peci jen neme plnohodnotn nahradit. Vhodn zvlt pro ky je, e pokud mme zobrazeno algebraick i geometrick okno programu, vidme jak analytick popis tvar, se ktermi pracujeme, tak i jejich geometrick umst n v rovin , vztahy mezi t mito tvary. I pes nesporn vhody, kter jsme zde vyjmenovali, m GeoGebra i n kolik nedostatk. Mezi n meme zaadit napklad m n pesn vykreslovn kivek, pomalost objevujc se zvlt pi v tm mnostv objekt na nkresn i n kter chyb jc nstroje { kupkladu nstroj dovolujc uivateli uv st jeden nebo i vce objekt do pohybu (znm v prosted Cabri, kde je symbolizovan pruinkou) zde neexistuje. Dalm nedoMatematika - fyzika - informatika 19 2009/2010

427

statkem je tak nemonost prce s polorovinami a jejich prniky nebo sjednocenmi. Navc se pi prci s jednm souborem na vce potach me objevit zmizen n kterch objekt, tento probl m se tk hlavn textovch pol.

Ukzka prosted programu

Nejprve ukeme monosti prce programu, jeho grack prosted. Standardn pracuje s dv ma okny { algebraickm a geometrickm. Ukeme rzn monosti denovn krunice. V geometrick m okn lze krunici denovat pomoc nstroje pro vytvoen krunice jejm stedem a jednm bodem lecm na jejm obvodu (obr. 1).

;;; ; ; Obr. 1 Kru nice sestrojen dynamicky

V algebraick m okn vidme souadnice bod a rovnici vznikl krunice. Budeme-li pohybovat bodem S nebo bodem B , krunice, jej rovnice i souadnice bod se budou dynamicky m nit. Budeme-li tut lohu eit algebraickm pstupem, zadme rovnou v pkazov m dku programu krunici jej rovnic:

k : (x ; 3)2 + (y ; 2)2 = 8:

U krunice se tentokrt nezobraz jej sted (obr. 2), ale je stle dynamick, taenm bodu na jejm obvodu se posouv cel krunice a pochopiteln se v algebraick m okn m n i jej rovnice. Krunici lze m nit 428


i poklepnm na jej rovnici, tu pak lze upravit a zm ny se ihned promtnou v geometrick m okn . Sted krunice je mon zskat i (zobrazit) pkazem S = Stred k] zadanm na pkazov m dku programu.

;;; ; ; Obr. 2 Kru nice sestrojen algebraicky

Tetm zpsobem zadn, kter kombinuje oba pedel , je zadat krunici takto: S = (3, 2) B = (5, 4) k: Kruznice S, B]

Pkaz lze pochopiteln zkrtit, nepotebujeme-li uveden body: k: Kruznice (3, 2), (5, 4)].

A! pouijeme kteroukoliv z metod vzniku krunice, vdy s n lze snadno dle pracovat. Chceme-li sestrojit nap. teny z vn jho bodu, sta pout tlatko zvrazn n na panelu nstroj (obr. 3).

Vlastnosti programu GeoGebra

Nyn, po t to krtk ochutnvce, se podvejme na zkladn vlastnosti tohoto programu. Matematika - fyzika - informatika 19 2009/2010

429

{ Program je lokalizovn, lze v n m nastavit esk menu i npov du. Klov slova pkaz jsou tak lokalizovna, nepouvme tedy nap. OsculatingCircle, ale OskulacniKruznice.

; ; ; Obr. 3 Kru nice a jej te ny

{ Pi zpisu text, vzorc, nzv prom nnch a funkc lze pouvat doln i horn indexy. Zpis f 1 zobraz jako f1 , zatmco zpis x^3 zobraz jako x3 . To vede k lep itelnosti a srozumitelnosti funknch pedpis. V textu je tak povolena syntaxe vzorc jazyka LaTeX, co umouje vytvet popisy vetn znak pro sumu, integrl apod. { GeoGebra je vzhledov podobn ostatnm programm dynamick geometrie. M podobnou strukturu menu, prci s (jedinm) panelem nstroj. Co je vzhledov odlin a pro funkci a pouit programu velmi podstatn , je algebraick okno, v n m se objevuj souadnice bod, pedpisy funkc, hodnoty konstant a prom nnch, rovnice kivek. Vechny zde uveden objekty lze dle editovat, upravovat jejich vlastnosti, m nit barvu, typ ry, monosti zobrazen objektu, i nastavovat stopu objekt pi jejich pohybu. { Lze vytvet vlastn makroinstrukce a doplovat si tak dal vlastn nstroje do panelu nstroj. { Objekty lze, pokud je to z jejich charakteru mon , zadvat jak geometricky, jejich vytvoenm v geometrick m okn , tak i algebraicky, zpisem jejich rovnice do algebraick ho okna. $daje v obou oknech se 430


{ { {

{

{

neustle dynamicky ovlivuj. Mme-li nap. dn bod F a pmku d, meme pkazem Parabola F, d] vytvoit parabolu urenou ohniskem F a dic pmkou d. Parabola se ihned vykresl v geometrick m okn a v algebraick m okn se objev jej rovnice. Krunici lze zadat n kolika zpsoby geometricky (nap. stedem a jednm bodem, temi body apod.), lze ji zadat rovnic ve stedov m i obecn m tvaru. Jej rovnice se objev v algebraick m okn vdy ve stedov m tvaru. Pomoc posuvnk lze vytvet animace, nastavit i velikost jejich kroku. Ppadn lze pomoc zakrtvacch polek ovlivovat zobrazen nebo skryt vybranch objekt. Program um pracovat s vektory, stat je, potat jejich skalrn souin. Krom analytick geometrie um GeoGebra i mnoho z matematick analzy, m tak blzko k programm CAS. Um potat derivace, hledat primitivn funkce pro vechny b n funkce. Jak derivace, tak neurit integrly pitom hled symbolicky, nikoliv numericky. U polynomickch funkc um hledat jejich extr my. Podstatnou vlastnost prosted programu je jednoduchost a intuitivnost jeho ovldn a prce s nm. Program se po krtk m seznmen lb i km, slou jim nejprve k snadn mu a pesn mu sestrojovn graf funkc. Vyuij ho pi planimetrickch konstrukcch, pi vpotech v analytick geometrii i v diferencilnm a integrlnm potu. Uitel i k maj irok pole psobnosti od vytven a upravovn vlastnch dynamickch geometrickch gur ) a po experimentovn s ji hotovmi demonstranmi pklady pevzatmi z Internetu.

Pklady

Na n kolika pkladech ukeme monosti programu GeoGebra. Nebudeme se a tolik zabvat b nmi pklady, kter bvaj eeny klasickmi programy pro dynamickou geometrii, ale zvolme hlavn pklady, kter ukou specick monosti vyuvajc jeho algebraickch schopnost. Mezi jednoduch pklady, kter zvldaj i dynamick geometrick softwary, meme zaadit napklad poadavek nalezen kolmice k dan pmce prochzejc danm bodem. ) Po ta ov geometrick gura - mno ina objekt (geometrick ch obrazc, sel, textov ch pol, ) zobrazen ch na n kresn v programu dynamick geometrie majc na rozdl od statickho obr zku mo nost dynamick zmny vztah mezi sv mi jednotliv mi stmi. :::


431

Pklad 1 { Analytick dkaz kolmosti dvou sestrojench pmek

Zadn: Je dna pmka p a bod A, kter na n nele. Euklidovsky zkonstruujte kolmici k pmce p, kter prochz bodem A. Analyticky (vpotem) dokate, e dan dv pmky jsou skuten navzjem kolm . een: Je zejm , e pro takto jednoduchou lohu bude existovat nstroj dostupn v nabdce nstroj. Navc meme vhodn vyut pkazov dek, do n ho zadme pkaz Kolmice A, p]. $kolem je vak zkonstruovat tuto kolmici euklidovsky, m je myleno pomoc krunic a pmek, ne jednm pedpipravenm pkazem. Meme tedy postupovat napklad tak, e sestrojme krunici c majc za sted bod A protnajc pmku p ve dvou bodech (obr. 4). Zde musme dt pozor, aby polom r krunice pevyoval vzdlenost v(A p), toho vak jednodue doshneme teba zapsnm pkazu r 1 = Vzdalenost A, p] + 2. Dan krunice pak na pmce p vytvo dva prseky (body B , C ). Oba takto vznikl body pouijeme jako stedy pro krunice se shodnm polom rem (ten mus tentokrt bt v t ne polovina vzdlenosti v(B C ), vezm me tedy tuto vzdlenost v(B C ) jako nov polom r). Prseky vzniklch dvou krunic ji uruj hledanou kolmici k.

;; ; Obr. 4 Euklidovsky zkonstruovan kolmice k pmce

Poslednm kolem je analytick ov en, e sestrojen pmka k je opravdu kolm k pmce p. Vyuijeme pkazu pro zskn hodnot normlov ho (nebo sm rov ho) vektoru pmek a provedeme jejich souin souin = NormalovyVektor p] * NormalovyVektor k] (ppadn meme pout pkaz SmerovyVektor %]). Vsledek tohoto souinu vyjde 0 a jeliko skalrn souin dvou libovolnch nenulovch vektor je roven nule prv 432


tehdy, kdy jsou na sebe tyto vektory kolm , je zejm , e zskan pmka

k je skuten kolm na zadanou pmku p.

Nakonec jet zmime monost vnoen a et zen pkaz vkldanch pes pkazov dek, kter je uiten , chceme-li n kolik malch krok vm stnat do kroku jedin ho. Napklad na potku een nemusme nejprve zavd t prom nnou r 1, pak konstruovat krunici c a nakonec zji!ovat jej prseky s pmkou p. Toto ve meme zahrnout do jedin ho pkazu Prusecik Kruznice A, Vzdalenost A, p] + 2], p]. Uijeme-li tento postup, zobraz se pouze vsledn objekt (v tomto ppad pouze prseky B a C ), ne vak objekty objevujc se v mezikrocch (pijdeme tak o hodnotu r 1 i o krunici c). Je zejm , e obdobn pstup, kdy bychom zadali jeden sloen pkaz a dostali rovnou pouze vsledek, se d vhodn pout k een nejedn lohy, ale z hlediska pehlednosti a sloitosti takov ho pkazu (dosti asto by se toti jednalo o pkazy pom rn dlouh a komplikovan ) je nutn zvit ppadn pozitiva i negativa takov ho pstupu. Napklad v pedchoz loze lo pedevm o ukzku euklidovsk konstrukce, ne pmo o vslednou kolmici, kterou bychom dostali daleko jednodum pouitm ji ve zmn n ho pkazu Kolmice A, p]. (Pokra ovn) Literatura 1] Hohenwarter, M. { Preiner, J.: GeoGebra Help 3.0 : Ocial Manual. 2007. 73 s. Dostupn z WWW: http://www.geogebra.org/help/docuen.pdf . 2] Hohenwarter, M. { Hohenwarter, J.: Introduction to GeoGebra. 2008. 69 s. 3] GeoGebra online]. 2001{ ]cit. 2008-11-02]. Dostupn z WWW: http://www.geogebra.org/cms/ . 4] Voick, Z.: Matematika v kostce pro stedn koly (Fragment). Havl kv Brod 1999. 5] Vejsada, F. { Talafous, F.: Sbrka "loh z matematiky pro gymn zia. SPN, Praha 1969. 6] Burjan, V. { Maxian, M. { Beneov , K.: Opakov n z matematiky pro tdy gymn zi se zamenm na matematiku. SPN, Praha 1991. 7] Van ek, J.: Po ta em podporovan v uka geometrie (dizerta n pr ce). Pedagogick fakulta UK, Praha 2001. 8] Van ek, J.: Po ta ov kognitivn technologie ve v uce geometrie. 2009. V tisku. 9] Edwards, J. A. { Jones, K.: Linking Geometry and Algebra with Geogebra. Mathematics Teaching no. 194, 2006. <

<

>

>


433

Prohledvn graf do ky: hledn krunic s danmi vlastnostmi EVA MILKOV Katedra informatiky a managementu, Univerzita Hradec Kr lov

'eme-li lohu na grafu a potebujeme-li systematicky projt a zpracovat (prov st poadovan operace) vechny vrcholy (resp. hrany) dan ho grafu jeden po druh m tak, aby kad vrchol (resp. hrana) byl zpracovn prv jednou, pouijeme k tomu n jak vhodn algoritmus prohledvn grafu. K t m nejznm jm a nejast ji pouvanm algoritmm pat algoritmus prohledvn grafu do hloubky a algoritmus prohledvn grafu do ky. Zmn n algoritmy prohledvn lze dle vhodn modikovat a zskvat een rznch probl m z oblasti teorie graf. Pouit algoritm prohledvn je skuten irok . V lnku Modi kace algoritm aneb od Jarnka k prohledvn (viz %1]) jsme formulovali algoritmy prohledvn do hloubky a do ky jako modikace algoritmu Vojtcha Jarnka na nalezen minimln kostry grafu, abychom zdraznili, e pi prohledvn do hloubky a do ky podle takto formulovanch algoritm tvome souasn kostru grafu pslunou dan mu prohledvn. V tomto lnku se podvme detailn ji na prohledvn grafu do ky, na vlastnosti stromu prohledvn do ky a z nich plynouc tvrzen vhodnch pro formulaci algoritm tkajcch se hledn krunic s danmi vlastnostmi. Nejprve formulujme algoritmus prohledvn do ky jako proces barven vrchol a hran.

Algoritmus prohledvn do ky

Nech! je dn souvisl graf G = (V E ) s n vrcholy a m hranami a nech! vrchol v je libovoln vrchol mnoiny V . $kolem je systematicky zpracovat vechny vrcholy a hrany grafu G. zatek na potku nech je graf G neobarven. Zpracuj vrchol v,

434


obarvi jej mode (povaujeme jej za modr strom) a vlo do fronty FIFO. dokud nen FIFO przdn opakuj zatek x : = vrchol lec na prvnm mst ve front FIFO jestlie x je koncovm vrcholem neobarven hrany {x,y} pak jestlie hrana {x,y} se dotk modrho stromu (tj. y je neobarven) pak zatek zpracuj vrchol y, obarvi jej mode a vlo do fronty FIFO zpracuj hranu {x,y} a obarvi ji mode konec jinak (tj. vrchol y je ji obarven mode) zpracuj hranu {x,y} a obarvi ji erven jinak (tj. x nen koncovm vrcholem dn nezpracovan (neobarven) hrany) odeber x z fronty FIFO konec konec.

Poznmka: Hrana se dotk modr ho stromu, jestlie m jeden koncov vrchol v modr m stromu a druh nikoli. Hran, kter se dotkaj modr ho stromu ve vrcholu x, me bt vce. V tom ppad volbu hrany fx yg k obarven mode (zaazen do modr ho stromu) provedeme podle n jak ho pedem dohodnut ho pravidla, nap. lexikogracky (vzhledem k abecednmu poad vrchol). Ilustrujme uveden algoritmus na grafu G v obr. 1.

; Obr. 1


435

; ;

Zaneme-li prohledvn grafu G do ky ve vrcholu c, budou vrcholy zpracovny v poad c a d f e b g, piem bude konstruovna modr kostra (obr. 2).

Obr. 2

Obr. 3

a kdy ji zobrazme (obr. 3) jako koenov strom s koenem c, dostaneme strom prohledvn do ky pslun prohledvn grafu G do ky s potkem prohledvn ve vrcholu c. Uveden ilustrace shrme do nsledujc denice. Denice: Nech! G = (V E ) je souvisl graf, T jeho modr kostra zskan algoritmem prohledvn grafu G do ky se zatkem prohledvn ve vrcholu v. Koenov strom (T v) s koenem ve vrcholu v nazvme strom prohledvn do ky pslun prohledvn grafu G do ky s potkem prohledvn ve vrcholu v (dle jen strun { strom prohledvn do ky).

; ; Obr. 4

436

Obr. 5


Uvaujme nyn nsledujc rozshlej graf na obrzku 4 a aplikujme na n j prohledvn do ky s potkem ve vrcholu s. Jeho strom prohledvn do ky (T s) (jeden z monch) je na obr. 5 a po dopln n ervench hran (vyznaench slabou rou), kter nepat do stromu (T s), dostvme pvodn graf z obr. 4 avak ve tvaru zobrazen m na obr. 6.

; Obr. 6

Vta (vlastnost stromu prohledvni do ky): Nech! G = (V E ) je souvisl graf, T jeho modr kostra zskan algoritmem prohledvn vrchol grafu G do ky se zatkem prohledvn ve vrcholu v a (T v) pslun strom prohledvn do ky. Pak pro koncov vrcholy libovoln erven hrany grafu G plat, e tyto vrcholy le ve stejn vrstv nebo v sousednch vrstvch stromu (T v). Poznmka: sousednmi vrstvami stromu (T v) mme na mysli i-tou a (i + 1)-n vrstvu, i 2 f0 1 : : : h ; 1g, kde h je hloubka stromu (T v). Dkaz: Nech! fx yg je libovoln neobarven hrana grafu G a pedpokldejme, e vrchol y byl zaazen do fronty (do kostry T ) pozd ji ne vrchol x (v opan m ppad bychom postupovali analogicky). Nech! x le ve vrstv i, i 2 f0 1 : : : h ; 1g, stromu (T v). Je zejm , e vrcholy zaazen do T pozd ji ne vrchol x le ve vrstv j , kde j i, a vrcholy zaazen do T dve ne byl vrchol x odebrn z fronty le zejm ve vrstv j , kde j i + 1. Dle pedpokladu, a protoe vrchol y je sousednm vrcholem Matematika - fyzika - informatika 19 2009/2010

437

vrcholu x v grafu G, plat pro n j oba uveden vztahy, tj. i j i + 1, co znamen, e vrchol y le v i-t nebo (i + 1)-n vrstv . Podvejme se pozorn na obr. 6 a polohu ervench hran sledujme jednak vzhledem k vrstvm stromu (T s) a jednak vzhledem k podstromm stromu (T s) urenm pmmi nslednky vrcholu s, tj. sledujme ti podstromy, podstrom s koenem ve vrcholu q, podstrom s koenem ve vrcholu c a podstrom s koenem ve vrcholu d. Co lze zjistit? 1) Pi pohledu na jednotliv vrstvy vidme, e dn erven hrana neme zkrtit cestu, kter vede ve stromu prohledvn do ky z koene, tj. z vrcholu s, do n jak ho vrcholu y dan ho grafu, to znamen, e d lka nejkrat cesty mezi vrcholy s a y je rovna d lce cesty mezi vrcholy s a y ve stromu prohledvn s koenem s (cest nejkrat d lky mezi vrcholy s a y me bt vce). 2) Dle vidme, e hrana, kter spojuje vrcholy lec ve stejn vrstv , uruje krunici lich d lky, co je dleit informace pro uren, zda dan graf je nebo nen bipartitn. Poznmka: Krunice d lky k v grafu G je posloupnost (v0 e1 v1 : : : e v0 ), kde e = fv ;1 v g, i = 1 : : : k ; 1, e = fv ;1 v0 g a v 6= v 8 6= . Graf, jeho mnoinu vrchol meme rozd lit do dvou mnoin V1 a V2 tak, e kad hrana grafu m jeden koncov vrchol v mnoin V1 a druh v mnoin V2 , nazvme bipartitnm grafem. A plat v ta: Graf G je bipartitn prv tehdy, kdy v grafu G neexistuje krunice lich d lky. 3) Pi pohledu na jednotliv podstromy stromu (T s) zskme informaci, zda koen s le na n jak krunici, co pi pohledu po vrstvch zjistit nelze. Vidme, e dky hran fp ag a t dky hran fa og, kter ob maj koncov vrcholy v rznch podstromech, je zejm , e v dan m grafu krunice obsahujc vrchol s existuj, naopak u ostatnch ervench hran majcch oba vrcholy v t me podstromu je vid t, e uruj krunice, kter vrchol s neobsahuj. 4) Spojme-li v vahch oba pohledy, pak je zejm , e z krunic obsahujcch vrchol s je krunice (s c g a o m d s) nejkrat mon d lky. Je to dno tm, e dn hrana s vrcholy v rznch podstromech, kter by leela v i-t vrstv , kde i < 3, neexistuje, piem vrcholy hrany fa og k

i

438

i

i

k

k

i

j

i

j


le oba v 3. vrstv , kdeto vrcholy hrany fp ag le v sousednch vrstvch, 3. a 4. vrstv , a tud hrana fp ag uruje krunici o jednu hranu del. 5) Obdobn meme zjistit, zda hrana incidentn s vrcholem s (tj. hrana obsahujc vrchol s) le na krunici, a pokud ano, jak je d lka nejkrat takov krunice. Tuto skutenost vak meme zjistit i jinm, jednodum zpsobem, kter uvedeme v zv ru tohoto lnku. Proveden pozorovn shrme do nsledujcch ty tvrzen. Tvrzen 1: Nech! G je souvisl graf a (T v) jeho koenov strom prohledvn do ky. Pak d lka nejkrat cesty z vrcholu v do vrcholu y v grafu G je rovna h(y), kde h(y) zna slo vrstvy, ve kter le vrchol y. Poznmka: Nejkrat cestou z vrcholu x do vrcholu y rozumme tu cestu mezi t mito vrcholy, kter m minimln poet hran. Nap. d lka nejkrat cesty v grafu na obrzku 4 mezi vrcholy s a a je rovna 3 a jednou z takovch nejkratch cest je cesta (s c g a) ve stromu prohledvn do ky na obrzku 5. Tvrzen 2: Nech! G je souvisl graf a (T v) jeho koenov strom prohledvn do ky. Pak graf G obsahuje kru nici lich d lky prv tehdy, kdy v grafu G existuje erven hrana s koncovmi vrcholy lecmi ve stejn vrstv stromu (T v). Tvrzen 3: Nech! G je souvisl graf a (T v) jeho koenov strom prohledvn do ky. Pak v grafu G existuje kru nice obsahujc vrchol v prv tehdy, kdy v grafu G existuje erven hrana s koncovmi vrcholy lecmi v rznch podstromech stromu (T v). Tvrzen 4: Nech! G je souvisl graf a (T v) jeho koenov strom prohledvn do ky. Pak v grafu G existuje kru nice obsahujc hranu fv wg prv tehdy, kdy v grafu G existuje erven hrana, jej jeden koncov vrchol le v podstromu s koenem w a druh v podstromu s koenem z , kde z je pm nslednk vrcholu v a z 6= w. Na zklad vyslovench tvrzen lze ji pom rn snadno popsat algoritmy na nalezen krunice lich d lky, nalezen nejkrat krunice v grafu (tzv. obvodu grafu), zjit n, zda v grafu existuje krunice obsahujc dan vrchol (nalezen nejkrat takov krunice), zjit n, zda v grafu existuje krunice obsahujc danou hranu (nalezen nejkrat takov krunice), zjit n, zda Matematika - fyzika - informatika 19 2009/2010

439

v grafu existuje krunice lich d lky obsahujc dan vrchol. Uve*me pro pedstavu alespo n kter z nich. Dal algoritmy si jist ten ji doke na zklad uvedench informac sestavit sm. Ve vech dle popsanch algoritmech pedpokldme, e pracujeme se souvislm grafem.

1. Zjitn, zda v grafu existuje krunice lich dlky

V grafu vybereme libovoln vrchol v a provedeme z n j prohledvn do ky, piem pro kad vrchol y si ukldme informaci h(y) (tj. slo vrstvy, ve kter vrchol y le) a u erven hrany zji!ujeme, ve kterch vrstvch le jej koncov vrcholy. Jakmile v grafu najdeme ervenou hranu, kter m oba vrcholy v t e vrstv stromu prohledvn do ky s koenem v, ukonme innost algoritmu se sd lenm, e v grafu existuje krunice lich d lky. Pokud dn erven hrana tuto vlastnost nem, je zejm , e v grafu krunice lich d lky neexistuje (a tud dan graf je bipartitn).

2. Zjitn, zda se dan vrchol nachz na krunici

Provedeme prohledvn do ky, piem prohledvn zaneme v zadan m vrcholu v, o kter m mme zjistit, zda le nebo nele na n jak krunici. Vrcholm, kter soused s vrcholem v, piadme postupn sla 1 : : : p, kde p je poet t chto sousednch vrchol, a povaujeme je za koeny podstrom ve stromu prohledvn do ky s koenem v. Pak u kad ho vrcholu y ukldme slo podstromu stejn , jako m jeho pedchdce. Pokud v grafu existuje erven obarven hrana, pro jej koncov vrcholy plat, e le v rznch podstromech stromu prohledvn do ky s koenem v, pak krunice, do n nle vrchol v, existuje. V opan m ppad nikoli.

3. Zjitn, zda dan hrana le na krunici

Postupujeme obdobn jako v pedchozm ppad . Nech! fx yg je zadan hrana. Prohledvan vrchol a hran do ky zaneme ve vrcholu x, a sledujeme, zda v grafu existuje erven obarven hrana, pro kterou plat, e jeden jej vrchol le v podstromu s koenem y a druh vrchol v n jak m jin m podstromu. Pokud takov hrana existuje, pak krunice obsahujc danou hranu fx yg existuje. V opan m ppad nikoli. Ve vech tech ve uvedench ppadech plat, e chceme-li navc nalezen krunice i vypsat, je nutno ukldat pro kad vrchol y t informaci o tom, kter vrchol je jeho pedchdce ve stromu prohledvn do ky. Na zv r, jak jsme slbili, popeme jin zpsob uren, zda dan hrana fx yg le na krunici a v ppad , e ano, jak je nejkrat takov krunice. 440


Op t vyuijeme prohledvn do ky a vlastnost stromu prohledvn do ky.

4. Zjitn, zda dan hrana fx yg le na krunici { jednodu zpsob Z dan ho grafu G odebereme hranu fx yg a v grafu G ; fx yg provedeme prohledvn do ky z vrcholu x do vrcholu y. Pokud v grafu G ; fx yg existuje cesta z x do y, pak jsme nali nejkrat cestu, kter spolu s hranou fx yg tvo hledanou krunici nejkrat d lky v grafu G. Literatura 1] Milkov , E.: Modikace grafov ch algoritm (od Jarnka k prohled v n). MFI r. 11 (2001/02), . 6.

ZKU ENOSTI Zkuenosti z Hulna V tvarnk Mgr. Petr Stejskal, u itel matematiky, informatiky a v tvarn v chovy na Z# v Huln, se neboj posadit nkdy sv ky pi hodin v tvarn v chovy k po ta i s tm, e maj realizovat njak v tvarn projekty. $ ci tak spojuj svou v tvarnou fantazii s rozvjenm techniky pr ce na po ta i. Tak teba ped velikonocemi zdobili ci kraslice a poslaj n m do MFI tento pozdrav (origin ly jsou barevn): Hulnsk Z kladn kola se vak m e pochlubit i veejn m "spchem. Mikroregion Ji n Han vyhl sil v minulm roce sout na vytvoen n vrhu na sv logo. Clem sout e bylo zapojit mladou generaci do innosti v mikroregionu, vybudovat v n soun le itost nejen ke sv rodn

; ; ; ;


Obr. 1 Kraslice

441

obci i mstu, ale i k ostatnm lenm svazku { okolnmu regionu. Hlavnm smyslem bylo nalezen a zv raznn prvk region ln identikace, kter by v jednoduchm grackm vyj den vytv ely logo svazku { Mikroregionu, a n sledn tmto logem propagovat Mikroregion jako celek mezi ob any { veejnost. Sout e se z" astnili ci z kladnch kol ze ty okolnch obc. Jejich "kolem bylo vytvoit jednoduch a srozumiteln logo s drazem na vizu ln slo ku, n paditost a pou itelnost. Logo mlo mt nejen dostate nou informa n hodnotu, ale i jeho vizu ln podoba mla odpovdat sou asn m modernm trendm. V hulnsk Z# aktivizovala ky k " asti v sout i i v tvarnice Mgr. Ilona Herodesov . Selo se celkem 37 sout nch n vrh, kter hodnotila Rada svazku. Mikroregionu Ji n Han a na prvnch tech mstech se umstili ci pana u itele Stejskala. Uv dme jejich obr zek v edm proveden:

; ; ;

; ; ; Obr. 4 Tet cena

Obr. 5 Logo Z# Huln

Celkov vtz sout e Michal Charv t (nyn z 9. tdy) navc zvtzil i v sout i o logo koly (viz obr. 5). A co je novho u v s ve kole?

Redakce

Obr. 2 Prvn cena

Obr. 3 Druh cena

442


Z HISTORIE Vzpomnka na esk ho v dce a staten ho vlastence { profesora Frantika Zviku

; ; ; Frantiek Z vika

Dnes je jen v "zk ch odborn ch kruzch zn mo jmno zcela v jime n osobnosti esk vdy univ. prof. PhDr. Frantika Z viky, od jeho narozen v roce 2009 uplynulo 130 let. Poch zel z Moravy, kde se narodil ve Velkm Mezi 18. listopadu 1879 do nepli majetn ch pomr. Po z kladn kole a gymn ziu (v Teb i a Brn) za al v roce 1898 studovat na Filozock fakult esk Karlo-Ferdinandovy univerzity v Praze matematiku a fyziku (i kdy rodi e by z nho b vali radji mli knze). Po tvrtm semestru studi (1910) odeel jako asistent svho oblbenho u itele

prof. F. Kol ka na nov zzenou eskou vysokou kolu technickou do Brna. Profesor se po roce vr til zpt do Prahy, ale Z vika zstal do konce kol. roku 1902/3, proto e Kol ek pro nj neml pi stolici teoretick fyziky voln asistentsk msto. Z Brna dokon il v roce 1903 univerzitn studia (obhajobou pr ce z fyzik ln optiky) a nabyl u itelsk zpsobilosti vyu ovat (jazykem esk m) matematice a fyzice na vych gymn zich.

V dal karie vak dal pednost nejist se r sujc vdeck dr ze ped existen nmi jistotami povol n stedokolskho profesora. Koncem roku 1903 se vr til zpt do Prahy, a koliv dosti o systematizovan asistentsk msto pi stolici teoretick fyziky na pra sk esk univerzit zst valy st le nevyslyeny. Pomohl vak profesor experiment ln fyziky . Strouhal, kter Z vikovi nabdl msto v pomocnho asistenta v tamnm Fyzik lnm "stavu. Za petrv vajcch provizornch pomr se Z vika ve kol. roce 1906/7 vydal na zkuenou do zahrani . Za msto studijnho pobytu nakonec zvolil Cavendishovu laborato na Univerzit v Cambridgi, kde se pod vedenm erstvho nositele Nobelovy ceny za fyziku profesora Sira J. J. Thomsona zab val studiem kondenza nch pomr ve Wilsonov ml n komoe. Po n vratu za al konat docentsk pedn ky (habilitoval se jet ped odjezdem) a po tkem roku 1908 byl kone n ustanoven asistentem. Po v nm onemocnn a poslze "mrt prof. Kol ka (1913) byl Z vika poven suplov nm v uky teoretick fyziky, v roce 1914 byl jmenov n mimo dn m a v roce 1919 dn m profesorem teoretick fyziky na Prodovdeck fakult Univerzity Karlovy, kde byl editelem &stavu pro teoretickou fyziku a ve kol. roce 1926/7 dkanem.


443

Prvn vdeck pr ce F. Z viky spadaj do oblasti optiky. Zab vaj se z experiment lnho i teoretickho hlediska tot lnm odrazem svtla na anizotropnch l tk ch, pedevm dvouos ch krystalech. Do oblasti optiky pslu i Z vikova pr ce o odrazu svtla na kovech (1931), dl charakter maj jeho pr ce o vlivu rentgenovho z en na kondenzaci vodnch par ve Wilsonov ml n komoe (1909), o Hallov jevu (1912) a dv z hydrodynamiky o obtk n v lc visk'zn kapalinou (1929). St ejn skupina celkem devti Z vikov ch prac z let 1912 a 1939 pojedn v o problematice vlnovod: na z klad Maxwellov ch rovnic eil problm en elektromagnetick ch vln v prostoru s vodiv mi, resp. nevodiv mi v lci, trubicemi i jejich kombinacemi. A koli dos hl ady pvodnch v sledk, jeho publikace, a tm i z sluhy, ve sv dob zapadly { pi publikaci pev n v esk ch periodik ch { a unikly pozornosti svtov veejnosti. Znovuobjeveny a experiment ln potvrzeny byly a pozdji, s rozvojem techniky velmi kr tk ch elektromagnetick ch vln. V letech 1901 a 1914 spolupracoval na vyd v n Pehled pokroku fyziky v publikacch esk akademie vd a umn, kter upozorovaly eskou fyzik ln obec na problmy sou asn fyziky. Z jem ir odborn veejnosti upoutala Z vikova popul rn kniha Einsteinv princip relativnosti a teorie gravita n (1925) a obrana svho relativistickho stanoviska proti nkter m sv m kolegm, zejmna profesorm V. Posejpalovi (tvrci modelu svtovho teru) a B. Hostinskmu. Roku 1933 vyla Z vikova u ebnice Mechanika a roku 1943 Thermodynamika. V roce 1951 vydal prof. M. Brdika v Prodovdeckm nakladatelstv z pozstalosti jeho Kinetickou theorii plyn. Z vika bhem svho pedagogickho psoben na Prodovdeck fakult zaa-

444

zoval do fyzik lnch pedn ek modern partie { teorii relativity, kvantovou mechaniku, kinetickou teorii plyn aj. Mezi jeho nejzn mj ky patili nap. fyzik ln chemik a objevitel polarograck analytick metody J. Heyrovsk a cukrovarnick odbornk, editel V& cukrovarnickho a gener ln editel Masarykovy akademie pr ce K. andera. Stal se dn m lenem esk ch vdeck ch spole nost (esk akademie vd a umn, Kr lovsk esk spole nosti nauk), psobil jako redaktor asopisu pro pstov n matematiky a fyziky a inovnk Jednoty esk ch matematik a fyzik. Ml tak plno soukrom ch z jm { byl v niv automobilista, r d fotografoval, pstoval s man elkou a kolegy p turistiku, miloval jzdu na kole, tenis, plav n aj. Po tek druh svtov v lky zastihnul profesora Z viku na prahu estho desetilet ivota: oslava jeho narozenin se vak ji odehr vala v ponur atmosfe obsazov n naich vysok ch kol nmeck mi okupanty. Pes svoje mezin rodn uzn van vdeck renom byl vzhledem k dlouhodb nezastranmu negativnmu postoji k okupantm a pro podezen z " asti v odboji 21. ledna 1944 zat en gestapem, vznn nejdve v Praze a v Kounicov ch kolejch v Brn, a poslze transportov n do koncentra nch t bor Mauthausen a Osterode-Harz. Zemel na samm sklonku v lky vyslen "plavic, nkolik dn po osvobozen 17. dubna 1945 v Gifhornu u Braunschweigu. Tak zst v pouze vzpomnka na zbyte n zmaen ivot a ped asn ukon en dlo state nho vlastence, v znamnho vdce a vysokokolskho u itele, kter pom hal budovat mezin rodn vhlas esk fyziky v prvn polovin minulho stolet.

Bohumil Tesak


ZPRVY

; ;

Praemium Bohemiae 2008 { 2009 studentm

Dne 4. prosince 2009 byly v divadle st tnho z mku Sychrov udleny studentm presti n ceny Praemium Bohemiae. Jak byli ten i naeho asopisu informov ni v minul ch ro nicch, ceny udluje Nadace Bohuslava Jana Hor ka eskmu r ji z "rok nan nch prostedk, kter poch zej z celo ivotnho podnik n jejho zakladatele, mecen e Bohuslava Jana Hor ka. Ceny se udluj v den v ro narozen mecen e { na leton rok pipadly 85. Prvn ceny Praemium Bohemiae byly udleny v roce 2001 jet za " asti zakladatele. V loskm roce ceny nemohly b t z procesnch dvod udleny, nebo( vrcholilo ddick zen po smrti don tora v roce 2002, a to arbitr nm soudem v Lond n. Nadace se rozhodla letos ceny udlit rovn zptn, a proto byly ceny udleny za roky 2008 a 2009. V "vodu slavnosti promluvili ke studentm, jejich rodi m a u itelm a ostatnm hostm pedseda Nadace Mgr. Frantiek Hor ek a pedstavitel vdy v esk

republice: pedsedkyn U en spole nosti R prof. RNDr. Helena Illnerov , DrSc., mstopedseda tto spole nosti RNDr. Ji Grygar, CSc., pedseda Rady vdeck ch spole nost R prof. MUDr. Ivo H na, CSc. a pedseda JMF doc. RNDr. tefan Zajac, CSc. Svtov prodovdn olympi dy ve fyzice, chemii, biologii, matematice a informatice a evropskou sout EUSO pedstavil prof. Ing. Bohumil Vyb ral, CSc. z Univerzity Hradec Kr lov. Kvalitn hudebn program zaji(ovali ci ZU# v Turnov pod vedenm Mgr. Jaroslavy Nvltov, kter rovn slavnost udlen cen dila. Kritriem pro udlen cen Praemium Bohemiae 2008 a 2009 studentm byly jejich medailov "spchy na svtov ch olympi d ch v letech 2008 a 2009. Mezin rodn fyzik ln olympi da 2008, v poad ji 39., se konala v Hanoji ve Vietnamu a " astnilo se j 376 student z 81 st t vech kontinent. Naich 5 student dos hlo vynikajcho "spchu ziskem 2 zlat ch a 1 stbrn medaile. Nejlep n sout n fyzik Dalimil Maz zskal cenu Praemium Bohemiae ji r. 2007, a to rovn za zlatou medaili { tehdy v )r nu. V roce 2009 se konala v Mexiku, ve st t Yucat n, jubilejn 40. Mezin rodn fyzik ln olympi da, kter se z" astnilo 316 sout cch z 68 st t (men po et st t a sout cch byl ovlivnn obavou z prase chipky, kterou tam vak nikdo z asi 600 " astnk neonemocnl). Naich 5 student dovezlo z Mexika 5 medail: 2 stbrn a 3 bronzov. Chemie mla r. 2008 ji 40. ro nk mezin rodn olympi dy* sout se konala v Ma+arsku za " asti 261 student z 67 st t, pi em 4 et studenti vybojovali 3 medaile: 2 stbrn a 1 bronzovou. Roku 2009 se v Cambridge ve Velk Britanii konala 41. Mezin rodn chemick olympi da. Nai 4 studenti tentokr t zskali 4 me-


445

daile: 1 stbrnou a 3 bronzov. Biolo- 20. ro nk a hostil ji Egypt v K hie. gie mla r. 2008 v Indii 19. mezin rodn Olympi dy se z" astnilo 283 sout cch

olympi du, kterou hostilo msto Mumbai. Olympi dy se z" astnilo 220 student z 55 st t. Nai 4 reprezentanti pivezli 4 medaile: 3 stbrn a 1 bronzovou. Jubilejn 20. ro nk Mezin rodn biologick olympi dy 2009 po dalo Japonsko ve mst Tsukuba. Z" astnilo se j 221 sout cch z 56 st t a et 4 studenti opt pivezli 4 medaile: tentokr t 3 stbrn a 1 bronzovou.

; ; ;

Nejspnj esk sout c Dalimil Maz (dv zlat medaile: na MFO v r nu a Vietnamu)

Nejstar a nejrozs hlej mezin rodn olympi da { matematick { mla v r. 2008 ji 49. ro nk. Konala se ve panlskm Madridu za " asti 535 sout cch z 97 st t vech kontinent. #esti lenn esk dru stvo bylo "spn. Nai matematici pivezli 2 medaile: 1 stbrnou a 1 bronzovou. Jubilejn 50. mezin rodn MO zorganizovalo Nmecko v Brm ch. Z" astnil se j rekordn po et 565 sout cch ze 104 zem. Nai pivezli 3 medaile: 1 stbrnou a 2 bronzov. Mezin rodn olympi da v informatice mla roku 2008

446

ze 78 st t* 4 et reprezentanti pivezli 2 stbrn medaile. 21. Mezin rodn olympi du v informatice v r. 2009 mlo na starosti Bulharsko, kter ji uspo dalov Plovdivu. Z" astnilo se j 312 student z 82 zem. Nai 4 studenti pivezli 3 medaile: 2 stbrn a 1 bronzovou. Roku 2009 Nadace udlila rovn 3 mimo dn ceny Praemium Bohemiae, a to t lennmu eskmu t mu za excelentn v kon, kter v evropsk sout i EUSO dos hl absolutnho vtzstv. Tato sout integrovan zahrnuje fyziku, chemii a biologii a mohou se j z" astnit studenti do 17 let vku. Jeden ze dvou esk ch t m v konkurenci 40 t m z EU dos hl r. 2009 v Madridu absolutnho vtzstv a zskal zlat medaile. Cen Praemium Bohemiae v kategorii pro studenty bylo v roce 2009 udleno celkem 36 v celkov v i 470 tisc K (podle "spchu { kovu medaile vybojovan na sout i { byly ceny 30 tisc K za zlatou, 15 tisc K za stbrnou a 10 tisc K za bronzovou medaili* mimo dn ceny byly 10 tisc K ). Ocenn ch student bylo mn, 31, proto e ti vybojovali medaile jak v roce 2008, tak 2009 a dva se "spn z" astnili dvou rzn ch olympi d v tm e roce. Krom nan n ceny studenti dostali rovn medaili Bohuslava Jana Hor ka (rovn z kovu, kter odpovdal zskan medaili) a k tomu diplom. Nadace udlila od po tku v roce 2001 celkem 187 cen Praemium Bohemiae v kategorii pro studenty v celkov v i 3,5 milion K . Cena Praemium Bohemiae v kategorii pro vdce v roce 2009 udlena nebyla. Z uvedenho pehledu je zejm, e esk reprezentace na poli vdy je tradi n v razn efektivnj ne ve sportu, i kdy ji st t ve srovn n se sportem podporuje velmi m lo a pprava a rozvoj tchto v -


razn ch talent, budoucch posl vdy, se dje jenom na b zi dobrovolnosti jejich u itel a organiz tor sout . O to vt dk pat Hor kov nadaci, kter za tuto aktivitu materi ln oceuje alespo "spn studenty, kte dlaj dobr jmno esk republice ve svt.

; ; ;

Zlat Jan Hermann pi dkovnm projevu

Laureti cen Praemium Bohemiae 2008 { 2009 pro studenty v oborech fyzika, matematika a programovn a za sp ch na EUSO: (1) Dalimil Maz , zlat medaile na 39. Mezin rodn fyzik ln olympi d ve Vietnamu 2008. Absolvent Gymn zia J. Keplera v Praze, student University of Cambridge, Trinity College, Anglie. (2) Jan Hermann, zlat medaile na 39. Mezin rodn fyzik ln olympi d ve Vietnamu 2008. Absolvent Gymn zia v eskm Krumlov, student Prodovdeck fakulty a MFF Univerzity Karlovy. (3) Luk Ledvina, stbrn medaile na 39. Mezin rodn fyzik ln olympi d ve Vietnamu 2008. Absolvent Prvnho eskho gymn zia v Karlov ch Varech, student MFF Univerzity Karlovy.

(4) Jan Humpl k, stbrn medaile na 40. Mezin rodn fyzik ln olympi d v Mexiku 2009. Absolvent Prvnho eskho gymn zia v Karlov ch Varech, student MFF Univerzity Karlovy. (5) Michal Koutn, stbrn medaile na 40. Mezin rodn fyzik ln olympi d v Mexiku 2009. Absolvent Gymn zia v Teb i, student MFF Univerzity Karlovy. (6) Miroslav Klimo, stbrn medaile na 49. Mezin rodn matematick olympi d ve #panlsku 2008 a stbrn medaile na 20. Mezin rodn olympi d v informatice v Egypt 2008. Absolvent Gymn zia Mikul e Kopernka v Blovci, student Fakulty informatiky Masarykovy univerzity v Brn. (7) Josef Tkadlec, stbrn medaile na 50. Mezin rodn matematick olympi d v Nmecku 2009 a bronzov medaile na 49. Mezin rodn matematick olympi d ve #panlsku 2008. Absolvent Gymn zia J. Keplera v Praze, student MFF Univerzity Karlovy. (8) Roman Smr, stbrn medaile na 20. Mezin rodn olympi d v informatice v Egypt 2008. Absolvent Gymn zia E. Kr snohorsk v Praze, student MFF Univerzity Karlovy. (9) David Klaka, stbrn medaile na 21. Mezin rodn olympi d v informatice v Bulharsku 2009. Student Gymn zia, t. Kpt. Jaroe v Brn. (10) Richard Polma, bronzov medaile na 40. Mezin rodn fyzik ln olympi d v Mexiku 2009. Absolvent Gymn zia Mlad Boleslav, student Lkask fakulty Univerzity Karlovy v Hradci Kr lov. (11) J chym Skora, bronzov medaile na 40. Mezin rodn fyzik ln olympi d v Mexiku 2009. Student Gymn zia Ch. Dopplera v Praze. (12) Petr Ryav, bronzov medaile na 40. Mezin rodn fyzik ln olympi d v Mexi-


447

ku 2009. Student Gymn zia Jaroslava Heyrovskho v Praze. (13) Jan Matjka, bronzov medaile na 50. Mezin rodn matematick olympi d v Nmecku 2009. Absolvent Gymn zia, Jrovcova ul. v esk ch Budjovicch, student MFF Univerzity Karlovy. (14) Jan Vahara, bronzov medaile na 50. Mezin rodn matematick olympi d v Nmecku 2009. Absolvent Gymn zia v Holeov, student MFF Univerzity Karlovy. (15) Hynek Jemel k, bronzov medaile na 21. Mezin rodn olympi d v informatice v Bulharsku 2009. Student Gymn zia, t. Kpt. Jaroe v Brn. (16) Vlastimil Dort, bronzov medaile na

21. Mezin rodn olympi d v informatice v Bulharsku 2009. Student Gymn zia, #pit lsk ul. v Praze.

Mimo dn ceny Praemium Bohemiae 2009 za zisk zlat medaile a poh ru abso-

lutnho vtze na EUSO 2009 ve #panlsku pro esk t m ve slo en: (17) Lenka urnov , studentka Gymn zia, Jrovcova ul. v esk ch Budjovicch. (18) Ondej H k, student Gymn zia a SO#Pg v Hoicch v Podkrkono. (19) Tom Zeman, student Gymn zia J. Keplera v Praze.

;; ; ;; ;; ;

Bohumil Vybral

st student ocennch cenami Praemium Bohemiae v roce 2009

448


No title

Recommend Documents