Název: | \vyraz{L(i,j,k)} - ohodnocení grafů |
Další názvy: | L(i,j,k)-labelings of graphs |
Autoři: | Kopřiva, Martin |
Vedoucí práce/školitel: | Holub Přemysl, Doc. RNDr. Ph.D. |
Oponent: | Čada Roman, Doc. Ing. Ph.D. |
Datum vydání: | 2019 |
Nakladatel: | Západočeská univerzita v Plzni |
Typ dokumentu: | bakalářská práce |
URI: | http://hdl.handle.net/11025/46888 |
Klíčová slova: | graf;l(i;j;k)-ohodnocení;rozpětí;zobecněný petersenův graf |
Klíčová slova v dalším jazyce: | graph;l(i;j;k)-labelling;spread;generalized petersen graph |
Abstrakt: | Tato práce se věnuje \vyraz{L(i,j,k)}-ohodnocení grafů, se speciálním zaměřením na \vyraz{L(3,2,1)}-ohodnocení, a hledá minimální rozpětí, případně horní či dolní odhady tohoto rozpětí, kterým lze daný graf ohodnotit. Pro \vyraz{i, j, k}, \vyraz{L(i,j,k)}-ohodnocením grafu \vyraz{G} rozumíme přiřazení celých nezáporných čísel vrcholům grafu \vyraz{G} tak, že sousední vrcholy musejí být ohodnoceny hodnotami s rozdílem aspoň \vyraz{i}, vrcholy ve vzdálenosti \vyraz{2} musejí být ohodnoceny hodnotami s rozdílem aspoň \vyraz{j} a vrcholy ve vzdálenosti \vyraz{3} musejí být ohodnoceny hodnotami s rozdílem aspoň \vyraz{k}. V první části práce jsou shrnuty již známé výsledky z oblasti základních tříd grafů. Vlastní výzkum se zaměřuje na \vyraz{L(i,j,k)}-ohodnocení zobecněných Petersenových grafů. |
Abstrakt v dalším jazyce: | This bachelor thesis deals with \vyraz{L(i,j,k)}-labelling of graphs with special focus on \vyraz{L(3,2,1)}-labelling, and searches for minimal spread or upper and lower bounds on this spread by which the graph can be evaluated. For integers \vyraz{i, j, k}, \vyraz{L(i,j,k)}-labelling of a graph \vyraz{G} is a mapping of non-negative integers to vertices of \vyraz{G} such that the difference between the values of neighbouring vertices has to be at least \vyraz{i}, the difference between the values of vertices at distance \vyraz{2} has to be at least \vyraz{j}, and the difference between the values of vertices at distance \vyraz{3} has to be at least \vyraz{k}. Already known results for basic families of graphs are summarized in the first part of the thesis. Our own research concentrates on \vyraz{L(i,j,k)}-labelling of generalized Petersen graphs. |
Práva: | Plný text práce je přístupný bez omezení |
Vyskytuje se v kolekcích: | Bakalářské práce / Bachelor´s works (KMA) |
Soubory připojené k záznamu:
Soubor | Popis | Velikost | Formát | |
---|---|---|---|---|
Bakalarska prace, Martin Kopriva.pdf | Plný text práce | 1,05 MB | Adobe PDF | Zobrazit/otevřít |
PV_Kopriva.pdf | Posudek vedoucího práce | 1,12 MB | Adobe PDF | Zobrazit/otevřít |
PO_Kopriva.pdf | Posudek oponenta práce | 913,81 kB | Adobe PDF | Zobrazit/otevřít |
Kopriva_PO.pdf | Průběh obhajoby práce | 14,87 kB | Adobe PDF | Zobrazit/otevřít |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/46888
Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.