O strukturze grafów Kroneckera
| dc.contributor.advisor | Łuczak, Tomasz. Promotor | |
| dc.contributor.author | Banaszak, Justyna | |
| dc.date.accessioned | 2019-09-13T07:28:59Z | |
| dc.date.available | 2019-09-13T07:28:59Z | |
| dc.date.issued | 2019 | |
| dc.description | Wydział Matematyki i Informatyki | pl |
| dc.description.abstract | Przedmiotem pracy jest asymptotyczna struktura grafów Kroneckera. Grafem Kroneckera nazywamy graf, w którym zbiór wierzchołków stanowią wszystkie ciągi binarne o długości n, w którym prawdopodobieństwo, że dwa wierzchołki są połączone krawędzią zależy od liczby pozycji, na których mają one wspólne jedynki, wspólne zera oraz różne wartości. W pracy badam zachowanie grafów Kroneckera przy n dążącym do nieskończoności. W pierwszej części pracy rozważam własności grafów Kroneckera takie jak istnienie skojarzenia doskonałego i δ-krawędziowa spójność, gdzie δ jest minimalnym stopniem grafu. Pokazuję między innymi, że próg dla istnienia skojarzenia doskonałego jest taki sam, jak próg spójności tego grafu. Prezentowane tu wyniki częściowo opierają się na mojej pracy opublikowanej w Electronic Journal of Combinatorics. W ostatnim rozdziale pracy dowodzę, że za progiem spójności grafy Kroneckera mają stałą średnicę z prawdopodobieńśtwem dążącym do 1, gdy n dąży do nieskończoności. Wynik ten pochodzi z mojej wspólnej pracy z Tomaszem Łuczakiem, opublikowanej w Discrete Mathematics. | pl |
| dc.description.abstract | In the thesis we study the asymptotic structure of Kronecker graphs. Kronecker graph is a graph, where vertex set is the set of all binary vectors of length n, where the probability that two vertices are connected depends on the number of positions in their labels on which they have common zeros, common ones, and different values. In the thesis we study the behaviour of these graphs as n tends to infinity. In the first part of the work we examine several properties of Kronecker graphs such as k-connectivity and the existence of a perfect matching. In particular, we show that the thresholds for connectivity and for the existence of perfect matching basically coincide. These results are partially based on my paper published in Electronic Journal of Combinatorics. In the last chapter of the thesis we study the diameter of Kronecker graphs and prove that just above the connectivity threshold, the diameter of Kronecker graphs, with probability tending to 1 as n tends to infinity, is bounded from above by a constant. The article containing this result, by Tomasz Łuczak and myself, was published in Discrete Mathematics. | pl |
| dc.identifier.uri | http://hdl.handle.net/10593/24948 | |
| dc.language.iso | eng | pl |
| dc.rights | info:eu-repo/semantics/openAccess | pl |
| dc.subject | graphs | pl |
| dc.subject | grafy | pl |
| dc.subject | combinatorics | pl |
| dc.subject | kombinatoryka | pl |
| dc.subject | random structures | pl |
| dc.subject | struktury losowe | pl |
| dc.subject | Kronecker graphs | pl |
| dc.subject | grafy Kroneckera | pl |
| dc.title | O strukturze grafów Kroneckera | pl |
| dc.title.alternative | On the structure of Kronecker graphs | pl |
| dc.type | Dysertacja | pl |