2017

Diskr´ etn´ı matematika Petr Kov´aˇr [email protected] Vysok´ a ˇskola b´ an ˇsk´ a – Technick´ a univerzita Ostrava

DiM 470-2301/01, zimn´ı semestr 2016/2017

O tomto souboru

Tento soubor je zam´yˇslen pˇredevˇs´ım jako pom˚ ucka pro pˇredn´aˇsej´ıc´ıho. ˇ Radu d˚ uleˇzit´ych informac´ı v souboru nenajdete, protoˇze pˇredn´aˇsej´ıc´ı je ˇr´ık´a, ukazuje, pˇr´ıpadnˇe maluje na tabuli. Pˇredn´aˇsky jsou na webu k dispozici, aby studenti mohli snadno dohledat prob´ıran´a t´emata z pˇredn´aˇsek, kter´e zameˇskali. Pro samostatn´e studium doporuˇcuji skripta: M. Kubesa: Z´aklady diskr´etn´ı matematiky, v´yukov´y text ´ P. Kov´aˇr: Uvod do teorie graf˚ u, v´yukov´y text Pro pˇr´ıpravu ke zkouˇsce a p´ısemk´am doporuˇcuji cviˇcebnici: P. Kov´aˇr: Cviˇcen´ı z diskr´etn´ı matematiky, sb´ırka pˇr´ıklad˚ u Vˇse na http://homel.vsb.cz/~kov16/predmety dm.php

Pˇrehled pˇredn´ aˇsky

Kapitola Eulerovsk´ e a hamiltonovsk´ e grafy motivace eulerovsk´e grafy jedn´ım tahem“ ” hamiltonovsk´e grafy a obchodn´ı cestuj´ıc´ı

Eulerovsk´ e grafy Historicky prvn´ı probl´em vyˇreˇsen´y pomoc´ı Teorie graf˚ u 1736: Probl´em sedmi most˚ u mˇesta Kr´alovce – hled´an´ı tahu, kter´y obsahuje vˇsechny hrany dan´eho grafu G .

Pˇr´ıklad Poˇst’´ak m´a za u ´kol rozn´est poˇstu do kaˇzd´e ulice ve sv´em okrsku. M˚ uˇze kaˇzdou ulic´ı proch´azel jen jednou – nachod´ı se tak co nejm´enˇe a poˇstu doruˇc´ı dˇr´ıve. Pˇredstavme si graf, kter´y modeluje ulice okrsku tak, ˇze hrany odpov´ıdaj´ı ulic´ım a kˇriˇzovatky vrchol˚ um grafu. Poˇst’´akova u ´loha tak pˇresnˇe odpov´ıd´a hled´an´ı tahu, kter´y obsahuje kaˇzdou hranu pr´avˇe jednou. Podobnˇe m˚ uˇzeme pl´anovat trasu snˇeˇzn´e fr´ezy, kter´a odkl´ız´ı chodn´ıky, popel´aˇri, krop´ıc´ı vozy. . . Pˇr´ıklad v3

x5

v4 x4

v1

v2

x3

x1

x2

Lze tento graf (resp. jeho hrany) nakreslit jedn´ım tahem?

Definice Tah v grafu G , kter´y zaˇc´ın´a a konˇc´ı ve stejn´em vrcholu, se naz´yv´a uzavˇren´y tah. Jestliˇze nav´ıc obsahuje vˇsechny hrany souvisl´eho grafu G , m´ame uzavˇren´y eulerovsk´y tah. Graf, ve kter´em existuje uzavˇren´y eulerovsk´y tah, se naz´yv´a eulerovsk´y graf. Tah v souvisl´em grafu G , kter´y obsahuje vˇsechny hrany grafu G a v´ychoz´ı vrchol se liˇs´ı od koncov´eho vrcholu, se naz´yv´a otevˇren´y eulerovsk´y tah. ˇ ık´ame, ˇze takov´y graf lze nakreslit jedn´ım tahem. R´ Eulerova vˇ eta Graf G lze nakreslit jedn´ım uzavˇren´ym tahem pr´avˇe tehdy, kdyˇz je G souvisl´y a vˇsechny jeho vrcholy jsou sud´eho stupnˇe . Uˇzit´ım elegantn´ıho triku snadno uk´aˇzeme: D˚ usledek Graf G lze nakreslit jedn´ım otevˇren´ym tahem pr´avˇe tehdy, kdyˇz je G souvisl´y a pr´avˇe dva jeho vrcholy jsou lich´eho stupnˇe.

