Aplikace 1-VMV ohodnocení grafů. Applications of 1-VMV labelings graphs

ˇ - Technická univerzita Ostrava VSB Fakulta elektrotechniky a informatiky Katedra aplikované matematiky

Aplikace 1-VMV ohodnocen´ı graf˚ u Applications of 1-VMV labelings graphs

2012

Matˇej Krbeˇcek

Rád bych zde vyjádˇril sv˚ uj vdˇek Mgr. Petru Kováˇrovi, Ph.D.za jeho cenné rady, veden´ı a pˇripom´ınky pˇri tvorbˇe této bakaláˇrské práce. Bez jeho pomoci by práce v této podobˇe nikdy nevznikla. ˇ podporovali, Dále bych chtˇel podˇekovat vˇsem lidem, kteˇr´ı mˇe pˇri mém studiu na VSB zejména m´ ym rodiˇc˚ um.

Abstrakt Tato bakaláˇrská práce se zab´ yvá problematikou magick´ ych ohodnocen´ı graf˚ u. Shrnuje základn´ı pojmy, známé v´ ysledky existence 1-VMV (1-Vertex Magic Vertex) graf˚ ua pˇrináˇs´ı nové v´ ysledky pro grafy na lichém poˇctu vrchol˚ u, konkrétnˇe pˇrehled ˇrád˚ u, pro které existuje 14-pravideln´ y 1-VMV graf na lichém poˇctu vrchol˚ u, tento v´ ysledek nebyl doposud znám. Tvrzen´ı rozˇsiˇruje v´ ysledky jin´ ych autor˚ u t´ ykaj´ıc´ı se 2-, 4-, 6-, 8-, 10-, 12pravideln´ ych graf˚ u (viz ˇclánky [1], [2], [3], [4], [5]). V´ ysledky práce by se mohly vyuˇz´ıt i v praxi pˇri plánovan´ı ne´ upln´ ych vyrovnan´ ych/nevyrovnan´ ych turnaj˚ u, jejichˇz problematika jde do teorie 1-VMV graf˚ u pˇreformulovat. Kl´ıˇ cov´ a slova: 1-VMV ohodnocen´ı, ne´ uplné nevyrovnané/vyrovnané turnaje, 14-pravidelné grafy.

Abstract This thesis deals with magic graphs labeling. Thesis sums up basic concepts, known results on 1-VMV graphs and gives some new results for graphs of odd orders, in particular orders for which exist a 14-regular 1-VMV graph of odd order. This result was not known yet. The claim extends related results of other authors 2-, 4-, 6-, 8-, 10-, 12-regular graphs (see articles [1], [2], [3], [4], [5]) Thesis results can be used in practice for scheduling of equalized/fair incomplete tournaments which is a problem, that can be, formulated in the language of 1-VMV graphs. Key words: 1-VMV labeling, incomplete equalized/fair tournaments, 14-regular graphs.

Seznam pouˇ zit´ ych symbol˚ u a zkratek G = (V, E) Kn Km,n NNT Pn Cn Tn G f (x) wf (x) deg(x) △(G) δ(G) 1-VMV k G[H] A

– – – – – – – – – – – – – – – – –

Graf G s mnoˇzinou hran E a mnoˇzinou vrchol˚ uV Kompletn´ı graf s n vrcholy Kompletn´ı bipartitn´ı graf s partitami o m a n vrcholech Ne´ uplné nevyrovnané turnaje Cesta na n vrcholech Cyklus na n vrcholech Strom na n vrcholech Doplnˇek grafu G ohodnocen´ı vrcholu x Váha vrcholu x pˇri ohodnocen´ı f Stupeˇ n vrcholu x Maximáln´ı stupeˇ n v grafu G Minimáln´ı stupeˇ n v grafu G Magické ohodnocen´ı Magická konstanta Kompozice grafu G s grafem H podgraf vyuˇz´ıvan´ y v konstrukci d˚ ukazu 14-pravideln´ ych graf˚ u

OBSAH

1

Obsah ´ 1 Uvod 1.1 Ne´ uplné turnaje . . . . . . . . . . . . . . . . . . . . . 1.1.1 Ne´ uplné nevyrovnané turnaje (N N T ) . . . . . 1.1.2 Ne´ uplné vyrovnané turnaje (N V T ) . . . . . . . 1.1.3 Vyuˇzit´ı 1-VMV graf˚ u pro ne´ uplné turnaje . . . 1.2 Definice . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Pˇrehled znám´ ych v´ ysledk˚ u. . . . . . . . . . . . . . . . 1.3.1 Základn´ı v´ ysledky . . . . . . . . . . . . . . . . 1.3.2 Sud´ y poˇcet vrchol˚ u. . . . . . . . . . . . . . . . 1.3.3 Lich´ y poˇcet vrchol˚ u . . . . . . . . . . . . . . . 1.3.4 r-pravidelné grafy s malou hodnotou r . . . . . 1.3.5 Grafy, pro které 1-VMV ohodnocen´ı neexistuje

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

3 3 3 4 5 7 12 12 14 15 15 16

2 Nov´ e v´ ysledky 2.1 14-pravidelné grafy . . . . . . . . . . . . . . . . . . . . 2.1.1 Podgraf A . . . . . . . . . . . . . . . . . . . . . 2.1.2 D˚ ukaz existence 14-pravideln´ ych 1-VMV graf˚ u 2.1.3 Hledán´ı podgrafu A ve ”startovn´ıch” grafech. .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

18 18 18 20 25

3 Z´ avˇ er

29

4 Literatura

30

´ ˚ SEZNAM OBRAZK U

2

Seznam obr´ azk˚ u 1

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Pˇr´ıklad ˇcásti ne´ uplného nevyrovnaného turnaje (kaˇzd´ y t´ ym hraje 10 zápas˚ u) pro nejslabˇs´ı t´ ym 1 (s obt´ıˇznost´ı turnaje 346) a nejsilnˇejˇs´ı t´ ym 40 (s obt´ıˇznost´ı turnaje 121) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Pˇr´ıklad ˇcásti ne´ uplného vyrovnaného turnaje pro nejslabˇs´ı (t´ ym 1) a nejsilnˇejˇs´ı (t´ ym 40) t´ ym, kde maj´ı oba t´ ymy obt´ıˇznost zápas˚ u 220 . . . . . . . 5 Graf ukázkového turnaje, kde souˇcet sil soupeˇr˚ u je 30 pro kaˇzd´ y vrchol . . . 6 Graf G s mnoˇzinou vrchol˚ u V = {w, x, y, z} a mnoˇzinou hran E = {wx, wy, xy, yz} Vrchol x je sousedn´ım s y, vrcholy jsou spojeny hranou xy . . . . . . . . . . 7 Kompletn´ı graf K5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Kompletn´ı bipartitn´ı graf K3,2 . . . . . . . . . . . . . . . . . . . . . . . . . 8 Podgraf G′ = (V ′ , E ′ ) v grafu G s mnoˇzinou vrchol˚ u V ′ = {x, y, z} a mnoˇzinou hran E ′ = {xz, yz} . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Cesta Pn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Cyklus Cn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Strom Tn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1-VMV graf s magickou konstantou k=5 . . . . . . . . . . . . . . . . . . . . 10 3-pravideln´ y graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Cesta s 1-VMV ohodnocen´ım a magickou konstantou k = 3 . . . . . . . . . 13 Podgraf A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Pˇridán´ı 4 vrchol˚ u do podgrafu A, kter´ y je podgrafem G . . . . . . . . . . . 21 14-pravideln´ y graf na 19 vrcholech s podgrafem A . . . . . . . . . . . . . . 24 14-pravideln´ y graf na 21 vrcholech s podgrafem A . . . . . . . . . . . . . . 25 Podgraf B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Magick´ y ˇctverec 3 × 3 s magickou konstantou k = 15 . . . . . . . . . . . . . 27 Rozloˇzen´ı vrchol˚ u pro 1-VMV tripartitn´ı graf na 21 vrcholech. . . . . . . . . 28

7

1

´ UVOD

3

´ Uvod

1 1.1

Ne´ upln´ e turnaje

Turnaj je soutˇeˇz urˇcitého poˇctu u ´ˇcastn´ık˚ u ve sportovn´ı, nebo jakékoliv jiné discipl´ınˇe, kteˇr´ı mezi sebou soupeˇr´ı o celkové um´ıstˇen´ı. Turnaj˚ u známe mnoho typ˚ u. Jsou turnaje, kde soutˇeˇz´ıc´ı zaˇc´ınaj´ı skupinovou fáz´ı, ze které postupuj´ı do play-off ˇcásti. T´ımto zp˚ usobem se hraje vˇetˇsina fotbalov´ ych turnaj˚ u, jako napˇr´ıklad Mistrovstv´ı svˇeta, Mistrovstv´ı Evropy, Liga mistr˚ u, nebo také basketbalová liga NBA a mnoho dalˇs´ıch. Dalˇs´ı typem turnaj˚ u mohou b´ yt turnaje zaloˇzené pouze na systému play-off, tedy turnaje, ve kter´ ych jakmile jak´ ykoliv soupeˇr prohraje zápas, ihned z turnaje vypadává. Tento systém se vyuˇz´ıvá pˇreváˇznˇe u tenisov´ ych turnaj˚ u, jako je napˇr´ıklad Wimbledon. Hraj´ı se také turnaje, které maj´ı v´ıce skupinov´ ych fáz´ı s navazuj´ıc´ı play-off ˇcást´ı, typick´ ym pˇr´ıkladem takového turnaje byly do roku 2012 napˇr´ıklad hokejov´ a Mistrovstv´ı svˇeta. T´ ymy byly rozdˇeleny do dvou skupin po 4 celc´ıch, ze kter´ ych postupovali vˇzdy 3 nejlepˇs´ı u ´ˇcastn´ıci do 2 finálov´ ych skupin. Z tˇechto dvou skupin postupovali prvn´ı 3 do play-off. Známe také turnaje, kde ve fázi play-off se hraje v´ıce zápas˚ u (fotbalová Liga mistr˚ u, playoff ˇcást v hokejové soutˇeˇzi NHL. . . ). Jelikoˇz zp˚ usob˚ u jak´ ym systémem uspoˇrádat turnaj je celé ˇrada, budeme se zab´ yvat pouze skupinovou ˇcást´ı turnaj˚ u. Skupinovou ˇcást turnaj˚ u m˚ uˇzeme rozdˇelit do dvou kategori´ı: ´ • Upln´ e turnaje • Ne´ uplné turnaje ´ Upln´ e turnaje jsou takové turnaje, kde kaˇzd´ y t´ ym hraje se vˇsemi protihráˇci. Máme-li tedy napˇr´ıklad fotbalovou soutˇeˇz s 5 t´ ymy (t´ ym 1, t´ ym 2, t´ ym 3, t´ ym 4, t´ ym 5), bude kaˇzd´ y t´ ym hrát v jarn´ı i zimn´ı ˇcásti 4 zápasy. Vezmeme-li napˇr´ıklad t´ ym 2, potom tento t´ ym bude hrát zápas se vˇsemi ostatn´ımi t´ ymy, tedy t´ ymem 1, 3, 4 a t´ ymem 5. Protoˇze jako pˇr´ıklad uvád´ıme fotbalovou ligu bude s kaˇzd´ ym z tˇechto t´ ym˚ u hrát 2 krát, jednou v podzimn´ı ˇcást´ı a podruhé v ˇcásti jarn´ı. Jak jiˇz logicky vypl´ yvá, jsou ne´ uplné turnaje takové turnaje, ve kter´ ych t´ ymy nehraj´ı kaˇzd´ y s kaˇzd´ ym, ale pouze s urˇcit´ ym poˇctem soupeˇr˚ u. To m˚ uˇze b´ yt zp˚ usobeno napˇr´ıklad velk´ ym poˇctem t´ ym˚ u, kdy nen´ı z ˇcasového hlediska moˇzné vˇsechny zápasy odehrát. Poˇcet zápas˚ u, které mus´ı kaˇzd´ y t´ ym odehrát, se domluv´ı dopˇredu. Tento typ turnaj˚ u se v praxi bˇeˇznˇe nevyuˇz´ıvá, problém velkého poˇctu t´ ym˚ u se pˇreváˇze ˇreˇs´ı jejich rozdˇelen´ım do v´ıce skupin. D˚ uvodem, proˇc se s ne´ upln´ ymi turnaji setkáváme velice zˇr´ıdka, je nesnadné uspoˇrádán´ı turnaje tak, aby pro kaˇzd´ y t´ ym byla soutˇeˇz stejnˇe obt´ıˇzná. 1.1.1

