Náhodná nakreslení grafů: generování a analýza

Abstract

V této práci se budeme věnovat náhodným nakreslením grafům, ty budeme generovat pomocí rotačních schémat a kreslících systému, což jsou ze své podstaty kombinatorické objekty snadno udržitelné v paměti kódu. Tato náhodná nakreslení si budeme genero- vat ve velkém množství pro různé třídy grafů, nejčastěji to ale budou grafy úplné. Ve výsledcích experimentů nás pak bude zajímat distribuce singulárních hran, která by za příhodných výsledků mohla pomoci ve vyřešení hypotézy "Cycle Double Cover", ale na- konec zjistíme, že výsledky příznivé nejsou. Singulárních hran je i v nejlepších, velmi málo pravděpodobných, případech příliš, pročež způsob, který měl pomoci vyřešit onu hypotézu, pohořel. Letmo se věnujeme i počtu dvojcyklů v grafu, který souvisí s mí- rou nakreslení zvanou "face-width", souvislost ale do detailů nepopisujeme. Pro počet dvojcyklů dokážeme teoretický horní odhad, který následně experimentálně ověříme.

On these pages we will focus on the study of random graph embeddings which we generate using rotation systems and embedding schemes - both of which are by nature combinatorical objects easy to represent computationally. These random embeddings will be generated in large numbers for various graph classes, though we will focus primarily on complete graphs. In our results we examine the distribution of singular edges, which - if it is convinient enough - could potentially aid us in solving the Cycle Double Cover hypothesis. Unfortunately we will discover, that the results aren't favorable. The number of singular edges is far too high, even in the best - albeit little probable - cases, so our intended approach to support the resolution of the hypothesis was ultimately unsuccessful. Additionally, we briefly consider the number of two-cycles in a graph, that has a direct connection to a measure of graph embedding called face-width, although this relationship is not discussed in depth. We will establish an upper bound for the number of two-cycles and support this with emperical data.