Metody Algorytmiczne w Badaniach Siły Nieregularności Grafów
| dc.contributor.advisor | Karoński, Michał. Promotor | |
| dc.contributor.author | Kalkowski, Maciej | |
| dc.date.accessioned | 2010-06-11T12:13:03Z | |
| dc.date.available | 2010-06-11T12:13:03Z | |
| dc.date.issued | 2010-06-11T12:13:03Z | |
| dc.description | Wydział Matematyki i Informatyki: Zakład Matematyki Dyskretnej | pl_PL |
| dc.description.abstract | Celem rozprawy jest przedstawienie nowych metod rozwiązywania problemów globalnej i lokalnej siły nieregularności grafów. Powyższe dwa zagadnienia są rozpatrzone zarówno dla grafów ważonych, jak i totalnie ważonych. Wszystkie przedstawione metody i dowody mają charakter algorytmów wyznaczających wartości funkcji ważących. Rozdział drugi składa się z dwóch części i dotyczy lokalnego rozróżniania wierzchołków. W pierwszej, zagadnienie omówione jest dla totalnego ważenia. Wprowadzone są dwa twierdzenia, dowodzące, że istnieją lokalnie nieregularne 5-totalne-ważenie oraz 3-totalne-ważenie. W drugiej części rozdziału rozważony jest problem rozróżniania wierzchołków dla ważenia krawędzi nawiązujący do hipotezy 1-2-3. Wprowadzone są trzy nowe metody rozwiązania problemu, które wykazują, że możliwe są konstrukcje lokalnie nieregularnych 10-ważenia, 6-ważenia i 5-ważenia grafu. Rozdział trzeci dotyczy globalnego rozróżniania wierzchołków i również składa się z dwóch części. W pierwszej, zagadnienie rozpatrzone jest dla ważenia krawędzi grafu. Opisana jest metoda konstrukcji globalnie nieregularnego 6 ⌈n/δ⌉ -ważenia grafu. W drugiej części rozdziału omówione jest globalne rozróżnianie wierzchołków dla totalnego ważenia grafów. Wykazana jest konstrukcja globalnie nieregularnego (3⌈n/δ ⌉+1)-totalnego-ważenia. W ostatnim rozdziale przedstawione są pokrewne problemy rozróżniania wierzchołków. | pl_PL |
| dc.description.abstract | The thesis deals with new methods for solving the local and global irregularity strength problems. Both issues are discussed considering weightings and total weightings of a graph. All presented methods and proofs have an algorithmic construction, which assigns weights to a graph. The second chapter covers the problem of distinguishing connected vertices. First part considers total weightings. Two new theorems are presented, proving that there exist locally irregular 5-total-weighting and 3-total-weighting. Second part investigates weightings of a graph. Three new results are discussed, showing that there exist 10-weighting, 6-weihgting and 5-weighting, all locally irregular. The third chapter covers the problem of distinguishing all vertices of a graph. First part considers weightings of a graph. A new result is presented, which shows that there exist vertex distinguishing 6 ⌈n/δ⌉-weighting. Second part investigates total-weightings of a graph. A new construction of vertex distinguishing (3⌈n/δ ⌉+1)-total-weighting is proved. The last chapter considers other related graph coloring problems. | pl_PL |
| dc.identifier.uri | http://hdl.handle.net/10593/445 | |
| dc.language.iso | pl | pl_PL |
| dc.subject | grafy | pl_PL |
| dc.subject | graphs | pl_PL |
| dc.subject | algorytmy | pl_PL |
| dc.subject | algorithms | pl_PL |
| dc.subject | siła nieregularności | pl_PL |
| dc.subject | irregularity strength | pl_PL |
| dc.subject | kolorowanie | pl_PL |
| dc.subject | coloring | pl_PL |
| dc.title | Metody Algorytmiczne w Badaniach Siły Nieregularności Grafów | pl_PL |
| dc.title.alternative | Algorithmic Methods for the Irregularity Strength of Graphs | pl_PL |
| dc.type | Dysertacja | pl_PL |