Ne´ upln´ e nevyrovnan´ e turnaje (N N T )

Jak jsme zm´ınili v´ yˇse, v pˇr´ıpadˇe ne´ upln´ ych turnaj˚ u se poˇcet zápas˚ u vol´ı dopˇredu. Pˇredstavme ’ si ted soutˇeˇz se 40 t´ ymy, kde kaˇzd´ y t´ ym hraje 10 zápas˚ u. Je zˇrejmé, ˇze vˇsechny

1

´ UVOD

4

t´ ymy nebudou m´ıt stejné soupeˇre. M˚ uˇze tedy nastat pˇr´ıpad, ˇze nejslabˇs´ı t´ ym v soutˇeˇzi bude hrát s 10 pˇredn´ımi (nejlepˇs´ımi) t´ ymy a souˇcasnˇe nejsilnˇejˇs´ı t´ ym bude m´ıt své soupeˇre pˇreváˇznˇe z konce tabulky. Turnaj, kde je siln´ y t´ ym zv´ yhodnˇen´ y o proti t´ ym˚ um slabˇs´ım, nebude vyrovnan´ y. Tento turnaj budeme oznaˇcovat jako ne´ upln´ y nevyrovnan´ y turnaj. Na Obrázku 1 je znázornˇen pˇr´ıklad takového turnaje, kde s´ıla t´ ymu je opaˇcná, jako poˇrad´ı t´ ymu. Tedy nejslabˇs´ı t´ ym je t´ ym 1 a nejsilnˇejˇs´ı t´ ym je t´ ym 40. Jak spolu souvis´ı graf na Obrázku 1 a zm´ınˇen´ y turnaj je lépe vysvˇetleno v podkapitole vyuˇzit´ı 1-VMV graf˚ u pro ne´ uplné turnaje.

Obrázek 1: Pˇr´ıklad ˇcásti ne´ uplného nevyrovnaného turnaje (kaˇzd´ y t´ ym hraje 10 zápas˚ u) pro nejslabˇs´ı t´ ym 1 (s obt´ıˇznost´ı turnaje 346) a nejsilnˇejˇs´ı t´ ym 40 (s obt´ıˇznost´ı turnaje 121)

1.1.2

Ne´ upln´ e vyrovnan´ e turnaje (N V T )

Vezmˇeme stejnou soutˇeˇz, kterou jsem zmiˇ novali i v pˇr´ıpadˇe N N T . Máme tedy soutˇeˇz se 40 t´ ymy, kde kaˇzd´ y t´ ym hraje 10 z´ apas˚ u. Chceme-li, aby takov´ y turnaj byl vyrovnan´ y, poˇzadujeme, aby kaˇzd´ y t´ ym hrál 10 zápas˚ u takov´ ych, ˇze obt´ıˇznost v tˇechto zápasech bude pro tento t´ ym stejná, jako obt´ıˇznost ostatn´ıch t´ ymu v jejich zápasech. Jinak ˇreˇceno, poˇzadujeme, aby platilo, ˇze kaˇzd´ y t´ ym odehraje v souˇctu 10 stejnˇe tˇeˇzk´ ych zápas˚ u, kde obt´ıˇznost tˇechto zápas˚ u záleˇz´ı na s´ıle t´ ymu, pro kter´ y soupeˇre vyb´ıráme. Pokud je toto splnˇeno, budeme takov´ y turnaj oznaˇcovat jako ne´ upln´ y vyrovnan´ y. Na Obrázku 2 je znázornˇeno rozlosován´ı soupeˇr˚ u pro nejslabˇs´ı t´ ym (t´ ym 1) a nejsilnˇejˇs´ı t´ ym (t´ ym 40) tak aby oba t´ ymy mˇely stejnˇe obt´ıˇznou (tˇeˇzkou) soutˇeˇz(v tomto pˇr´ıpadˇe 220). S´ıla jednotliv´ ych t´ ym˚ u je rozdˇelená stejnˇe jako v pˇr´ıpadˇe NNT turnaj˚ u. Obrázek 2 je jen ukázkou, jak by vypadal turnaj pro nejsilnˇejˇs´ı a nejslabˇs´ı t´ ym, stejnˇe bychom postupovali pro zb´ yvaj´ıc´ı t´ ymy.

1

´ UVOD

5

Obrázek 2: Pˇr´ıklad ˇcásti ne´ uplného vyrovnaného turnaje pro nejslabˇs´ı (t´ ym 1) a nejsilnˇejˇs´ı (t´ ym 40) t´ ym, kde maj´ı oba t´ ymy obt´ıˇznost zápas˚ u 220

1.1.3

Vyuˇ zit´ı 1-VMV graf˚ u pro ne´ upln´ e turnaje

Pomoc´ı znalost´ı teorie magick´ ych graf˚ u je moˇzné naplánovat ne´ upln´ y turnaj, kter´ y bude nav´ıc vyrovnan´ y. V kapitole ”Pˇrehled znám´ ych v´ ysledk˚ u”je sepsáno pro jak´ y poˇcet t´ ym˚ u a zápas˚ u jde takov´ yto turnaj sestavit. Pokusme se postup vytvoˇren´ı takového turnaje popsat na následuj´ıc´ım pˇr´ıkladu. Mˇejme soutˇeˇz s 9 t´ ymy (t´ ym 1, t´ ym 2, t´ ym 3, t´ ym 4, t´ ym 5, t´ ym 6, t´ ym 7, t´ ym 8, t´ ym 9) a urˇceme, ˇze kaˇzd´ y t´ ym bude hrát 6 zápas˚ u. Jednotlivé t´ ymy si m˚ uˇzeme pˇredstavit jako vrcholy grafu. Hrany tohoto grafu budou tvoˇrit jednotlivé zápasy. Pokud tedy bude t´ ym 1 hrát s t´ ymem 2, potom tento zápas v grafu znázorn´ıme jako hranu mezi vrcholem pˇredstavuj´ıc´ım t´ ym 1 a vrcholem pˇredstavuj´ıc´ım t´ ym 2. Tato soutˇeˇz tedy bude m´ıt podobu 6 pravidelného grafu na 9 vrcholech (9 t´ ym˚ u, kaˇzd´ y bude hrát 6 zápas˚ u, proto kaˇzd´ y vrchol bude m´ıt 6 soused˚ u, tedy 6 incidentn´ıch hran). Jeden takov´ y graf je znázornˇen na Obrázku 3. Pokud nav´ıc poˇzadujeme, aby tento turnaj byl vyrovnan´ y, mus´ıme zohlednit kvalitu jednotliv´ ych t´ ym˚ u. Jej´ıch kvalitu/s´ılu m˚ uˇzeme vyˇc´ıst napˇr´ıklad z um´ıstˇen´ı v pˇredchoz´ım roˇcn´ıku turnaje. Kaˇzdému t´ ymu pˇriˇrad´ıme celé ˇc´ıslo od 1 do n, kde n je celkov´ y poˇcet t´ ym˚ u v soutˇeˇzi. V naˇsem pˇr´ıpadˇe tedy budeme pˇriˇrazovat ˇc´ısla od 1 do 9. Nejslabˇs´ı t´ ym bude ohodnocen ˇc´ıslem 1, druh´ y nejslabˇs´ı ˇc´ıslem 2, takto budeme pokraˇcovat aˇz po t´ ym nejsilnˇejˇs´ı, kter´ y bude ohodnocen ˇc´ıslem 9. Koneˇcné rozdˇelen´ı ohodnocen´ı t´ ymu je v tabulce 1. Pokud máme takto ohodnocené t´ ymy, m˚ uˇzeme nyn´ı zaˇc´ıt pl´ anovat jednotlivé zápasy. Zápasy naplánujeme tak, ˇze vˇsechny vrcholy v grafu budou m´ıt stejnou váhu (vysvˇetleno v podkapitole 1.2 ). Jednoduˇse ˇreˇceno, pokud si zvol´ıme nˇejak´ y vrchol (t´ ym) a seˇcteme jednotlivá ohodnocen´ı sousedn´ıch vrchol˚ u (soupeˇr˚ u) tohoto vrcholu (t´ ymu), dostaneme pˇrirozené ˇc´ıslo. Pokud je toto ˇc´ıslo stejné pro vˇsechny vrcholy v grafu, jedná se o 1VMV graf. Ve sportovn´ı terminologii ˇreˇceno, pokud bychom ze vˇsech protivn´ık˚ u vybraného

1

´ UVOD

6

Obrázek 3: Graf ukázkového turnaje, kde souˇcet sil soupeˇr˚ u je 30 pro kaˇzd´ y vrchol Název t´ ymu T´ ym 1 T´ ym 2 T´ ym 3 T´ ym 4 T´ ym 5 T´ ym 6 T´ ym 7 T´ ym 8 T´ ym 9

S´ıla t´ ymu nejslabˇs´ı druh´ y nejslabˇs´ı tˇret´ı nejslabˇs´ı ˇctvrt´ y nejslabˇs´ı stˇrednˇe siln´ y ˇctvrt´ y nejsilnˇejˇs´ı tˇret´ı nejsilnˇejˇs´ı druh´ y nejsilnˇejˇs´ı nejsilnˇejˇs´ı

Ohodnocen´ı t´ ymu 1 2 3 4 5 6 7 8 9

Tabulka 1: tabulka ohodnocen´ı t´ ym˚ u podle jejich kvality/s´ıly

t´ ymu udˇelali jednoho soupeˇre, kter´ y by byl siln´ y jako souˇcet jednotliv´ ych ohodnocen´ı vrchol˚ u (sila(P ) = f (souper1) + f (souper2) + f (souper3) + f (souper4) + f (souper5) + f (souper6)), bude kaˇzd´ y t´ ym hrát se stejnˇe siln´ ym soupeˇrem. M˚ uˇzeme tedy mluvit o ne´ uplném vyrovnaném turnaji.

1

´ UVOD

1.2

7

Definice

V této podkapitole jsou uvedeny základn´ı pojmy a definice potˇrebné pro správné pochopen´ı dalˇs´ıho textu. Uvedené pojmy a definice jsou jen v´ ybˇerem velkého mnoˇzstv´ı pojm˚ u v teorii graf˚ u. Jsou zde uvedeny pouze pojmy a definice pouˇz´ıvané v této bakaláˇrské práci. Definice 1.2.1. Graf (obyˇcejný ˇci jednoduchý neorientovaný graf ) je uspoˇra ´dan´ a dvojice G = (V, E), kde V je mnoˇzina vrchol˚ u a E je mnoˇzina hran – mnoˇzina vybraných dvouprvkových podmnoˇzin mnoˇziny vrchol˚ u. Prvky mnoˇziny V budeme znaˇcit mal´ ymi p´ısmeny, napˇr. x, prvky mnoˇziny E jsou potom {x, y}, nebo zkrácenˇe xy. Na mnoˇzinu hran odkazujeme jako na E(G), na mnoˇzinu vrchol˚ u V (G). Grafy se ˇcasto zadávaj´ı pˇr´ımo názorn´ ym obrázkem, jinak je lze také zadat v´ yˇctem vrchol˚ u a v´ yˇctem hran.