Vˇ eta Graf G lze nakreslit jedn´ım uzavˇren´ym tahem pr´avˇe tehdy, kdyˇz je G souvisl´y a vˇsechny jeho vrcholy jsou sud´eho stupnˇe . D˚ ukaz Indukc´ı vzhledem k poˇctu hran (jen naznaˇcena implikace ”⇐” ). Z´aklad indukce: Lze pouˇz´ıt trivi´aln´ı graf. Pro netrivi´aln´ı souvisl´y graf G je kaˇzd´y vrchol stupnˇe alespoˇ n 2. Nejmenˇs´ı takov´y graf je G = Cn . Cyklus Cn je jistˇe moˇzno nakreslit jedn´ım uzavˇren´ym tahem (proˇc?). Indukˇcn´ı krok: Pˇredpokl´adejme, ˇze kaˇzd´y souvisl´y graf G se sud´ymi stupni a s m´enˇe neˇz |E (G )| hranami je moˇzno nakreslit jedn´ım uzavˇren´ym tahem. V G najdeme cyklus C (kaˇzd´y vrchol je stupnˇe alespoˇ n 2). V grafu G − C jsou vrcholy sud´eho stupnˇe a nebo izolovan´e vrcholy. Pokud G − C nen´ı souvisl´y, lze kaˇzdou jeho komponentu dle indukˇcn´ıho pˇredpokladu nakreslit jedn´ım tahem. Nyn´ı pˇrid´ame do cyklu C uzavˇren´y tah pro kaˇzd´y vrchol dalˇs´ı vi , kter´y leˇz´ı v nˇekter´e komponentˇe. Z´ısk´ame uzavˇren´y tah grafem G . Podle principu (siln´e) matematick´e indukce je d˚ ukaz ”⇐” hotov. 

D˚ usledek Graf G lze nakreslit jedn´ım otevˇren´ym tahem pr´avˇe tehdy, kdyˇz je G souvisl´y a pr´avˇe dva jeho vrcholy jsou lich´eho stupnˇe. D˚ ukaz ”⇒” M˚ uˇzeme-li graf G nakreslit jedn´ım otevˇren´ym tahem, tak G je souvisl´y a vˇsechny vrcholy jsou sud´eho stupnˇe s v´yjimkou prvn´ıho a posledn´ıho vrcholu otevˇren´eho tahu. ”⇐” M´am-li souvisl´y graf G s pr´avˇe dvˇema vrcholy u, v lich´eho stupnˇe, m˚ uˇzeme do grafu G pˇridat nov´y vrchol x, kter´y spoj´ıme (nov´ymi) hranami s vrcholy u, v a dostaneme souvisl´y graf G 0 , ve kter´em jsou vˇsechny vrcholy (i vrcholy u, v , x) sud´eho stupnˇe. Podle Eulerovy vˇety v grafu G 0 existuje uzavˇren´y eulerovsk´y tah T 0 . Vynech´an´ım vrcholu x a obou pˇridan´ych hran dostaneme otevˇren´y eulerovsk´y tah T mezi vrcholy u a v v grafu G . 

Pˇr´ıklady u4

u3

u5

v3

v7 v6

u2 v2

u6

u1 u7

v4

u10 u8

u9

w1 w2

v1 w6

w7

w8

v5

w9 w5

w3 w4

Kter´e z uveden´ych graf˚ u lze nakreslit jedn´ım tahem?

Eulerovsk´e tahy lze pouˇz´ıt i pro ˇreˇsen´ı jin´ych probl´em˚ u, neˇz putov´an´ı v mapˇe. Pˇekn´e vyuˇzit´ı eulerovsk´ych graf˚ u: Pˇr´ıklad Vrcholy stavov´eho grafu nˇejak´eho syst´emu odpov´ıdaj´ı moˇzn´ym stav˚ um, kter´e mohou nastat, a hrany spojuj´ı stavy, mezi kter´ymi existuje leg´aln´ı pˇrechod – napˇr´ıklad koneˇcn´e automaty. Pˇri testu syst´emu bychom r´adi provˇeˇrili vˇsechny moˇzn´e stavy a pˇrechody mezi nimi. Optim´aln´ı test m˚ uˇzeme napl´anovat podle eulerovsk´eho tahu grafem.

