Temat: graphs theory - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: Implementacja algorytmów analizy grafów
Implementation of graphs analysis algorithms
Autorzy:: Konieczny, Łukasz
Opis:: Specification and implementation of graph2vec algorithm, which makes possible embedding of graphs as vectors of desired dimensions number.
Opis oraz implementacja algorytmu graph2vec, który pozwala osadzać grafy jako wektory o zadanej liczbie wymiarów.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 2.

Tytuł:: Perfect Graph Recognition and Coloring.
Rozpoznawanie i kolorowanie grafów doskonałych
Autorzy:: Siwiec, Adrian
Opis:: Badania nad grafami doskonałymi trwają nieprzerwanie od ich wprowadzenia w 1961 roku. Dopiero w roku 2001 została udowodniona słynna hipoteza o grafach doskonałych, a w roku 2005 opublikowany został pierwszy wielomianowy algorytm rozpoznający grafy doskonałe. Od 1988 roku znany jest algorytm kolorujący grafy doskonałe, ale korzysta on z metody elipsoidalnej, która jest uznawana za skomplikowaną i niepraktyczną. W 2018 roku opublikowany został kombinatoryczny algorytm kolorujący grafy doskonałe niezawierające kwadratów.Rozdział 1 zawiera podstawowe definicje teorii grafów. Rozdział 2 zawiera wprowadzenie do grafów doskonałych, grafów Berge'a, krótki opis twierdzenia o grafach doskonałych oraz algorytm rozpoznawania grafów doskonałych. Rozdział 3 stanowi opis metody elipsoidalnej kolorowania grafów doskonałych. W rozdziale 4 omawiana jest implementacja wspomnianych algorytmów, wraz z informacjami o wprowadzonych optymalizacjach i zrównolegleniu. Appendix A jest krótkim omówieniem algorytmu kolorowania grafów doskonałych bez kwadratów.
Perfect graphs are a subject of intense study since their introduction in 1961. Only in 2001 the famous perfect graph conjecture was proven to be true and in 2005 a polynomial method of determining if a graph is perfect was found. Since 1988 an algorithm is known for coloring perfect graphs, but it uses an ellipsoid method which is said to be complicated and impractical. As recently as in 2018 a polynomial algorithm that uses a combinatorial approach for coloring perfect graphs without squares was published.We begin with basic definitions in Chapter 1. In Chapter 2 we introduce perfect graphs and Berge graphs, give an overview of the strong perfect graph theorem and talk about an algorithm for polynomial perfect graph recognition. Chapter 3 is a study of the ellipsoid method of coloring perfect graphs. In Chapter 4 we present our implementation of algorithms from Chapters 2 and 3, along with notes on optimization and parallelisation. Appendix A is a overview of the recent algorithm for coloring square-free perfect graphs.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 3.