Obrázek 4: Graf G s mnoˇzinou vrchol˚ u V {wx, wy, xy, yz}

= {w, x, y, z} a mnoˇzinou hran E =

Definice 1.2.2. Dva vrcholy x, y ∈ V (G) jsou sousedn´ı, pokud mezi nimi existuje hrana xy ∈ E(G)

Obrázek 5: Vrchol x je sousedn´ım s y, vrcholy jsou spojeny hranou xy

Definice 1.2.3. Mnoˇzina sousedn´ıch vrchol˚ u vrcholu x je tvoˇrena vˇsemi vrcholy y, pro které plat´ı xy ∈ E(G). Mnoˇzinu sousedn´ıch vrchol˚ u vrcholu x budeme znaˇcit N (x). Pokud si vrchol x pˇredstav´ıme jako sportovn´ı t´ ym (t´ ym x), kter´ y hraje turnaj, potom jeho soused bude t´ ym, kter´ y s n´ım odehraje zápas. Mnoˇzina sousedn´ıch vrchol˚ u k tomuto vrcholu bude tedy pˇredstavovat mnoˇzinu t´ ym˚ u, které s t´ ymem x odehraj´ı zápas. Jinak

1

´ UVOD

8

ˇreˇceno, pokud si za vrcholy pˇredstav´ıme sportovn´ı t´ ymy, potom hrana mezi tˇemito t´ ymy bude pˇredstavovat jedno jejich vzájemné sportovn´ı utkán´ı. Definice 1.2.4. Kompletn´ı graf je takový graf, který m´ a kaˇzdé dva vrcholy navz´ ajem sousedn´ı. Znaˇc´ı se Kn , kde n je poˇcet vrchol˚ u.

Obrázek 6: Kompletn´ı graf K5

Kompletn´ı graf je tedy takov´ y graf, kde kaˇzd´ y vrchol je spojen´ y hranou se vˇsemi ostatn´ımi vrcholy. Kompletn´ı 1-VMV graf lze sestrojit pouze pokud n = 1. Ve sportovn´ı tématice nám kompletn´ı graf pˇredstavuje klasick´ y u ´pln´ y skupinov´ y turnaj, tedy turnaj, kde hraje kaˇzd´ y s kaˇzd´ ym. Definice 1.2.5. Graf, jehoˇz mnoˇzina vrchol˚ u je sjednocen´ım dvou nepr´ azdných disjunktn´ıch mnoˇzin U a W a mnoˇzina hran E = {∀u ∈ U ∧ ∀w ∈ W : uw}, se nazýv´ a kompletn´ı bipartitn´ı graf s partitami U a W . Znaˇc´ıme jej Km,n , kde m = |U | a n = |W |.

Obrázek 7: Kompletn´ı bipartitn´ı graf K3,2

Kompletn´ı bipartitn´ı graf si m˚ uˇzeme pˇredstavit jako dvˇeskupiny (partity) vrchol˚ u, kde vrchol nen´ı spojen hranou s vrcholy ve stejné skupinˇe (parititˇe), ale je spojen se vˇsemi ostatn´ımi vrcholy v druhé skupinˇe (partitˇe). Jinak ˇreˇceno je spojen se vˇsemi vrcholy, které s n´ım nejsou v jedné partitˇe. Definice 1.2.6. Podgrafem grafu G rozum´ıme libovolný graf A na podmnoˇzinˇe vrchol˚ u V (A) ⊆ V (G), který m´ a za hrany libovolnou podmnoˇzinu hran grafu G maj´ıc´ı oba vrcholy ve V (A). P´ıˇseme A ⊆ G.

1

´ UVOD

9

Obrázek 8: Podgraf G′ = (V ′ , E ′ ) v grafu G s mnoˇzinou vrchol˚ u V ′ = {x, y, z} a mnoˇzinou ′ hran E = {xz, yz}

Definice 1.2.7. Cesta délky n se znaˇc´ı Pn a m´ a n + 1 vrchol˚ u spojených za sebou n hranami.

Obrázek 9: Cesta Pn

Definice 1.2.8. Cyklus délky n se znaˇc´ı Cn a m´ a n ≥ 3 vrchol˚ u spojených do jednoho cyklu n hranami.

Obr´ azek 10: Cyklus Cn

Definice 1.2.9. Strom Tn je souvislý acyklický graf takový, jehoˇz ˇza ´dný podgraf nen´ı cyklus.

1

´ UVOD

10

Obrázek 11: Strom Tn

Definice 1.2.10. Ohodnocen´ı grafu G je funkce f , kter´ a vrchol˚ um nebo hran´ am v grafu G pˇriˇrad´ı ˇc´ısla, nejˇcastˇeji z mnoˇziny pˇrirozených ˇc´ısel. V této bakaláˇrské práci se budeme zab´ yvat pouze vrcholov´ ym ohodnocen´ım grafu. Tedy ohodnocen´ım kdy jsou hodnoty v ohodnocen´ı f pˇriˇrazeny pouze vrchol˚ um. Hranov´ ym ohodnocen´ım (hodnoty jsou pˇriˇrazeny jednotliv´ ym hranám) a totáln´ım ohodnocen´ı (hodnoty jsou pˇriˇrazeny hranám i vrchol˚ um) se zab´ yvat nebudeme. Definice 1.2.11. V´ aha vrcholu x grafu G pˇri ohodnocen´ı f , znaˇc´ıme wf (x) se rovn´ a: wf (x) =

P

u∈N (x) f (u);

Obrázek 12: 1-VMV graf s magickou konstantou k=5

Má-li kaˇzd´ y vrchol v grafu stejnou váhu wf (x), potom je tento graf 1-VMV. Definice 1.2.12. 1-VMV ohodnocen´ı grafu G = (V, E) je bijektivn´ı zobrazen´ı f : V (G) → {1, 2, 3, . . . , n} takové, ˇze pro kaˇzdý vrchol x ∈ V (G) plat´ı wf (x) =

P

u∈N (x) f (u)

= k;

1

´ UVOD

11

kde k je magick´ a konstanta. 1-VMV ohodnocen´ı se také ˇcasto oznaˇcuje anglick´ ym názvem ”distance magic labeling”. Jedná se o vrcholové ohodnocen´ı, které pˇriˇrazuje kaˇzdému vrcholu z grafu G ˇc´ıslo z mnoˇziny pˇrirozen´ ych ˇc´ısel, tak aby souˇcet hodnot sousedn´ıch vrchol˚ u byl stejn´ y pro vˇsechny vrcholy v grafu G. Pokud má nˇejak´ y graf takové ohodnocen´ı, existuje v tomto grafu magická konstanta k. Pˇr´ıklad grafu s 1-VMV ohodnocen´ım je na obrázku 12. Definice 1.2.13. Stupeˇ n vrcholu x je roven poˇctu vˇsech hran, které jsou s vrcholem x incidentn´ı. Stupeˇ n vrcholu x znaˇc´ıme deg(x). Ze stupnˇe vrcholu x také z´ıskáváme informaci o tom, s kolika vrcholy je vrchol x sousedn´ı. Je zˇrejmé, ˇze stupeˇ n ˇzádného vrcholu nem˚ uˇze b´ yt vˇetˇs´ı neˇz poˇcet vrchol˚ u v grafu bez vrcholu samotného. Vrchol sám se sebou nem˚ uˇze b´ yt v jednoduchém grafu sousedn´ı. Nejvyˇsˇs´ı moˇzn´ y stupeˇ n, kterého m˚ uˇze vrchol x ∈ V (G) nab´ yvat, je deg(x) = |V (G)| − 1. Definice 1.2.14. Pravidelný nebo také regul´ arn´ı graf je graf, který m´ a vˇsechny vrcholy stejného stupnˇe. ˇ Casto se takové to grafy oznaˇcuj´ı napˇr´ıklad 3-pravideln´ y, kde ˇc´ıslovka pˇred slovem pravideln´ y udává stupeˇ n vrchol˚ u v pravidelném grafu. 3-pravideln´ y graf má tedy vˇsechny vrcholy stupnˇe 3.

Obrázek 13: 3-pravideln´ y graf

Definice 1.2.15. Kompozice nebo také sloˇzen´ı graf˚ u G a H je graf, který m´ a vrcholovou mnoˇzinu V (G)×V (H) a dva vrcholy (u1 , v1 ) a (u2 , v2 )∈ V (G)×V (H) jsou spojeny hranou pr´ avˇe tehdy, kdyˇz plat´ı u1 = u2 a v1 v2 ∈ E(H), nebo u1 u2 ∈ E(G). Kompozici grafu G a H (v tomto poˇrad´ı) znaˇc´ıme G[H]. Kompozici si m˚ uˇzeme pˇredstavit jako sloˇzen´ı libovolného grafu s nˇejak´ ym jin´ ym grafem. Pokud máme tedy graf Kp s 10 vrcholy (p = 10) a sloˇz´ıme tento graf s grafem Kn se

1

´ UVOD

12

ˇ 4 vrcholy (n = 4), bude m´ıt v´ ysledn´ y graf Kp [Kn ] 40 vrchol˚ u. Casto také poˇzadujeme, aby se pˇri kompozici dvou graf˚ u neporuˇsila vlastnost b´ yt pravideln´ y. Technika kompozice je v teorii 1-VMV graf˚ u velice uˇziteˇcná a pouˇz´ıvaná. Vybrané vˇety, kde je kompozice pouˇzita, jsou uvedené v podkapitole 1.3.

1.3

Pˇ rehled zn´ am´ ych v´ ysledk˚ u

V této kapitole se seznám´ıme se základn´ımi v´ ysledky dosaˇzen´ ymi na poli 1-VMV graf˚ u. Tyto v´ ysledky byly objeveny nezávisle na sobˇe. 1.3.1

Z´ akladn´ı v´ ysledky

Vˇ eta 1.1. ([1]) Necht’ m, n > 1. Kompletn´ı m-partitn´ı graf, který m´ a kaˇzdou partitu velikosti n, je 1-VMV grafem tehdy a jen tehdy, pokud n je sudé, nebo pokud n a m jsou souˇcasnˇe lich´ a ˇc´ısla. Vˇ eta 1.2. ([1]) Necht’ f je magické ohodnocen´ı grafu G = (V, E) pak P

x∈V (G) deg(x)f (x)

= kn,

kde n je poˇcet vrchol˚ u v grafu G a k je magick´ a konstanta. D˚ usledek 1.1. ([1]) Necht’ G je r-pravidelný 1-VMV graf s magickou konstantou k na n vrcholech pak plat´ı: k=

r(n+1) 2

D˚ usledek 1.2. ([1]) Neexistuje takový 1-VMV r-pravidelný graf a kde r je liché. Vˇ eta 1.3. ([1]) • Cesta Pn je 1-VMV graf pr´ avˇe tehdy a jen tehdy, kdyˇz n = 1, nebo n = 3. • Cyklus Cn je 1-VMV graf pr´ avˇe tehdy a jen tehdy, kdyˇz n = 4. • Kompletn´ı graf Kn je 1-VMV graf pr´ avˇe tehdy a jen tehdy, kdyˇz n = 1. • Kolo Wn = Cn + K1 je 1-VMV graf pr´ avˇe tehdy a jen tehdy, kdyˇz n = 4. • Strom T je 1-VMV graf pr´ avˇe tehdy a jen tehdy, kdyˇz T = P1 , nebo T = P3 . Tuto skupinu vˇet m˚ uˇzeme povaˇzovat za jádro teorie 1-VMV graf˚ u. Obsahuj´ı základn´ı vzorec (Vˇeta 1.2), z tohoto vztahu m˚ uˇzeme odvodit vzorec pro v´ ypoˇcet magické konstanty . Pokud tedy máme nˇejak´ y pravideln´ y graf G, kter´ y je 1-VMV, m˚ uˇzeme pro k = r(n+1) 2 tento graf za pˇredpokladu, ˇze známe poˇcet vrchol˚ u n a pravidelnost r dopoˇc´ıtat magickou konstantu k. Jako pˇr´ıklad si m˚ uˇzeme uvést 14-pravideln´ y graf na 19 vrcholech. Jak je ukázáno v kapitole 2, tento graf je 1-VMV grafem. M˚ uˇzeme tedy dosadit hodnoty do vzorce:

1

´ UVOD

13 k = r(n+1) , 2 14(19+1) , k= 2 k = 140,

magická konstanta je tedy 140. Pod´ıv´ ame-li se na tento vzorec podrobnˇeji, zjist´ıme, ˇze nem˚ uˇzeme za pravidelnost dosadit liché ˇc´ıslo a poˇcet vrchol˚ u sudé ˇc´ıslo. Pokud bychom tak uˇcinili, vyˇsla by nám magická konstanta jako desetinné ˇc´ıslo. Z definice magické konstanty je zˇrejmé, ˇze k mus´ı b´ yt celé ˇc´ıslo. Po tomto zjiˇstˇen´ı tedy m˚ uˇzeme ˇr´ıct, ˇze neexistuje 1-VMV, graf kter´ y by mˇel lichou pravidelnost. Pro sudá n to vypl´ yvá z d˚ usledku 1.1, pro lichá n z principu sudosti. Vˇeta 1.1 hovoˇr´ı o kompletn´ıch multipartitn´ıch grafech. Máme-li graf s m partitami a nav´ıc kaˇzdá partita má velikost n, kde m, n > 1, potom tento graf m˚ uˇze b´ yt distance magic pouze tehdy, je-li n sudé, nebo n a m jsou lichá ˇc´ısla. Jinak ˇreˇceno neexistuje kompletn´ı multipartitn´ı 1-VMV graf, kter´ y by mˇel sud´ y poˇcet partit a lich´ y poˇcet vrchol˚ u.

Obrázek 14: Cesta s 1-VMV ohodnocen´ım a magickou konstantou k = 3 Dále jsou zde uvedeny poˇcty vrchol˚ u pro nˇekolik základn´ıch tˇr´ıd graf˚ u, pro které existuje 1-VMV graf dané tˇr´ıdy. Jako prvn´ı m˚ uˇzeme zm´ınit graf cesty Pn . Takov´ y graf m˚ uˇze byt distance magic pouze ve dvou pˇr´ıpadech. Prvn´ım je, ˇze tuto cestu vytvoˇr´ıme pouze jedn´ım vrcholem. Takov´ y graf je 1-VMV vˇzdy. Druhou moˇznost´ı je vytvoˇrit cestu tˇremi vrcholy a dvˇemi hranami, pˇr´ıklad této cesty je na Obrázku 14. Na cestu m˚ uˇzeme nahl´ıˇzet jako na speciáln´ı typ stromu. Pro stromy jsou poˇcty vrchol˚ u umoˇzn ˇuj´ıc´ı existenci 1-VMV stejné. Tedy bud’ strom tvoˇren´ y jedn´ım, nebo tˇremi vrcholy. Dalˇs´ım typem grafu je graf kolo. Tento graf podle definice vznikne ze dvou ˇcást´ı. Prvn´ı ˇca´st tvoˇr´ı nˇejak´ y cyklus, druhou ˇcást tvoˇr´ı samostatn´ y vrchol, kter´ y je sousedn´ı se vˇsemi vrcholy v cyklu. Takov´ y graf m˚ uˇze b´ yt 1-VMV pouze tehdy, pokud cyklus, kter´ y tvoˇr´ı prvn´ı ˇcást tohoto grafu, bude sestrojen ˇctyˇrmi vrcholy. Pokud z kola Wn = C4 + K1 , které je magic distance, odebereme vrchol K1 , z´ıskáme cyklus C4 . Protoˇze vˇsem vrchol˚ um v tomto cyklu vezmeme jednoho souseda, zmenˇs´ı se váha kaˇzdého vrcholu o stejné ˇc´ıslo. Tento cyklus bude tedy 1-VMV. Pro jin´ y poˇcet vrchol˚ u neˇz n = 4 1-VMV cyklus neexistuje. Pˇri aplikaci uveden´ ych vˇet v podkapitole 1.3.1 na ne´ uplné turnaje se dozv´ıdáme, ˇze nem˚ uˇzeme uspoˇrádat ne´ upln´ y vyrovnan´ y turnaj takov´ y, kde kaˇzd´ y t´ ym bude hrát lich´ y poˇcet zápas˚ u. V pˇr´ıpadˇe ne´ uplného vyrovnaného turnaje jsme také schopni vypoˇc´ıtat obt´ıˇznost turnaje pro jednotlivé t´ ymy (jde o vyrovnan´ y turnaj, je tedy tato obt´ıˇznost pro vˇsechny t´ ymy stejná). Obt´ıˇznost turnaje je ekvivalentem pro magickou konstantu, budeme tedy dosazovat do vzorce k = r(n+1) , kde k je v´ ysledná obt´ıˇznost turnaje, r je 2 poˇcet zápas˚ u, kter´ y kaˇzd´ y t´ ym odehraje a n je poˇcet t´ ym˚ u v turnaji.

1

´ UVOD

1.3.2

14

Sud´ y poˇ cet vrchol˚ u

Existence 1-VMV grafu je pro sud´ y poˇcet vrchol˚ u zcela vyˇreˇsena, proto se pˇri hledán´ı 14-pravideln´ ych 1-VMV graf˚ u budeme zab´ yvat pouze lich´ ym poˇctem vrchol˚ u. Vˇ eta 1.4. ([2]) r-pravidelný 1-VMV graf na sudém n existuje pr´ avˇe tehdy, je-li r-sudé v rozmez´ı 2 ≤ r ≤ n−2, r ≡ 0 (mod 2) a je splnˇen´ a nˇekter´ a z n´ asleduj´ıc´ıch dvou podm´ınek: • r ≡ 0 (mod 4) • n ≡ r + 2 ≡ 2 (mod 4) V praxi to znamená, ˇze nem˚ uˇzeme uspoˇrádat ne´ upln´ y vyrovnan´ y turnaj, pokud poˇcet t´ ym˚ u i poˇcet zápas˚ u, které tyto t´ ymy maj´ı odehrát, nen´ı dˇeliteln´ y 4 beze zbytku. Jako pˇr´ıklad si m˚ uˇzeme pˇredstavit turnaj s 10 t´ ymy, kde kaˇzd´ y t´ ym má hrát 6 zápas˚ u. Poˇcet t´ ym˚ u 10 nen´ı beze zbytku dˇeliteln´ y 4 (10/4 = 2 zbytek 2), poˇcet zápas˚ u, kter´ y kaˇzd´ y t´ ym má odehrát, také nen´ı beze zbytku dˇeliteln´ y 4 (6/4 = 1 zbytek 2). Tento turnaj tedy nem˚ uˇze b´ yt vyrovnan´ y dle Vˇety 1.4. Vˇ eta 1.5. ([1]) Necht’ G je libovolný r-pravidelný graf. Pak G[K n ] je 1-VMV pro vˇsechna sud´ a n. Tato vˇeta nám tedy ˇr´ıká, máme-li libovoln´ y r-pravideln´ y graf G, m˚ uˇzeme provést u n v grafu K n kompozici (sloˇzen´ı grafu) grafu G s grafem K n tak, ˇze pokud poˇcet vrchol˚ y bude sud´ y, potom tento graf bude 1-VMV. Vˇsimnˇete si, ˇze v´ ysledn´ y graf G[K n ] má sud´ poˇcet vrchol˚ u. Vˇ eta 1.6. ([1]) Necht’ G je libovolný r-pravidelný graf s k vrcholy, kde k je liché ˇc´ıslo a n je liché pˇrirozené ˇc´ıslo. Pak r je sudé a graf G[K n ] je 1-VMV graf. Pˇredstavme si, ˇze máme opˇet graf G, tentokrát s lich´ ym poˇctem vrchol˚ u. Provedeme kompozici tohoto graf s grafem K n , kter´ y má také lich´ y poˇcet vrchol˚ u. Pokud nav´ıc pravidelnost (r) bude sudé ˇc´ıslo, tak v´ ysledn´ y graf kompozice G[K n ] je 1-VMV graf. Vˇ eta 1.7. ([1]) Graf mKp [K n ], kde np je liché a m je sudé, p > 1, m ≥ 2 je 1-VMV pr´ avˇe tehdy, kdyˇz p ≡ 3 (mod 4). Z Vˇety 1.7 tedy plyne, ˇze m˚ uˇzeme sloˇzit m kopi´ı grafu Kp s grafem K n tak, aby byl v´ ysledn´ y graf 1-VMV, pokud plat´ı, ˇze: • np je liché a m je sudé, • p > 1, m ≥ 2 • p ≡ 3 (mod 4).

1

´ UVOD

1.3.3

15

Lich´ y poˇ cet vrchol˚ u

Pokud bychom chtˇeli sestrojit nˇejak´ y pravideln´ y 1-VMV graf na lichém poˇctu vrchol˚ u, m˚ uˇzeme vyuˇz´ıt následuj´ıc´ı vˇety. Vˇ eta 1.8. ([1]) Necht’ m ≥ 1, n > 1 a p ≥ 3. mCp [K n ] m´ a 1-VMV ohodnocen´ı pr´ avˇe tehdy, kdyˇz n je sudé nebo mnp je liché nebo n je liché a p ≡ 0 (mod 4). V této vˇetˇe se opˇet setkáváme s pojmem kompozice (sloˇzen´ı) graf˚ u. Z Vˇety 1.8 se dozv´ıdáme, ˇze za pˇredpokladu, kdy poˇcet vrchol˚ u v cyklu Cp je nejménˇe tˇri (p ≥ 3), poˇcet vrchol˚ u v doplˇ nku u ´plného grafu K n je vˇetˇs´ı neˇz jedna (n > 1) a vezmeme nejménˇe jednu kopii (m ≥ 1), potom m˚ uˇzeme sestrojit lich´ y poˇcet m-kopi´ı grafu Cp s grafem K n , tak, y, aby v´ ysledn´ y graf této kompozice byl 1-VMV, pokud poˇcet vrchol˚ u v grafu K n je sud´ nebo souˇcin poˇctu kopi´ı m, vrchol˚ u v grafu Cp a grafu K n je liché ˇc´ıslo (mnp je liché), nebo pokud je poˇcet vrcholu v cyklu Cp dˇeliteln´ y ˇctyˇrmi bezezbytku (p ≡ 0 (mod 4)). 1.3.4

r-pravideln´ e grafy s malou hodnotou r