Hamiltonovsk´ e grafy Definice Hamiltonovsk´y cyklus v grafu je takov´y cyklus, kter´y proch´az´ı vˇsemi vrcholy. Graf, ve kter´em existuje hamiltonovsk´y cyklus, se naz´yv´a hamiltonovsk´y graf. Hamiltonovsk´y cyklus proch´az´ı kaˇzd´ym vrcholem pr´avˇe jedenkr´at. Na prvn´ı pohled se zd´a, ˇze hled´an´ı hamiltonovsk´eho cyklu je velmi podobn´e hled´an´ı eulerovsk´emu tahu. Nen´ı tomu tak! Zat´ımco pro rozhodnut´ı o existenci eulerovsk´eho tahu v souvisl´em grafu je nutnou i dostateˇcnou podm´ınkou sudost vˇsech stupˇ n˚ u, pro existenci hamiltonovsk´eho cyklu ˇz´adn´a takov´a podm´ınka nen´ı zn´ama (asi neexistuje). D˚ usledek: obecnˇe nen´ı lehk´e rozhodnout, zda dan´y graf je hamiltonovsk´y.

Pˇr´ıklad Probl´em obchodn´ıho cestuj´ıc´ıho, kter´y m´a navˇst´ıvit vˇsechna mˇesta sv´eho regionu, vr´atit se do v´ychoz´ıho mˇesta a pˇritom nacestovat co nejkratˇs´ı vzd´alenost. Zjednoduˇsen´a verze: m˚ uˇze navˇst´ıvit kaˇzd´e mˇesto s alespoˇ n 500 obyvateli pr´avˇe jednou a vr´atit se zpˇet?

Optim´aln´ı ˇreˇsen´ı u ´lohy obchodn´ıho cestuj´ıc´ıho pro 13 509 mˇest v USA.

Pˇr´ıklad Poˇst’´ak na vesnici rozn´aˇs´ı obvykle jen m´alo poˇstovn´ıch z´asilek. Sp´ıˇs neˇz proj´ıt kaˇzdou ulici, mus´ı poˇst’´ak navˇst´ıvit vˇsechny adresy (domy), do kter´ych m´a doruˇcit nˇejakou z´asilku. Pˇr´ıklad Ve velkoskladu se pˇri nav´aˇzen´ı nebo pˇred´av´an´ı zboˇz´ı rozv´aˇz´ı paleta, nebo tˇreba nˇekolik palet s r˚ uzn´ym zboˇz´ım na urˇcit´a m´ısta ve skladu. Voz´ık m´a opˇet za u ´kol navˇst´ıvit vˇsechna vybran´a m´ısta a pˇritom urazit co nejkratˇs´ı vzd´alenost. Vˇsechny uveden´e u ´lohy odpov´ıdaj´ı nalezen´ı hamiltonovsk´eho cyklu, pˇr´ıpadnˇe nejkratˇs´ıho hamiltonovsk´eho cyklu v grafu.

Pˇr´ıklady Kter´e n´asleduj´ıc´ı grafy jsou a kter´e nejsou hamiltonovsk´e?

Hamiltonovsk´e a nehamiltonovsk´e grafy. Pˇr´ıklady Dalˇs´ı u ´lohy vedouc´ı na hled´an´ı hamiltonovsk´eho cyklu rodinn´y v´ylet po turistick´ych zaj´ımavostech divadeln´ı nebo cirkusov´e turn´e po republice Hamiltonova hra

Diracova vˇ eta Mˇejme graf G na n vrcholech, kde n ≥ 3. Je-li nejmenˇs´ı stupeˇ n vrchol˚ u v grafu alespoˇ n n/2, tak je graf G hamiltonovsk´y. D˚ ukaz V pˇredmˇetu Teorie Graf˚ u I. Vˇsimnˇete si: vˇeta m´a tvar implikace, nikoli ekvivalence. Proto graf, kter´y splˇ nuje podm´ınky vˇety je hamiltonovsk´y, ale ne kaˇzd´y hamiltonovsk´y graf mus´ı podm´ınky vˇety splˇ novat. Pˇr´ıklad Pˇr´ıklad grafu, kter´y je jistˇe hamiltonovsk´y, ale nem´a mnoho“ hran. ”

Cyklus C7 .

Oreho vˇ eta Mˇejme graf G na n vrcholech, kde n ≥ 3. Jestliˇze pro kaˇzd´e dva nesousedn´ı vrcholy u a v v grafu G plat´ı deg(u) + deg(v ) ≥ n, tak je graf G hamiltonovsk´y. Diracova vˇeta je speci´aln´ım pˇr´ıpadem Oreho vˇety. Pˇr´ıklad Je n´asleduj´ıc´ı graf hamiltonovsk´y? u4

u7 u2

u1 u3

u5

u6

Proˇ c se ˇr´ık´ a hamiltonovsk´ e grafy“? ”

Pˇr´ıˇstˇ e

Kapitola Vzd´ alenost a metrika motivace vzd´alenost v grafu v´ypoˇcet metriky vzd´alenost v ohodnocen´ych grafech hled´an´ı nejkratˇs´ı cesty