Tytuł:: Information system for assessing the professional activities complexity – theoretical and practical aspects of implementation
System informacyjny do oceny złożoności działalności zawodowej – teoretyczne i praktyczne aspekty wdrożenia
Autorzy:: Zaritskyi, O.
Tematy:: information system
profession activity estimation
job analysis
graphs theory
fuzzy set
system informacyjny
szacowanie działalności zawodowej
analiza pracy
teoria grafów
zbiór rozmyty; Pokaż więcej
Wydawca:: Politechnika Lubelska. Wydawnictwo Politechniki Lubelskiej
Powiązania:: https://bibliotekanauki.pl/articles/408529.pdf Link otwiera się w nowym oknie
Opis:: The article deals with theoretical and practical issues of the implementation of professional activity analytical evaluation information technologies. The focus is on new methods for presenting and processing data in the activity description and evaluation tasks.
Artykuł dotyczy teoretycznych i praktycznych zagadnień wdrażania technologii informatycznych do analitycznej oceny aktywności zawodowej. Nacisk kładziony jest na nowe metody prezentacji i przetwarzania danych w opisie i ocenie zadań.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Surgery of Graphs: M-Function and Spectral Gap
Autorzy:: Kurasov, P.
Tematy:: quantum graphs
spectral theory; Pokaż więcej
Wydawca:: Polska Akademia Nauk. Instytut Fizyki PAN
Powiązania:: https://bibliotekanauki.pl/articles/1030010.pdf Link otwiera się w nowym oknie
Opis:: We discuss behaviour of the spectral gap for quantum graphs when two metric graphs are glued together. It appears that precise answer to this question can be given using a natural generalisation of the Titchmarsh-Weyl M-functions.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: Heavy Subgraphs, Stability and Hamiltonicity
Autorzy:: Li, Binlong
Ning, Bo
Tematy:: heavy subgraphs
hamiltonian graphs
closure theory; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31341693.pdf Link otwiera się w nowym oknie
Opis:: Let G be a graph. Adopting the terminology of Broersma et al. and Čada, respectively, we say that G is 2-heavy if every induced claw (K1,3) of G contains two end-vertices each one has degree at least |V (G)|/2; and G is o-heavy if every induced claw of G contains two end-vertices with degree sum at least |V (G)| in G. In this paper, we introduce a new concept, and say that G is S-c-heavy if for a given graph S and every induced subgraph G′ of G isomorphic to S and every maximal clique C of G′, every non-trivial component of G′ − C contains a vertex of degree at least |V (G)|/2 in G. Our original motivation is a theorem of Hu from 1999 that can be stated, in terms of this concept, as every 2-connected 2-heavy and N-c-heavy graph is hamiltonian, where N is the graph obtained from a triangle by adding three disjoint pendant edges. In this paper, we will characterize all connected graphs S such that every 2-connected o-heavy and S-c-heavy graph is hamiltonian. Our work results in a different proof of a stronger version of Hu’s theorem. Furthermore, our main result improves or extends several previous results.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: Geometric properties of quantum graphs and vertex scattering matrices
Autorzy:: Kurasov, P.
Nowaczyk, M.
Tematy:: scattering theory
quantum graphs
matching (boundary) conditions; Pokaż więcej
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Powiązania:: https://bibliotekanauki.pl/articles/255512.pdf Link otwiera się w nowym oknie
Opis:: Differential operators on metric graphs are investigated. It is proven that vertex matching (boundary) conditions can be successfully parameterized by the vertex scattering matrix. Two new families of matching conditions are investigated: hyperplanar Neumann and hyperplanar Dirichlet conditions. Using trace formula it is shown that the spectrum of the Laplace operator determines certain geometric properties of the underlying graph.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 7.

Tytuł:: Algorytmy kompresji grafów losowych.
Random graph compression algorithms.
Autorzy:: Palenica, Paweł
Opis:: W tej pracy pokazujemy teoretyczne wyniki dla entropii strukturalnej grafów losowych Erdősa–Rényiego oraz grafów losowych preferential-attachment wraz z implementacją algorytmów kompresji osiągających wynik zbliżony do optymalnego. Dodatkowo, przedstawiamy wybrane własności dla wspomianych modeli grafów oraz dodatkowo modelu duplication-divergence. Przedstawiamy wyniki eksperymentów potwierdzające teoretyczne wyniki na grafach syntetycznych oraz obiecujące wyniki w porównaniu do klasycznych algorytmów kompresji danych.
In this thesis we present theoretical results for structural entropy of Erdős–Rényi model ran-dom graphs and preferential-attachment model random graphs together with implementationsof corresponding asymptotically optimal random graph compression algorithms. Addition-ally, we investigate some properties of two aforementioned models along with duplication-divergence model. Lastly, we present experimentation results confirming the theoreticalbounds on model graphs and delivering promising results over conventional sequential datacompression algorithms.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 8.

Tytuł:: Remarks on 15-vertex (3,3)-ramsey graphs not containing K₅
Autorzy:: Urbański, Sebastian
Tematy:: Folkman numbers
Kₙ-free graphs
extremal graph theory
generalized Ramsey theory; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/972005.pdf Link otwiera się w nowym oknie
Opis:: The paper gives an account of previous and recent attempts to determine the order of a smallest graph not containing K₅ and such that every 2-coloring of its edges results in a monochromatic triangle. A new 14-vertex K₄-free graph with the same Ramsey property in the vertex coloring case is found. This yields a new construction of one of the only two known 15-vertex (3,3)-Ramsey graphs not containing K₅.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 9.