Existence 1-VMV ohodnocen´ı pravideln´ ych graf˚ u je na lichém poˇctu vrchol˚ u zcela vyˇreˇsena pro 2-, 4-, 6-, 8-, 10- a 12-pravidelné grafy. Vˇ eta 1.9. ([1]) Graf G na n vrcholech je 1-VMV graf s magickou konstantou k = n + 1 pr´ avˇe tehdy a jen tehdy, kdyˇz G = tC4 , kde t je pˇrirozené ˇc´ıslo. 2-pravideln´ y 1-VMV graf existuje pouze na sudém poˇctu vrchol˚ u, jinak ˇreˇceno, 1-VMV 2-pravideln´ y graf G existuje pouze je-li G t kopi´ı cyklu C4 , tedy na 4, 8, 12, 16 . . . vrcholech. Z vˇety 1.8 je zˇrejmé, ˇze na lichém poˇctu vrchol˚ u neexistuje 2-pravideln´ y graf takov´ y, kter´ y by mˇel 1-VMV hodnocen´ı. Vˇ eta 1.10. ([3]) 4-pravidelný 1-VMV graf na lichém poˇctu n existuje pr´ avˇe tehdy a jen tehdy, kdyˇz n ≥ 17. Je zˇrejmé, ˇze z tvrzen´ı vˇety o 1-VMV 4-pravideln´ ych grafech na lichém poˇctu vrchol˚ u vypl´ yvá, ˇze takov´ y nejmenˇs´ı graf existuje na 17 vrcholech a pro vˇsechna lichá n vˇetˇs´ı. Pro sudá n uˇz od 6 vrchol˚ u. Vˇ eta 1.11. ([4]) 6-pravidelný 1-VMV graf na lichém poˇctu n existuje pr´ avˇe tehdy a jen tehdy, kdyˇz n = 9, nebo n ≥ 13. 1-VMV 6-pravideln´ y graf na sudém poˇctu vrchol˚ u existuje na n = 8 a dále pro vˇsechna n ≥ 12. Nejmenˇs´ı 6-pravideln´ y 1-VMV graf na lichém poˇctu vrcholu existuje na 9 vrcholech. M˚ uˇzeme tedy ˇr´ıct, ˇze 6-pravideln´ y 1-VMV graf existuje, pro vˇsechna lichá n vˇetˇs´ı, nebo rovno 9 s vyj´ımkou n = 11. 1-VMV graf na 11 vrcholech s pravidelnost´ı 6 neexistuje. Vˇ eta 1.12. ([4]) 8-pravidelný 1-VMV graf na lichém poˇctu n existuje pr´ avˇe tehdy a jen tehdy, kdyˇz n ≥ 15.

1

´ UVOD

16

Nejmenˇs´ı 8-pravideln´ y 1-VMV graf existuje pro sudá n na n = 10, n = 12 a dále pro vˇsechna n ≥ 14. V pˇr´ıpadˇe 8-pravideln´ ych graf˚ u na lichém poˇctu vrchol˚ u je hranice existence 1-VMV ohodnocen´ı na 15 vrcholech. 1-VMV 8-pravideln´ y graf m˚ uˇze existovat, pokud poˇcet vrchol˚ u je lich´ y a je nejménˇe 15. Vˇ eta 1.13. ([4]) 10-pravidelný 1-VMV graf na lichém poˇctu n existuje pr´ avˇe tehdy a jen tehdy, kdyˇz n ≥ 15. Na sudém n m˚ uˇze existovat 10-pravideln´ y 1-VMV graf, pokud n = 12, a n ≥ 14. V pˇr´ıpadˇe lichého poˇctu u vrcholu u 10-pravideln´ ych graf˚ u, je hranice existence stejná jako u graf˚ u 8-pravideln´ ych. Tedy pro vˇsechny grafy, které maj´ı poˇcet vrchol˚ u lich´ y a nejménˇe 15, m˚ uˇze existovat 1-VMV 10-pravideln´ y graf. Vˇ eta 1.14. ([4]) 12-pravidelný 1-VMV graf na lichém poˇctu n existuje pr´ avˇe tehdy a jen tehdy, kdyˇz n ≥ 15. 12-pravidelné 1-VMV grafy existuj´ı na sudém poˇctu vrchol˚ u jen tehdy, pokud n ≥ 14. 1-VMV 12-pravidelné grafy mohou existovat pro lichá n, pouze pokud plat´ı n ≥ 15, stejnˇe jako u 8 nebo 10 pravideln´ ych graf˚ u. 1.3.5

Grafy, pro kter´ e 1-VMV ohodnocen´ı neexistuje

Pokud se zab´ yváme 1-VMV grafy, m˚ uˇzeme se také zaj´ımat o to, jak pozn´ ame, ˇze pro nˇejak´ y graf 1-VMV ohodnocen´ı neexistuje. V následuj´ıc´ım souboru vˇet je ukázáno, pro které grafy 1-VMV ohodnocen´ı neexistuje. Vˇ eta 1.15. ([1]) Necht’ u a v jsou vrcholy z 1-VMV grafu G. Pak |N (u) ⊕ N (v)| = 0 nebo |N (u) ⊕ N (v)| ≥ 3 (symbolem A ⊕ B znaˇc´ıme symetrickou diferenci mnoˇziny A a mnoˇziny B ). Setkáváme se zde s pojmem symetrická diference mnoˇzin. Tato mnoˇzinová operace je nˇekdy také oznaˇcována jako symetrick´ y rozd´ıl, A ⊕ B je tedy mnoˇzina prvk˚ u, které náleˇz´ı do A nebo do B, nikoliv vˇsak do A i do B souˇcasnˇe. D˚ usledek 1.3. ([1]) Necht’ G je graf ˇra ´du n, který m´ a dva vrcholy stupnˇe n − 1. Pak G nen´ı 1-VMV. Pokud se v libovolném grafu nacházej´ı dva vrcholy stejného stupnˇe velikosti n − 1 (deg(u)P = deg(v) = n − 1), potom tento graf nem˚ uˇze b´ yt 1-VMV, protoˇze z celkového souˇctu ni=1 (i), bude kaˇzdému vrcholu scházet jiné ˇc´ıslo. D˚ usledek 1.4. ([1]) Kaˇzdý kompletn´ı multipartitn´ı graf se dvˇema partitami velikosti 1 nen´ı 1-VMV. Máme-li multipartitn´ı graf se dvˇema partitami, kde kaˇzdá partita má 1 vrchol, tak tento graf nen´ı nic jiného neˇz dva sousedn´ı vrcholy. Takov´ y graf nem˚ uˇze b´ yt nikdy 1-VMV. D˚ usledek 1.5. ([1]) Pokud graf G m´ a cestu (u, v, w, t, p) se stupnˇem vrchol˚ u deg(v) = deg(t) = 2, pak G nen´ı 1-VMV.

1

´ UVOD

17

Sdˇelen´ı této vˇety je zcela zˇrejmé. Jsou-li stupnˇe vrchol˚ u v a t v cestˇe (u, v, w, t, p) rovny dvˇema, potom graf obsahuj´ıc´ı tuto cestu nemá 1-VMV ohodnocen´ı. Pokud plat´ı deg(v) = deg(u) = 2, potom váha vrcholu v je rovna Wf (v) = f (u) + f (v)= wf (t) = f (w) + f (p), kde ohodnocen´ı f (w) se zkrát´ı pro f (u) = f (v), coˇz nen´ı moˇzné. Z toho vypl´ yvá, ˇze f nen´ı injektivn´ı a graf nen´ı 1-VMV. Vˇ eta 1.16. ([1]) Pokud G obsahuje dva vrcholy u a v takové ˇze |N (u) ∩ N (v)| = deg(v) − 1 = deg(u) − 1, pak G nem´ a 1-VMV ohodnocen´ı. Pokud pr˚ unik mnoˇziny sousedn´ıch vrchol˚ u vrcholu u a vrcholu v je o jedniˇcku menˇs´ı neˇz stupeˇ n vrcholu v a souˇcasnˇe o jedniˇcku menˇs´ı neˇz stupeˇ n vrcholu u, potom tento graf nemá 1-VMV ohodnocen´ı. Obecnˇejˇs´ı neˇz d˚ usledek 1.3. Vˇ eta 1.17. ([1]) Necht’ G je graf na n vrcholech s maxim´ aln´ım stupnˇem △ a minim´ aln´ım stupnˇem δ. Pokud △(△ + 1) > δ(2n − δ + 1) pak G nen´ı 1-VMV. Jsou-li v grafu velké rozd´ıly mezi stupni vrchol˚ u, tak v takovém grafu neexistuje 1VMV ohodnocen´ı. Vˇ eta 1.18. ([1]) Graf mKp [K n ] kde np je liché, m je sudé, p ≡ 1 (mod 4) a p > 1, nen´ı 1-VMV. O grafu mKp [K n ] jsme se jiˇz v podkapitole 1.3 zmiˇ novali. Kdy pro tento graf 1-VMV u v grafu ohodnocen´ı neexistuje? Pokud je souˇcin poˇctu vrchol˚ u v grafu K n a poˇctu vrchol˚ Kp lich´ y (np je liché), poˇcet kopii je sud´ y (m je sudé), p je vˇetˇs´ı neˇz jedna (p > 1) a nen´ı dˇelitelné 4 bezezbytku (p ≡ 1 (mod 4)), potom tento graf nen´ı 1-VMV. Vˇ eta 1.19. ([1]) Necht’ n je liché, k ≡ r ≡ 2 (mod 4) a G je r-pravidelný graf s k vrcholy. Pak G[K n ] nen´ı 1-VMV. Vezmeme-li r-pravideln´ y graf G na k vrcholech a provedeme jeho kompozici (sloˇzen´ı) y má lich´ y poˇcet vrchol˚ u (n je liché), potom tento s doplˇ nkem kompletn´ıho grafu K n , kter´ graf nen´ı 1-VMV pokud, k i r dávaj´ı zbytek 2 po dˇelen´ı 4.

´ VYSLEDKY ´ 2 NOVE

2

18

Nov´ e v´ ysledky

V této podkapitole jsou zahrnuty nové v´ ysledky, kter´ ych jsme dosáhli pˇri práci na této bakaláˇrské práci. Jak jiˇz bylo zm´ınˇeno v podkapitole 1.3, pro sud´ y poˇcet vrchol˚ u je existence pravideln´ ych 1-VMV graf˚ u vyˇreˇsena. Z tohoto d˚ uvodu jsme se zab´ yvali pouze grafy s lich´ ym poˇctem vrchol˚ u, pˇresnˇeji existenc´ı 1-VMV ohodnocen´ı 14-pravideln´ ych graf˚ u na lichém poˇctu vrchol˚ u.

2.1

14-pravideln´ e grafy

V ˇclánku ([5]) byly nalezeny vˇsechny (n − 3)-pravidelné grafy na n vrcholech. Vˇ eta 2.1. ([5]) (n − 3) pravidelný graf na n vrcholech existuje pr´ avˇe, tehdy kdyˇz n ≡ 0 (mod 3). Nav´ıc struktura grafu je jednoznaˇcnˇe urˇcena-jedn´ a se o K n3 [K 3 ]. Nyn´ı ukáˇzeme, ˇze: Vˇ eta 2.2. 14-pravidelný 1-VMV graf na n vrcholech neexistuje pro ˇza ´dné n < 19. D˚ ukaz. Nejmenˇs´ı pˇr´ıpad, kdy lze sestrojit 14-pravideln´ y graf, je na 15 vrcholech. Takov´ y graf naz´ yváme grafem kompletn´ım. V tomto grafu je kaˇzd´ y vrchol v1 , v2 , . . . , v15 spojen´ y hranou se vˇsemi zb´ yvaj´ıc´ımi 14 vrcholy. Pro vrchol s ohodnocen´ım i je váha v magickém ohodnocen´ı wi rovna souˇctu vah vrchol˚ u sousedn´ıch, w(vi ) = f (v1 )+f (v2 )+. . .+f (v15 , )− f (vi ), z toho plyne, ˇze pro kaˇzd´ y vrchol v takovémto grafu bude váha jiná. Graf K15 nemá 1-VMV. Z Vˇety 2.1 je zˇrejmé, ˇze ani na 17 vrcholech neexistuje 14-pravideln´ y 1-VMV graf, protoˇze 17 nen´ı dˇelitelné ˇc´ıslem 3. 2.1.1

Podgraf A

V následuj´ıc´ı konstrukci budeme pouˇz´ıvat graf A. Proto si jej nyn´ı pop´ıˇseme. Graf A je uspoˇrádaná dvojice A = (V ′ , E ′ ), kde V ′ (A) je mnoˇzina vrchol˚ u: V ′ (A) = {x1 , x2 , x3 , x4 , x5 , x6 , y1 , y2 , y3 , y4 y5 , y6 } a E ′ (A) je mnoˇzina vˇsech hran: E ′ (A) = {x1 x2 , x1 y2 , y1 x2 , y1 y2 , x2 x3 , x2 y2 , y3 x2 , y2 y3 , x1 x3 , x1 y3 , y1 x3 , y1 y3 , x3 x4 , x3 y4 , y3 x4 , y3 y4 , x4 x5 , x4 y5 , y4 x5 , y4 y5 , x5 x6 , x5 y6 , y5 x6 , y5 y6 , x4 x6 , x4 y6 , y4 x6 , y4 y6 , x1 x6 , x1 y6 , y1 x6 , y1 y6 , }


19

Pro vrcholy x1 , y1 , . . . , xn , yn bude platit: f (x1 ) + f (y1 ) = f (x2 ) + f (y2 ) = f (x3 ) + f (y3 ) = f (x4 ) + f (y4 ) = f (x5 ) + f (y5 ) = f (x6 ) + f (y6 ) = n + 1. Hrany, které nejsou tuˇcnˇe zv´ yraznˇeny x1 x2 , x1 y2 , y1 x2 , y1 y2 , x1 x3 , x1 y3 , y1 x3 , y1 y3 , x3 x4 , x3 y4 , y3 x4 , y3 y4 , x4 x5 , x4 y5 , y4 x5 , y4 y5 , x4 x6 , x4 y6 , y4 x6 , y4 y6 , x1 x6 , x1 y6 , y1 x6 , y1 y6 , budou pˇri vytváˇren´ı grafu G′ z podgrafu A odstranˇeny. Tyto hrany jsou v obrázku 15 zv´ yraznˇeny ˇcervenou barvou. Dále budeme mnoˇzinu hran, které maj´ı b´ yt odstranˇeny, oznaˇcovat velk´ ym p´ısmenem O. Naopak hrany zv´ yraznˇené tuˇcnˇe jsou, v obrázku 15 zv´ yraznˇeny barvou zelenou: x2 x3 , x2 y2 , y3 x2 , y2 y3 , x5 x6 , x5 y6 , y5 x6 , y5 y6 , v podgrafu A ponecháme, budou d˚ uleˇzité v dalˇs´ım kroku konstrukce.

Obr´ azek 15: Podgraf A


2.1.2

20

D˚ ukaz existence 14-pravideln´ ych 1-VMV graf˚ u

Nyn´ı ukáˇzeme: Vˇ eta 2.3. Pokud existuje 14-pravidelný 1-VMV graf G na n vrcholech, kde n ≥ 19 a n je liché s podgrafem A (Obr´ azek 15), kde f (x1 ) + f (y1 ) = f (x2 ) + f (y2 ) = f (x3 ) + f (y3 ) = f (x4 ) + f (y4 ) = f (x5 ) + f (y5 ) = f (x6 ) + f (y6 ) = n + 1, pak existuje 14-pravidelný 1-VMV graf na n + 4t vrcholech pro vˇsechna nez´ aporn´ a cel´ a ˇc´ısla t. D˚ ukaz. D˚ ukaz provedeme indukc´ı vzhledem k poˇctu vrchol˚ u, ukáˇzeme, ˇze pokud máme 14-pravideln´ y 1-VMV graf G na n vrcholech (n ≥ 19 a n je liché) s podgrafem A u kterého plat´ı: f (x1 ) + f (y1 ) = f (x2 ) + f (y2 ) = f (x3 ) + f (y3 ) = f (x4 ) + f (y4 ) = f (x5 ) + f (y5 ) = f (x6 ) + f (y6 ) = n + 1. Pak m˚ uˇzeme sestavit na |V (G) + 4| vrcholech 1-VMV graf G′ takov´ y, kter´ y bude obsahovat jin´ y podgraf A′ , kde bude pro nˇejaké vrcholy x′1 , y1′ , . . . , x′n , yn′ platit f (x′1 ) + f (y1′ ) = f (x′2 ) + f (y2′ ) = f (x′3 ) + f (y3′ ) = f (x′4 ) + f (y4′ ) = f (x′5 ) + f (y5′ ) = f (x′6 ) + f (y6′ ) = n + 5. Zároveˇ n bude graf G′ m´ıt 1-VMV ohodnocen´ı. Pˇredpokládejme, ˇze G je 14-pravideln´ y 1-VMV graf na n vrcholech (kde n ≥ 19 a n je liché) s magick´ ym ohodnocen´ım f , kter´ y obsahuje podgraf A. Obrázek 16 znázorˇ nuje pˇridán´ı 4 nov´ ych vrchol˚ u s1 , s2 , s3 , s4 do podgrafu A grafu G. ′ Novˇe vznikl´ y graf budeme oznaˇcovat G . Ukáˇzeme, ˇze existuje 1-VMV ohodnocen´ı f ′ grafu ′ G na n + 4 vrcholech, kde G′ vznik´ a z G odstranˇen´ım 24 hran mnoˇziny O (tyto hrany jsou na Obrázku 16 zakresleny ˇcervenou barvou), pˇridán´ım 4 nov´ ych vrchol˚ u s1 , s2 , s3 , s4 , pro které plat´ı: f (s1 ) + f (s2 ) = f (s3 ) + f (s4 ) = n + 5 a pˇridán´ım dalˇs´ıch 52 hran. V Obr´ azku 16 jsou pˇridané hrany zakresleny barvou ˇcernou a modrou, jsou to hrany: s1 x1 , s1 x2 , s1 x3 , s1 x4 , s1 x5 , s1 x6 , s1 y1 , s1 y2 , s1 y3 , s1 y4 , s1 y5 , s1 y6 , s2 x1 , s2 x2 , s2 x3 , s2 x4 , s2 x5 , s2 x6 , s2 y1 , s2 y2 , s2 y3 , s2 y4 , s2 y5 , s2 y6 , s3 x1 , s3 x2 , s3 x3 , s3 x4 , s3 x5 , s3 x6 , s3 y1 , s3 y2 , s3 y3 , s3 y4 , s3 y5 , s3 y6 , s4 x1 , s4 x2 , s4 x3 , s4 x4 , s4 x5 , s4 x6 , s4 y1 , s4 y2 , s4 y3 , s4 y4 , s4 y5 , s4 y6 Mnoˇzinu pˇridan´ ych hran dále budeme oznaˇcovat velk´ ym p´ısmenem P . Je zˇrejmé, ˇze budeme-li provádˇet operace pˇridáván´ı a odeb´ırán´ı hran, m˚ uˇzeme t´ım naruˇsit pravidelnost grafu. Pokud odebereme hrany O, tak se vrchol˚ um x1 , x2 , x3 , x4 , x5 , x6 , y1 , y2 , y3 , y4 , y5 , y6 zmenˇs´ı stupeˇ n o 4. Znamená to tedy, ˇze jejich stupeˇ n nyn´ı bude pouze (14 − 4) = 10. Chybˇej´ıc´ı 4 hrany kaˇzdého vrcholu dopln´ıme pˇridán´ım hran z mnoˇziny P . Kaˇzd´ y vrchol x1 , x2 , x3 , x4 , x5 , x6 , y1 , y2 , y3 , y4 , spoj´ıme jednou hranou s kaˇzd´ ym z vrchol˚ u s1 , s2 , s3 , s4 . T´ım budeme m´ıt u vrchol˚ u x1 , x2 , x3 , x4 , x5 , x6 , y1 , y2 , y3 , y4 opˇet zajiˇstˇen stupeˇ n 14. Novˇe pˇridané vrcholy s1 , s2 , s3 , s4 maj´ı zat´ım stupeˇ n pouze 12. Chybˇej´ıc´ı dvˇe


21

hrany u vrchol˚ u s1 , s2 , s3 , s4 dopln´ıme pˇridán´ım hran: s1 s3 , s1 s4 , s2 s3 , s2 s4 (modré hrany na obrázku 16). T´ım budeme m´ıt zajiˇstˇen stupeˇ n 14 i u tˇechto zb´ yvaj´ıc´ıch vrchol˚ u.

Obrázek 16: Pˇridán´ı 4 vrchol˚ u do podgrafu A, kter´ y je podgrafem G Pod´ıvejme se na následuj´ıc´ı ohodnocen´ı f ′ grafu G′ .  f (v) + 2     1  n+4 f ′ (v) =   2    n+3

pro pro pro pro pro

v v v v v

∈ V (G), = s1 , = s2 , = s3 , = s4

(1)

Protoˇze ˇc´ısla 1, 2 jsou pˇriˇrazeny vrchol˚ um s1 , s3 a ˇc´ısla 3, 4, . . . , n + 2 jsou na vrcholech V (G) a zb´ yvaj´ıc´ı ˇc´ısla n+3 a n+4 jsou na vrcholech s2 a s4 , tak je kaˇzdé z ˇc´ısel 1, 2, . . . , n+4 pouˇzito právˇe jednou. Je zˇrejmé, ˇze f ′ je bijekc´ı V (G′ ) → {1, 2, . . . , n + 4}. Nyn´ı ukáˇzeme, ˇze váha vˇsech vrchol˚ u v v grafu G′ je 7(n + 5). Zaˇcneme nejprve novˇe pˇridan´ ymi vrcholy s1 , s2 , s3 , s4 . Pro s1 a s2 plat´ı: P wf ′ (s1 ) = wf ′ (s2 ) = 6i=1 (f ′ (xi ) + f ′ (yi )) + f ′ (s3 ) + f ′ (s4 ) =

= f ′ (x1 ) + f ′ (y2 ) + f ′ (x3 ) + f ′ (x4 ) + f ′ (x5 ) + f ′ (x6 ) + f ′ (y1 ) + f ′ (y2 ) + f ′ (y3 ) + f ′ (y4 ) + f ′ (y5 ) + f ′ (y6 ) + f ′ (s3 ) + f ′ (s4 ) = = f (x1 ) + 2 + f (x2 ) + 2 + f (x3 ) + 2 + f (x4 ) + 2 + f (x5 ) + 2 + f (x6 ) + 2 + f (y1 ) + 2 + f (y2 ) + 2 + f (y3 ) + 2 + f(y4 ) + 2 + f (y5 ) +2 + f (y6 ) + 2 + f ′(s3 ) + f ′ (s4 ) = = 12 · 2 + f (x1 ) + f (y1 ) + f (x2 ) + f (y2 ) + f (x3 ) + f (y3 ) + f (x4 ) + f (y4 ) + f (x5 ) + f (y5 ) + f (x6 ) + f (y6 ) + f ′ (s3 ) + f ′ (s4 ) =


22

= 24 + (n + 1) + (n + 1) + (n + 1) + (n + 1) + (n + 1) + (n + 1) + 2 + (n + 3) = = 24 + 6(n + 1) + 2 + (n + 3) = (7n + 35) = = 7(n + 5). Pro s3 a s4 budeme postupovat stejnˇe jako v pˇredeˇslém pˇr´ıpadˇe. P wf ′ (s3 ) = wf ′ (s4 ) = 6i=1 (f ′ (xi ) + f ′ (yi )) + f ′ (s1 ) + f ′ (s2 ) =