Tytuł:: Algorytmy heurystyczne dla problemu minimalizacji sumy kosztów zadań opóźnionych
Heuristics algorithms for the single machine total tardiness problem.
Autorzy:: Wodecki, Mieczysław
Tematy:: Scheduling theory, deterministic
Programming involving graphs or networks; Pokaż więcej
Wydawca:: Polskie Towarzystwo Matematyczne
Powiązania:: https://bibliotekanauki.pl/articles/748154.pdf Link otwiera się w nowym oknie
Opis:: W pracy rozpatrujemy problem minimalizacji sumy kosztów opóźnień zadań wykonywanych na jednej maszynie. Należy on do klasy problemów silnie NP-zupełnych. Zamieszczone w literaturze wyniki obliczeniowe wskazują, że w rozsądnym czasie można uzyskać jego rozwiązanie optymalne jedynie dla przykładów o niewielkich rozmiarach. Z tego właśnie powodu proponujemy szybki algorytm heurystyczny oraz algorytm typu „popraw” oparty na metodzie tabu search.
This paper presents approximations algorithms for the single machine total weighted tardiness problems. The algorithms is based on a tabu search technique with a specific neighborhood definition. Results of testing the algorithms on large number of randomly generated examples are also given and analysed.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 10.

Tytuł:: Badanie grafów Hamiltona z językiem Python
Study of Hamiltonian graphs with Python
Autorzy:: Szestało, Piotr
Opis:: W pracy przedstawiono implementację w języku Python wybranych algorytmówzwiązanych z grafami Hamiltona. Wykorzystano interfejs dla grafówoparty na dwóch podstawowych klasach Edge i Graph. Klasa Edge reprezentujekrawędzie skierowane z wagą. Klasa Graph reprezentuje grafy proste ważone,skierowane i nieskierowane.W pracy zaimplementowano dwa algorytmy przeszukiwania grafów: algorytmprzeszukiwania wszerz (BFS), oraz algorytm przeszukiwania w głąb(DFS). Zaimplementowano algorytm rekurencyjny na bazie DFS, który znajdujewszystkie ścieżki i cykle Hamiltona w grafach skierowanych i nieskierowanych.Dla grafów nieskierowanych ważonych zbadano problem komiwojażera.Zaimplementowano algorytm dokładny na bazie DFS, oraz szereg algorytmówprzybliżonych: algorytm najbliższych sąsiadów, algorytm najbliższychsąsiadów z powtórzeniami, algorytm sortowania krawędzi. Dla metrycznegoproblemu komiwojażera przedstawiono algorytm 2-aproksymacyjny, bazującyna minimalnym drzewie rozpinającym. Omówiono również trzy metaheurystyki,które są stosowane w kontekście problemu komiwojażera.Dla grafów skierowanych acyklicznych zaimplementowany został algorytmsortowania topologicznego, na bazie DFS. Stworzono również funkcjedo badania tranzytywności turnieju (grafu pełnego skierowanego), oraz doznajdywania ścieżek Hamiltona w turniejach.Ważną częścią pracy są zestawienia twierdzeń matematycznych, któredotyczą cykli Hamiltona, z wieloma przykładami edukacyjnymi. Dla algorytmówrozwiązujących problem komiwojażera wykonane zostały testy wydajnościowe,oraz testy dokładności.
Python implementation of selected graph algorithms connected with Hamiltoniangraphs are presented. Graphs interface based on two clases is used.The Edge class represents directed weighted edges. The Graph class is forsimple weighted graphs, directed and undirected.In this work, two graphs traversing algorithms are implemented: breadth-firstsearch (BFS) and depth-first search (DFS). The recursive algorithm based onDFS is implemented, for finding all Hamiltonian paths and cycles in directedor undirected graphs.In the case of weighted undirected graphs, the travelling salesman problemis considered. The exact (brute force) algorithm based on DFS is given.Several heuristic algorithms are presented: the nearest neighbor algorithm,the repeated nearest neighbor algorithm, and the sorted edge algorithm. Forthe metric travelling salesman problem, 2-approximation algorithm is shown,which is based on the minimum spanning tree.In the case of directed graphs, the topological sorting algorithm is implemented.Two additional functions are given: for transitivity testing oftournaments and for finding a Hamiltonian path in tournaments.The important part of the work is a range of theorems on Hamiltoniancycles, with many educational examples. The algorithms solving the travellingsalesman problem were tested for the complexity and the accuracy.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Informacja

Wyszukujesz frazę "graphs theory" wg kryterium: Temat