= f ′ (x1 ) + f ′ (y2 ) + f ′ (x3 ) + f ′ (x4 ) + f ′ (x5 ) + f ′ (x6 ) + f ′ (y1 ) + f ′ (y2 ) + f ′ (y3 ) + f ′ (y4 ) + f ′ (y5 ) + f ′ (y6 ) + f ′ (s1 ) + f ′ (s2 ) = = f (x1 ) + 2 + f (x2 ) + 2 + f (x3 ) + 2 + f (x4 ) + 2 + f (x5 ) + 2 + f (x6 ) + 2 + f (y1 ) + 2 + f (y2 ) + 2 + f (y3 ) + 2 + f(y4 ) + 2 + f (y5 ) +2 + f (y6 ) + 2 + f ′(s1 ) + f ′ (s2 ) = = 12 · 2 + f (x1 ) + f (y1 ) + f (x2 ) + f (y2 ) + f (x3 ) + f (y3 ) + f (x4 ) + f (y4 ) + f (x5 ) + f (y5 ) + f (x6 ) + f (y6 ) + f ′ (s1 ) + f ′ (s2 ) = = 24 + (n + 1) + (n + 1) + (n + 1) + (n + 1) + (n + 1) + (n + 1) + 1 + (n + 4) = = 24 + 6(n + 1) + 2 + (n + 3) = (7n + 35) = = 7(n + 5). Nyn´ı budeme poˇc´ıtat váhu vrchol˚ u x1 , x2 , x3 , x4 , x5 , x6 , y1 , y2 , y3 , y4 , y5 , y6 . Pro x1 a y1 : wf ′ (x1 ) = wf ′ (y1 ) = = wf (x1 ) + 10 ·2 − f ′ (x6 ) − f ′ (y6 ) − f ′ (x2 ) − f ′ (y2 ) + f ′ (s1 ) + f ′ (s2 ) + f ′ (s3 ) + f ′ (s4 ) = = wf (x) + 20 − f (x6 ) + f (y6 ) + f (x2 ) + f (y2 ) + f ′ (s1 ) + f ′ (s2 ) + f ′ (s3 ) + f ′ (s4 ) = + 20 − 2(n + 1) + 2(n + 5) = = 14(n+1) 2 = 7n + 7 + 20 − 2 + 10 = = 7(n + 5).

U zb´ yvaj´ıc´ıch vrcholu v podgrafu A budeme postupovat stejnˇe. Pro x2 a y2 : wf ′ (x2 ) = wf ′ (y2 ) = = wf (x2 ) + 10 · 2 − f ′ (x6 ) − f ′ (y6 ) − f ′ (x1 ) − f′ (y1 ) + f ′ (s1 ) + f ′ (s2 ) + f ′ (s3 ) + f ′ (s4 ) = = wf (x) + 20 − f (x6 ) + f (y6 ) + f (x1 ) + f (y1 ) + f ′ (s1 ) + f ′ (s2 ) + f ′ (s3 ) + f ′ (s4 ) = = 14(n+1) + 20 − 2(n + 1) + 2(n + 5) = 2 = 7n + 7 + 20 − 2 + 10 = = 7(n + 5). Pro x3 a y3 : wf ′ (x3 ) = wf ′ (y3 ) = = wf (x3 ) + 10 · 2 − f ′ (x4 ) − f ′ (y4 ) − f ′ (x5 ) − f′ (y5 ) + f ′ (s1 ) + f ′ (s2 ) + f ′ (s3 ) + f ′ (s4 ) = = wf (x) + 20 − f (x4 ) + f (y4 ) + f (x5 ) + f (y5 ) + f ′ (s1 ) + f ′ (s2 ) + f ′ (s3 ) + f ′ (s4 ) = + 20 − 2(n + 1) + 2(n + 5) = = 14(n+1) 2 = 7n + 7 + 20 − 2 + 10 = = 7(n + 5).


23

Pro x4 a y4 : wf ′ (x4 ) = wf ′ (y4 ) = = wf (x4 ) + 10 · 2 − f ′ (x3 ) − f ′ (y3 ) − f ′ (x5 ) − f′ (y5 ) + f ′ (s1 ) + f ′ (s2 ) + f ′ (s3 ) + f ′ (s4 ) = = wf (x) + 20 − f (x3 ) + f (y3 ) + f (x5 ) + f (y5 ) + f ′ (s1 ) + f ′ (s2 ) + f ′ (s3 ) + f ′ (s4 ) = = 14(n+1) + 20 − 2(n + 1) + 2(n + 5) = 2 = 7n + 7 + 20 − 2 + 10 = = 7(n + 5). Pro x5 a y5 : wf ′ (x5 ) = wf ′ (y5 ) = = wf (x5 ) + 10 · 2 − f ′ (x3 ) − f ′ (y3 ) − f ′ (x4 ) − f′ (y4 ) + f ′ (s1 ) + f ′ (s2 ) + f ′ (s3 ) + f ′ (s4 ) = = wf (x) + 20 − f (x3 ) + f (y3 ) + f (x4 ) + f (y4 ) + f ′ (s1 ) + f ′ (s2 ) + f ′ (s3 ) + f ′ (s4 ) = + 20 − 2(n + 1) + 2(n + 5) = = 14(n+1) 2 = 7n + 7 + 20 − 2 + 10 = = 7(n + 5). Pro x6 a y6 : wf ′ (x6 ) = wf ′ (y6 ) = = wf (x6 ) + 10 · 2 − f ′ (x1 ) − f ′ (y1 ) − f ′ (x2 ) − f′ (y2 ) + f ′ (s1 ) + f ′ (s2 ) + f ′ (s3 ) + f ′ (s4 ) = = wf (x) + 20 − f (x1 ) + f (y1 ) + f (x2 ) + f (y2 ) + f ′ (s1 ) + f ′ (s2 ) + f ′ (s3 ) + f ′ (s4 ) = + 20 − 2(n + 1) + 2(n + 5) = = 14(n+1) 2 = 7n + 7 + 20 − 2 + 10 = = 7(n + 5). Nyn´ı zb´ yvá vypoˇc´ıtat váhu pro zb´ yvaj´ıc´ı vrcholy v grafu G′ P ′ ′ (v) = wfP u∈NB (V ) f (u) = u∈wG (V ) (f (u) + 2) = wf (v) + 14 · 2 = 14(n+1) + 28 2 = 7(n + 5). T´ımto jsme dokázali, ˇze váha pro vˇsechny vrcholy v grafu G′ je stejná. Sestroj´ıme G′ s n + 4. Opakován´ım postupu t-krát, dostaneme graf s n + 4t vrcholy. D˚ ukaz konˇc´ı. V kapitole 1.3 jsme ukázali, pro jaké poˇcty vrchol˚ u existuj´ı 2-, 4-, 6-, 8-, 10-, 12pravidelné grafy. Nyn´ı ukáˇzeme, pro jaké poˇcty vrchol˚ u existuj´ı 14-pravidelné grafy. Vˇ eta 2.4. 14-pravidelný 1-VMV graf na lichém poˇctu vrchol˚ u existuje pr´ avˇe tehdy, kdyˇz n ≥ 19.


24

D˚ ukaz. Jak jsme dokázali v´ yˇse, pro n < 19 ˇzádn´ y 1-VMV graf na lichém poˇctu vrchol˚ u neexistuje. Na obrázku 17 je nakreslen 1-VMV graf pro n = 19, v tomto grafu je ˇcervenˇe zv´ yraznˇen podgraf A, kter´ y umoˇzn ˇuje konstrukci podle Vˇety 2.3. Z Vˇety 2.3 plyne, ˇze t´ım máme zajiˇstˇeno 1-VMV ohodnocen´ı ve vˇsech n = 19 + 4t grafech, kde t je reálné ˇc´ıslo.

Obrázek 17: 14-pravideln´ y graf na 19 vrcholech s podgrafem A Kompozic´ı grafu na 19 vrcholech o 4 vrcholy ovˇsem nepokryjeme celou mnoˇzinu graf˚ u, pro které plat´ı n ≥ 19. T´ımto postupem vynecháme vˇsechny grafy na n vrcholech, pro které plat´ı: n = 19 + 2c, kde c je liché pˇrirozené ˇc´ıslo. Pro tyto grafy mus´ıme pouˇz´ıt nejlépe nov´ y startovn´ı graf na 21 vrcholech. Jak je vidˇet na Obrázku 18 i tento graf obsahuje poˇzadovan´ y podgraf A. Na tento graf tedy m˚ uˇzeme také pouˇz´ıt techniku Vˇety 2.3, kterou jsem vyuˇzili v pˇr´ıpade grafu na 19 vrcholech. T´ım máme zaruˇceno, ˇze existuje 1-VMV ohodnocen´ı i pro zb´ yvaj´ıc´ı grafy na n = 19 + 2c vrcholech.


25

Obrázek 18: 14-pravideln´ y graf na 21 vrcholech s podgrafem A

2.1.3

Hled´ an´ı podgrafu A ve ”startovn´ıch” grafech.

Nyn´ı si ukáˇzeme, jak´ ym zp˚ usobem jsme hledali podgraf A ve startovn´ıch podgrafech kter´ ymi jsou: • 14-pravideln´ y graf na 19 vrcholech • 14-pravideln´ y graf na 21 vrcholech V pˇr´ıpadˇe grafu s 19 vrcholy jsme postupovali následovnˇe: Pouˇzili jsme pomocn´ y software jehoˇz autorem je Petr Kováˇr, kter´ y hledá pro dan´ y poˇcet vrchol˚ u a danou pravidelnost vˇsechny grafy (tento software je vhodn´ y pouze pro malé poˇcty vrchol˚ u). Jako parametry jsme zadali 19 vrchol˚ u a pravidelnost 14. V´ ysledkem spuˇstˇeného vyhledávan´ı byl seznam vˇsech 14-pravideln´ ych 1-VMV graf˚ u na 19 vrcholech, kter´ y mˇel následuj´ıc´ı podobu: (vybrali jsme ukázku) Labeling #12: Vertex ’ 1’; label=’ Vertex ’ 2’; label=’ Vertex ’ 3’; label=’ Vertex ’ 4’; label=’ Vertex ’ 5’; label=’ Vertex ’ 6’; label=’ Vertex ’ 7’; label=’

1’, 2’, 3’, 4’, 5’, 6’, 7’,

degree=’14’, degree=’14’, degree=’14’, degree=’14’, degree=’14’, degree=’14’, degree=’14’,

neighbours: neighbours: neighbours: neighbours: neighbours: neighbours: neighbours:

2,3,4,5,6,7,8,9,12,14,16,17,18,19 1,3,4,5,7,8,9,10,11,14,15,16,18,19 1,2,4,6,8,9,10,11,12,13,14,15,17,18 1,2,3,5,6,7,10,11,12,13,16,17,18,19 1,2,4,6,8,9,10,11,12,13,14,15,17,18 1,3,4,5,7,8,9,11,12,13,15,16,17,19 1,2,4,6,8,9,10,11,12,13,14,15,16,19


Vertex Vertex Vertex Vertex Vertex Vertex Vertex Vertex Vertex Vertex Vertex Vertex

26

’ 8’; label=’ 8’, degree=’14’, neighbours: 1,2,3,5,6,7,10,12,13,14,15,16,17,19 ’ 9’; label=’ 9’, degree=’14’, neighbours: 1,2,3,5,6,7,10,11,13,14,15,16,18,19 ’10’; label=’10’, degree=’14’, neighbours: 2,3,4,5,7,8,9,11,12,13,15,16,17,18 ’11’; label=’11’, degree=’14’, neighbours: 2,3,4,5,6,7,9,10,13,14,15,16,17,19 ’12’; label=’12’, degree=’14’, neighbours: 1,3,4,5,6,7,8,10,13,14,15,17,18,19 ’13’; label=’13’, degree=’14’, neighbours: 3,4,5,6,7,8,9,10,11,12,14,16,17,18 ’14’; label=’14’, degree=’14’, neighbours: 1,2,3,5,7,8,9,11,12,13,15,17,18,19 ’15’; label=’15’, degree=’14’, neighbours: 2,3,5,6,7,8,9,10,11,12,14,16,18,19 ’16’; label=’16’, degree=’14’, neighbours: 1,2,4,6,7,8,9,10,11,13,15,17,18,19 ’17’; label=’17’, degree=’14’, neighbours: 1,3,4,5,6,8,10,11,12,13,14,16,18,19 ’18’; label=’18’, degree=’14’, neighbours: 1,2,3,4,5,9,10,12,13,14,15,16,17,19 ’19’; label=’19’, degree=’14’, neighbours: 1,2,4,6,7,8,9,11,12,14,15,16,17,18 Pˇr´ıklad v´ ypisu z PC software.

Na pˇr´ıkladu lze vidˇet, ˇze v prvn´ım ˇrádku je udáno ˇc´ıslo grafu, tedy ˇc´ıslo udávaj´ıc´ı poˇrad´ı v jakém byl graf programem objeven. V prvn´ım sloupci jsou jednotlivé vrcholy, ve druhém jejich hodnota, ve tˇret´ım pravidelnost a ve ˇctvrtém jsou vˇsichni sousedé daného vrcholu. Jak bylo jiˇz zm´ınˇeno, v podgrafu A jsou velice d˚ uleˇzité ty dvojice vrchol˚ u, pro které plat´ı f (xi ) + f (yi ) = n + 1. Ve 14-pravidelném grafu na 19 vrcholech jsou dvojice, které tento pˇredpis splˇ nuj´ı následuj´ıc´ı: (1, 19); (2, 18); (3, 17); (4, 16); (5, 15); (6, 14); (7, 13); (8, 12); (9, 11); Zjistili jsme, se kterou dvojic´ı je kaˇzd´ y vrchol spojen´ y. Vezmeme li si napˇr´ıklad vrchol 1, jehoˇz sousedem je vrchol 2 a vrchol 18. Bude tento vrchol spojen´ y s dvojic´ı (2, 18). Takto jsme zjistili vˇsechny ostatn´ı dvojice pro vˇsechny vrcholy. Jakmile jsme vˇsechny tyto dvojice naˇsli, zaˇcali jsme se zab´ yvat t´ım, které dvojice jsou spolu sousedn´ı. Zp˚ usob jak´ ym jsme postupovali si m˚ uˇzeme ukázat napˇr´ıklad na dvojici (1, 19). Pokud jiˇz v´ıme se kterou dvojic´ı je spojen´ y vrchol 1 a vrchol 19, tak dvojice, které jsou pro tyto vrcholy spoleˇcné jsou sousedn´ı s dvojic´ı (1, 19). Tedy pokud je vrchol 1 a 19 spojen´ y s dvojic´ı (2, 18) je dvojice vrchol˚ u (1, 19) s dvojic´ı (2, 18) sousedn´ı. V grafu ve kterém hledáme podgraf A jsem tedy urˇcili, které dvojice vrchol˚ u dávaj´ıc´ı souˇcet vah n + 1 obsahuje a jak jsou tyto dvojce mezi sebou sousedn´ı. Nyn´ı je na ˇradˇe abychom proˇsetˇrili, zda nalezené dvojice, tvoˇr´ı v grafu se kter´ ym pracujeme podgraf A. Pro ulehˇcen´ı hledán´ı podgraf A zjednoduˇs´ıme. Kaˇzdou dvojici která splˇ nuje podm´ınku f (xi ) + f (yi ) = n + 1, si pˇredstav´ıme jako vrchol jeden. Tyto novˇe vzniklé vrcholy oznaˇcme ˇ ri hrany, které jsou mezi q1 , . . . , qm (kde m je poˇcet tˇechto dvojic v prohledávané grafu). Ctyˇ incidentn´ımi dvojicemi vrchol˚ u, splˇ nuj´ıc´ı tuto podm´ınku, znázorn´ıme jako hranu jednu. Na obrázku 19 je zakreslen v´ ysledn´ y zjednoduˇsen´ y podgraf, kter´ y vznikl z grafu A v´ yˇse zm´ınˇen´ ymi u ´pravami. Tento graf budeme znaˇcit B.


27

Obrázek 19: Podgraf B

V posledn´ım kroku budeme dosazovat do schématu na Obrázku 19 jednotlivé vrcholy q1 , . . . , qn a kombinovat je tak aby podgraf B utvoˇrili. Jakmile najdeme takovou kombinaci vrchol˚ u, která tento podgraf tvoˇr´ı, a pˇri tvorbˇe tohoto podgrafu jsme postupovali podle v´ yˇse popsaného postupu, nalezli jsem zároveˇ n podgraf A. Pro graf s 21 vrcholy, jsme postupovali následovnˇe: Tento graf je tripartitn´ı. Kaˇzdá partita má 7 vrchol˚ u, jednotlivé vrcholy v paritˇe jsou sousedn´ı se vˇsemi vrcholy ve zb´ yvaj´ıc´ıch dvou paritách. V jedné partitˇe vrcholy navzájem sousedn´ı nejsou. Pokud tedy tento graf sestav´ıme tak, aby se rovnal souˇcet vrchol˚ u v jednotliv´ ych paritách dostaneme 1-VMV graf. To lze snadno provést. Zaˇcneme t´ım ˇze si nakresl´ıme magick´ y ˇctverec 3 × 3 (Obrázek 20), magick´ y ˇctverec, kter´ y má souˇcet prvk˚ uv jednotliv´ ych sloupc´ıch a ˇrádc´ıch stejn´ y. Sestrojen´ım magického ˇctverce doc´ıl´ıme toho, ˇze bude m´ıt 3 parity s 3 prvky, kde kaˇzdá partita dává stejn´ y souˇcet.

Obrázek 20: Magick´ y ˇctverec 3 × 3 s magickou konstantou k = 15 Zb´ yvaj´ıc´ı 4 prvky do kaˇzdé partity dopln´ıme tak, ˇze pod magick´ y ˇctverec zaˇcneme psát postupnˇe dalˇs´ı vrcholy od nejmenˇs´ıho po nejvˇetˇs´ı. Zaˇcneme zleva doprava a na novém ˇrádku smˇer obrát´ıme, t´ım vytvoˇr´ıme 1-VMV graf na 21 vrcholech. Nav´ıc pokud jsem takto postupovali, tak vrcholy od 4 aˇz do 7 ˇrádku, které jsou ve stejném sloupci dávaj´ı stejn´ y souˇcet.


28

Obrázek 21: Rozloˇzen´ı vrchol˚ u pro 1-VMV tripartitn´ı graf na 21 vrcholech.

Kdyˇz máme takto rozm´ıstˇené vrcholy, vyhledáme v kaˇzdé paritˇe, tak jako pˇredeˇslém pˇr´ıpadˇe, dvojice splˇ nuj´ıc´ı f (xi )+f (yi ) = n+1. Protoˇze se jedná a tripartitn´ı graf, tak dvojice v jedné partitˇe bude spojená s kaˇzdou dvojic´ı ve zb´ yvaj´ıc´ıch dvou partitách. M˚ uˇzeme také jednotlivé dvojice, které potˇrebujeme m´ıt v podgrafu A, z´ıskat prohozen´ım vhodn´ ych dvojic vrchol˚ u v partitách, a to vyuˇzit´ım toho, ˇze od 4 ˇrádku maj´ı dva vrcholy pod sebou v kaˇzdém ˇrádku vˇzdy stejn´ y souˇcet. Tedy kdyˇz prohod´ıme vrcholy v jednotliv´ ych paritách pod sebou za vrcholy na stejné pozici v jiné paritˇe, nezmˇen´ı se celkov´ y souˇcet partity. Prohazován´ım jednotliv´ ych vrchol˚ u dostaneme potˇrebné dvojice, které se sv´ ym uskupen´ım tvoˇr´ı podgraf A. Takové to v´ ysledné rozloˇzen´ı vrchol˚ u je na Obrázku 21, kde kaˇzdá partita je reprezentována jedn´ım sloupcem.

´ ER ˇ 3 ZAV

3

29

Z´ avˇ er

V této bakaláˇrské práci jsme se zab´ yvali problematikou 1-VMV ohodnocen´ı graf˚ u a jeho aplikaci na sportovn´ı turnaje. Jsou zde zahrnuty základn´ı pojmy a dosud známé v´ ysledky, které jsme rozˇs´ıˇrili o konstruktivn´ı d˚ ukaz existence 14-pravideln´ ych graf˚ u, pro liché poˇcty vrchol˚ u. Zjistili jsme, ˇze zat´ım co pro 14-pravidelné grafy na sudém poˇctu vrchol˚ u existuje magické ohodnocen´ı jiˇz na 16 vrcholech, tak pro liché poˇcty vrchol˚ u je hranic´ı existence 19 vrchol˚ u. Nejmenˇs´ı poˇcet vrchol˚ u, kdy 14-pravideln´ y graf existuje, je 15, tento graf je grafem kompletn´ım a nen´ı 1-VMV. Jak bylo dokázáno Petrem Kováˇrem a Adamem Silberem, v ˇclánku Distance magic graphs of high regularity (v této práci Vˇeta 2.1) ani na 17 vrcholech neexistuje 14-pravideln´ y 1-VMV graf. Dalˇs´ım lich´ ym poˇctem vrchol˚ u v poˇrad´ı je tedy 19. Podaˇrilo se naj´ıt 19.pravideln´ y 1-VMV graf. Dále jsem ukázali, ˇze pokud v takovém to grafu existuje speciáln´ı podgraf A, bude tento graf 1-VMV. Následnˇe jsem dokázali, ˇze takov´ y to podgraf je moˇzné nalézt ve vˇsech grafech, kde poˇcet vrchol˚ u je 19 + 2t, kde t je celé kladné ˇc´ıslo. K tomuto d˚ ukazu jsme zvolili d˚ ukazovou techniku matematickou indukc´ı. Vycházeli jsme ze dvou startovn´ıch graf˚ u. Ze 14-pravidelného grafu na 19 vrcholech, kde jsem dok´ azali, ˇze 1-VMV ohodnocen´ı existuje pro vˇsechny grafy na 19 + 4t vrchole a z grafu na 21 vrcholech, kde jsme stejn´ y zp˚ usobem ukázali, ˇze magické ohodnocen´ı existuje ve vˇsech grafech na 21 + 4t vrcholech. T´ım jsme dokázali existenci 14-pravideln´ ych 1-VMV graf˚ u pro vˇsechny liché poˇcty vrchol˚ u n ≥ 19. Tento d˚ ukaz rozˇsiˇruje dosud známé v´ ysledky pravideln´ ych magicky ohodnocen´ ych graf˚ u na lichém poˇctu vrchol˚ u. P˚ uvodn´ı v´ ysledky 1-VMV 2-, 4-, 6-, 8-, 10-, 12-pravideln´ ych graf˚ u tato práce rozˇsiˇruje o grafy 14-pravidelné. Navázali jsem na sérii obdobn´ ych ˇclánk˚ u, z nichˇz nˇekteré jsou zaslané a nˇekteré jiˇz pˇrijaté, nebo publikované. V podobném duchu ˇcekáme, ˇze je moˇzno ˇreˇsit i 16- nebo 2t-pravidelné grafy pro pˇrirozené ˇc´ıslo t, u kter´ ych vˇsak bude konstrukce nároˇcnˇejˇs´ı. Bude zapotˇreb´ı provést vˇetˇs´ı indukˇcn´ı krok, tedy pˇridat v´ıce vrchol˚ u a bude mnoho velk´ ych ”startovn´ıch” graf˚ u.

REFERENCE

4

30

Literatura

Reference [1] S. Arumugan, D. Fronˇcek, N. Kamatchi, Distance Magic Graphs–A Survey, (accepted). [2] D. Fronˇcek, P. Kováˇr, and T. Kováˇrová, Fair incomplete tournaments, Bulletin of the ICA, 48, (2006), 31–33. [3] P. Kováˇr, T. Kováˇrová and D. Fronˇcek, A not on 4-regular distance magic graphs, (submitted). [4] P. Kováˇr, A. Silber, P Kabel´ıková and M. Kravˇcenko, On regular distance magic graphs of odd order, (submitted). [5] P. Kováˇr, A. Silber, Distance magic graphs of high regularity, (submitted).

Aplikace 1-VMV ohodnocení grafů. Applications of 1-VMV labelings graphs

Recommend Documents