Zbiór minimalnych przekrojów z wprowadzonymi na nim operacjami binarnymi jest kratą dystrybutywną. Zestaw minimalnych przekrojów w kracie dystrybutywnej minimalnych przekrojów można opisać analitycznie na podstawie podzbioru nierozkładalnych minimalnych przekrojów. Proponowane jest kodowanie kraty dystrybutywnej w celu efektywnej realizacji operacji na przekrojach.
EN
The set of minimal cuts with binary operations introduced on it is a distributive lattice. A set of minimal cuts in a distributive minimal cut lattice can be described analytically from a subset of indecomposable minimal cuts. We propose a coding of a distributive lattice for the efficient implementation of operations on cuts.
In 2020, Behr [1] introduced the problem of edge coloring of signed graphs and proved that every signed graph (G, σ) can be colored using ∆(G) or ∆(G) +1colors, where ∆(G) denotes the maximum degree of G. Three years later, Janczewski et al. [2] introduced a notion of signed class 1, such that a graph G is of signed class 1 if and only if everysigned graph (G, σ) can be colored using ∆(G) colors. It is a well-known fact [3] that almost all graphs are of class 1. In this paper, we conjecture that a similar fact is true for signed class 1, that almost all graphs are of signed class 1. To support the hypothesis we implemented an application that colored all the signed graphs with at most 8 vertices. We describe an algorithm behind the application and discuss the results of conducted experiments.
W nowoczesnym przemyśle skomplikowane systemy zabezpieczeń chronią przed powstaniem zdarzeń niebezpiecznych, np. przekroczeniem parametrów dopuszczalnych urządzeń ciśnieniowych, uwolnieniem substancji niebezpiecznej lub wytworzeniem atmosfery wybuchowej.
Celem tego artykułu jest przedstawienie, porównanie oraz implementacja algorytmów odnajdywania ścieżki do zastosowania w grach przeglądarkowych z wykorzystaniem ogólnodostępnych, darmowych technologii internetowych. Pokazano również możliwość wykorzystania najlepszego algorytmu w grze przeglądarkowej
EN
The goal of this article is to present, compare and implement path finding algorithms for use in browser games, using public, free internet technologies. The possibility of using the best algorithm in a browser game is also shown.
5
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In this paper we solve a variant of the multi-hop influence maximization problem in social networks by means of a hybrid algorithm that combines a biased random key genetic algorithm with a graph neural network. Hereby, the predictions of the graph neural network are used with the biased random key genetic algorithm for a more accurate translation of individuals into valid solutions to the tackled problem. The obtained results show that the hybrid algorithm is able to outperform both the biased random key genetic algorithm and the graph neural network when used as standalone techniques. In other words, we were able to show that an integration of both techniques leads to a better algorithm.
An original method for finding the optimal band of a given width based on the algorithms for the maximum flow / minimum cut construction is proposed. An example of the presented algorithm work is given.
PL
Zaproponowano oryginalną metodę znajdowania optymalnego pasa o danej szerokości w oparciu o algorytmy konstruowania maksymalnego przepływu / minimalnego przekroju. Podano przykład działania prezentowanego algorytmu.
7
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Explicit constructions in Extremal Graph Theory give appropriate lower bounds for Turan type problems. In the case of prohibited cycles, the explicit constructions can be used for various problems of Information Security. We observe recent applications of algebraic constructions of regular graphs of large girth and graphs with large cycle indicator to Coding Theory and Cryptography. In particular, we present a new multivariate platforms of postquantum Non-commutative Cryptography defined in graph theoretical terms.
8
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Correlation clustering is a NP-hard problem, and for large signed graphs finding even just a good approximation of the optimal solution is a hard task. In this article we examine the effect of ranking of the nodes and process them in order of ranks. We present that based on the rate of positive edges in the graph we should use different optimization methods. We show that all the building blocks of our methods are needed under certain circumstances.
9
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The work compares the accuracy of calculations of the reliability parameters of the sewerage network using the Decomposition and Equivalent Replacement (MDE) method, proposed by Yu. A. Yermolin and M.I. Alekseev [3], definitely simpler and less onerous in relation to the graph method. Comparing the results of calculations with both methods, applied to a simple network, one can come to the conclusion that the MDE calculations in simple cases give satisfactory accuracy. However, it would be necessary to check whether, as the complexity increases, this accuracy is still satisfactory.
PL
W pracy porównano dokładność obliczeń parametrów niezawodnościowych sieci kanalizacyjnej metodą dekompozycji i ekwiwalentnej zamiany (MDE), zaproponowaną przez Ju. A. Jermolina i M.I. Alieksjejewa [3], zdecydowanie prostszą i mniej uciążliwą w stosunku do metody grafów. Porównując wyniki obliczeń obiema metodami, zastosowane do prostej sieci, można dojść do wniosku, że obliczenia metodą MDE w prostych przypadkach dają zadowalającą dokładność. Należałoby jednak sprawdzić, czy w miarę wzrostu złożoności, dokładność ta jest nadal zadowalająca.
Zbiór danych katastralnych stanowi bazowe dane przestrzenne, na których opierają się procesy związane z zarządzaniem gruntami. Jest on także istotnym rejestrem, na podstawie którego prowadzi się analizy przestrzenne w procesach decyzyjnych. W tych działaniach ważny jest zapis struktur katastralnych w modelu matematyczno-topologicznym. Podjęto się takich prac na podstawie istniejących zbiorów danych, głównie geometrycznych i wybranych zbiorów atrybutów. Przy realizacji tego zadania wykreował się cel niniejszej publikacji związany z oceną topologiczną struktur katastralnych wybranego obiektu badawczego. Badania wiązały się z zapisem relacji sąsiedztwa wybranych obiektów katastralnych w modelu grafowym. Grafowy model struktur katastralnych pozwala na ocenę wizualną rozdrobnienia działek. Model topologiczny tych struktur jest niejednorodny i utrudnia jednoznaczną ocenę analityczną zbiorów. Wyniki wykazały różnorodność w strukturze działek ewidencyjnych pasów drogowych. Model stworzono w grafowej bazie danych. Wyniki pozwalają na znalezienie miejsc o szczególnym rozdrobnieniu działek pasa drogowego. Są to miejsca, które powstały w procesach tworzenia pasów drogowych lub ich modernizacji – poszerzania. Wnioski z wykonanych badań wskazują na konieczność scaleń działek, których właścicielami są gminy, powiaty, województwa czy Skarb Państwa (Dyrekcja Dróg Krajowych i Autostrad). Analiza zbiorów katastralnych w innych regionach kraju, w oparciu o dane wizualizowane w Geopotralu, potwierdza istnienie nieuzasadnionego rozdrobienia działek na terenach nowo wybudowanych ciągów komunikacyjnych. Istniejąca sytuacja zmusza do poszukiwań przyczyn zaistnienia takiego rozdrobienia i szukania rozwiązań w celu ich uporządkowania. Wnioski końcowe wskazują na konieczność przeprowadzania scaleń w tych obszarach. Po uporządkowaniu tych struktur prostsza będzie interpretacja wyników analiz przestrzennych, opartych o bazowe zbiory katastralne, a także obraz mapy katastralnej będzie czytelniejszy.
EN
The collection of cadastral data is basic spatial data on the basis of which processes associated with land management are conducted. In these activities, it is important that the cadastral structures are in the mathematical-topological model. Such works were being done on the basis of existing geometric data sets and selected sets of attributes. The aim of the present publication was created during these works, concerning the assessment of topological structures of the selected object. The research was associated with the records of neighborhood relationships of selected cadastral objects in the graph model. The graph model of cadastral structures enables the visual assessment of parcel fragmentation. The topological model of these structures is heterogeneous; therefore, it is difficult to clearly and analytically evaluate the sets. The results showed diversity in the structure of the cadastral road parcels. The model was created in the graph database. The results enabled us to find places with a particularly high fragmentation of road parcels. These are places that have arisen in the process of creating roads or their modernization – widening. The conclusions from the research indicate the need of merging parcels owned by municipalities, counties, provinces, or the Treasury (Directorate for National Roads and Motorways). An analysis of cadastral data sets in other Polish regions based on the data visualized in Geopotrals confirms the existence of unjustified parcel fragmentation in areas of newly built roads. The existing situation forces us to search for the causes for the occurrence of such fragmentation and seek solutions to organize them. Our final conclusions indicate the need to perform mergers in these parcels. After arranging these structures, it is easier to interpret the results of a spatial analysis based on the underlying cadastral data; also, a cadastral map would be clearer.
11
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W artykule przedstawiono główne cechy systemów kanalizacyjnych, jako obiektów złożonych (o strukturze typu "drzewo") i pracujących w zmiennych, trudnych często do przewidzenia, warunkach. Do oceny wielkości zrzutu nieoczyszczonych ścieków w wyniku uszkodzenia sieci przeanalizowano zastosowanie metody równań stanów oraz metody dekompozycji i ekwiwalentowania.
EN
The article points out main features of the sewage systems, which are complex objects (possessing "tree" structure) working in changing, often hard to predict, environment. In order to estimate the quantity of untreated sewers' drop, which resulted from failures of the sewage system, author has analysed the usage of state-space model as well as decomposition and equivalent model.
A new type of graph is introduced, the grammar graph. The possibility of assigning labels to each node in such a graph extends it to the grammar net. The grammar net should be considered as a new graphical tool that helps in an analysis of whether a particular sentence belongs to a given context-sensitive grammar. Another concept, the derivation net, closely related to the grammar graph and of a similar structure, will be used to show an algorithm that is able to decide that some sentences do not belong to a language generated by a context sensitive grammar, while leaving others as a candidate members of it.
PL
W artykule wprowadzony został nowy rodzaj grafu – graf gramatyczny. Możliwość przypisywania etykiet do węzłów daje rozszerzenie do tzw. sieci gramatycznej. Sieć gramatyczną należy traktować jako nowe narzędzie graficzne w analizie przynależności zdań do danego języka kontekstowego. Inna koncepcja, sieć wywodu, ściśle związana z grafem gramatycznym i o podobnej strukturze, została wykorzystana do pokazania algorytmu, który potrafi wstępnie wyselekcjonować niektóre zdania nienależące do danego języka generowanego przez gramatykę kontekstową, pozostawiając inne jako potencjalnie w nim zawarte.
Jedną z dróg do osiągnięcia wielopłaszczyznowej spójności baz danych przestrzennych jest harmonizacja danych, metadanych i usług geoinformacyjnych. Ważnym elementem harmonizacji danych jest porównanie i weryfikacja wykorzystywanych modeli na płaszczyźnie strukturalnej – zarówno w odniesieniu do topologicznych struktur danych, jak i do wzajemnych relacji przestrzennych. Przedmiotem przeprowadzonych badań były krajowe bazy danych referencyjnych o różnym poziomie uogólnienia i przeznaczeniu (BDOT500, BDOT10k, VMapL2u, BDOO). Przyjęte zasady modelowania obiektów topograficznych są podstawowymi wyznacznikami ich struktury w sensie topologicznym. W stosowanych tam modelach obiektów topograficznych stosuje się często typowe struktury danych, w tym: graf planarny i nieplanarny, wypełnienie powierzchni (partycji), których własności mogą decydować o poprawności modelowania cech obiektów topograficznych. W badaniach przyjęto, że wyznacznikiem poprawności jest możliwie pełna charakterystyka tych obiektów, ze szczególnym uwzględnieniem wzajemnych relacji występujących pomiędzy obiektami, umożliwiająca szerokie wykorzystanie zastosowanych modeli, zgodne z przeznaczeniem baz danych referencyjnych. Posłużono się dokumentacją techniczną baz danych, ale też uwzględniono wymagania stawiane przez dokumenty standaryzacyjne i techniczne, konkretyzujące zasady realizacji zapisów dyrektywy INSPIRE. Wskazano też kilka kierunków działań, w których mogłyby toczyć się prace nad uspójnianiem topologicznym i strukturalnym poszczególnych baz danych.
EN
An important element of spatial data harmonization is comparison and verification of applied models – with reference to the topological structures and the spatial relationships between objects. The Polish reference databases of various levels of generalisation and destination have been investigated. They were: topographical databases on two levels of generalization: BDOT500 and BDOT10k, the geographical data base (BDOO) and the Vector Smart Map Level 2 in the modified structure (VMapL2u). From the topological perspective the assumed modelling rules of topographical objects are the basic indicators of their topological structure. Typical data structures, such as planar and non-planar graphs and partition structure (eg. GT-polygons) are often applied in models of topographical objects. Their features may influence the correctness of modelling the topographical phenomena. The technical documentation of considered data bases as well as the INSPIRE standardization documents were used during the project implementation. Studies have been restrained to three categories of features: the road network, the hydrographic network and the land cover, modelled in large number of feature classes. Spatial relationships between objects in these feature classes, considering types of its geometric representations, were also reviewed. Several directions have been shown for the future works on topological and structural harmonization of considered data bases.
W niniejszym artykule skupiono się na ocenie dostępności do lokalnego transportu zbiorowego w Łodzi. Do analizy wykorzystano m.in. podejście grafowe oraz dostępność kumulatywną, poszerzone o analizy sieciowe. Badanie oparto w głównej mierze na dwóch bazach danych aktualnych na I kwartał 2016 r. Jest to baza otrzymana od Zarządu Dróg i Transportu w Łodzi w postaci wykazu wszystkich przystanków, linii autobusowych i tramwajowych, czasów przejazdu pomiędzy przystankami, częstotliwości oraz rodzaju taboru obsługującego poszczególne linie komunikacyjne. Druga baza to informacje nt. liczby, rozmieszczenia oraz struktury wieku i płci mieszkańców Łodzi wg danych ewidencyjnych ludności Urzędu Miasta Łodzi. Artykuł uzupełniono o autorską recenzję Modelu w zakresie zapisów odnoszących się do jego założeń strategicznych. Badanie zamyka część wnioskowa zawierająca ponadto rekomendacje dla postulatów modelu.
EN
This article focuses on the evaluation of accessibility to the local public transport in Lodz. For the analysis was used, among others, graph approach and the availability of cumulative, extended to the analysis of the network. The research was based on the main part of the two databases up to date on the first quarter of 2016. This is the base received from the Board of Roads and Transport in Lodz, in the form of a list of all the stops, bus and tram lines, transit times between stops, frequency, and type of vehicles that support individual lines communication. Second base is information on the number, distribution and structure of the age and sex of the inhabitants of the city, according to the registration of the population of the City of Lodz. The article was accompanied by an original review model in terms of the provisions relating to its strategic objectives. The survey closes some of the conclusions and further comprising recommendations for the demands of the model.
15
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The paper focuses on the problem of managing the scope understood as managing the multiplicity of elements that constitute the application context for Java Enterprise Edition (Java EE) frameworks. The subject of constructing graph modeling languages is the basis for scope management considerations. The problem can be demonstrated while the frameworks are superposed, which is necessary for meta-modeling compliant to the Context-Driven Meta-Modeling (CDMM) approach. The realization of the approach is based on Spring and AspectJ frameworks, which offer incompatible concepts of scope management. As part of the analysis the scope management problem in Java EE frameworks application context was identified, formulated, its area was defined and the sketch of the generalized concept of scope management elaborated and implemented by the author in relation to Java EE frameworks was presented.
PL
Artykuł ten koncentruje się na problemie zarządzania zakresem rozumianym jako zarządzanie krotnościami elementów składających się na kontekst aplikacji we frameworkach Java Enterprise Edition (Java EE). Punktem odniesienia dla rozważań dotyczących zarządzania zakresem jest zagadnienie konstruowania grafowych języków modelowania. Problem ten ujawnia się przy składaniu ze sobą tych frameworków niezbędnym w meta-modelowaniu zgodnym z podejściem Context-Driven Meta-Modeling (CDMM). Jego realizacja oparta jest na frameworkach Spring i AspectJ, w których koncepcje zarządzania zakresem nie są zgodne. W ramach analizy zidentyfikowano problem zarządzania zakresem w kontekście aplikacji Java EE, sformułowano ten problem, określono jego zakres oraz zaprezentowano zarys opracowanej i zrealizowanej przez autora uogólnionej koncepcji zarządzania zakresem w odniesieniu do frameworków Java EE.
The article presents an innovative concept of applying graph databases in transport information systems. The model of a graph database has been presented together with implementation of data structures and search operations in a graph. The transformation concept of relational model to a graph data model has been developed. The schema of graph database has been proposed for public transport information system purposes. The realization methods have been illustrated by the use of search function based on the Cypher query language.
Przedstawiono problematykę doboru środków transportu do realizacji operacji transportowych: w łańcuchach dostaw - na przykładzie zadania transportowego, w produkcji - na przykładzie projektu budowy budynku magazynowego oraz w magazynowaniu. Przedstawiona metoda pozwala na wyznaczenie takiego planu realizacji operacji transportowych (wyznaczenie kolejności wykonywanych operacji transportowych optymalnymi środkami transportu), dla którego funkcja kryterium (koszt/czas) jest optymalna. Przeprowadzone badania symulacyjne wykazały, że zastosowanie tej metody umożliwia jednoznaczny dobór środków transportu do realizacji poszczególnych operacji transportowych przy zadanej funkcji kryterium uwzględniającej założone ograniczenia.
EN
The article discusses the issue of selection of the means of transport to carry out transport operations: the chains of suppliers on the example of transport task, in production - for example the building project and in the storage warehouse. The developed method allows to determine the construction schedule (determination of the order of operations performed optimal means of transport) with the optimal function criterion (cost / time). The simulations have shown that this method allows an unambiguous selection of the means of transport (vehicles) to implement the particular technological operations at a given time/cost, taking into account the established constraints.
18
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W pracy przedstawiono metodę dekompozycji i ekwiwalentowania (MDE), zaproponowaną przez Ju. A. Jermolina i M. I. Alieksjejewa do obliczania parametrów niezawodnościowych sieci kanalizacyjnej, zdecydowanie prostszą i mniej uciążliwą w stosunku np. do metody przeglądu zupełnego, metody wzorów analitycznych, metody częstości uszkodzeń czy metody grafów. Analizując metodę przedstawioną w [1] autorzy przyjęli założenie, że tylko kanały będące krawędziami grafu zakończonymi liśćmi, czyli kanały zewnętrzne sieci, mają niezerowy wydatek, co stanowi ograniczenie jej praktycznego zastosowania. Drugą kwestią, mocno ograniczającą praktyczne zastosowanie MDE, jest niejawne, aczkolwiek jasno wynikające z samego algorytmu dekompozycji, założenie, że sieć jest drzewem binarnym. Takie założenie wyklucza przypadki, kiedy węzeł łączy więcej niż dwa kanały dopływające. Celem niniejszej pracy było przedstawienie rozwiązań tych problemów (ograniczeń).
EN
The paper presents the method of decomposition and equivalent (MDE), proposed by Jermolin and Alieksjejew. The method helps to calculate reliability parameters of the sewage system in a much simpler and less burdensome way, if compared to other methods such as: a complete review method, a method of analytical formulas, a method of failure frequency or a graph method. In the method presented in [1], the authors assumed that only the channels that constitute the edges of the graph tipped with leaves, or external network channels have a non-zero discharge. Such an assumption limits its practical application. Another issue, that strongly limits practical applications of MDE is the assumption, implicit but clearly resulting from the decomposition algorithm, that the network has a form of a binary tree. Such an assumption excludes cases when a node connects more than two inflow channels. The study presents solutions to these problems (constraints).
Przedstawiono problematykę doboru środków transportu do realizacji operacji transportowych na przykładzie zadania transportowego w łańcuchu dostaw. Opracowana metoda pozwala na wyznaczenie takiego planu realizacji operacji transportowych (wyznaczenie kolejności wykonywanych operacji transportowych określonymi środkami transportu), dla którego funkcja kryterium (koszt/czas) jest optymalna. Przeprowadzone badania symulacyjne wykazały, że zastosowanie tej metody umożliwia jednoznaczny dobór środków transportu do realizacji poszczególnych operacji transportowych przy minimalizowanym koszcie uwzględniającym założone ograniczenia.
EN
The article discusses the issue of selection of the means of transportation to implement transport operations based on an example of transport task in supply chain. This method allows to determinate the plan of transport operations. (definition of the order of performed operations), with the optimal function criteria (time / cost). The results of simulation research have proven that this method allows an unambiguous selection of the means of transportation in order to implement the particular transport operations at a given cost and considering the limitations.
The paper presents a methodology of study the properties of the transmission networks modeled by 3’rd and 4’th degree chordal rings, developed by the authors. Research methodology is based on two kinds of tests. First of them, measured the amount of data transmitted in different network structures using the HTTP protocol. The second, was measured quality of the received video stream, by the SSIM (Structural similarity) method. For testing, the set of virtual machines, connected by virtual network of 3rd and 4th chordal rings topology were used.
PL
W artykule zaprezentowano opracowaną przez autorów metodykę badania własności transmisyjnych sieci modelowanych przy pomocy grafów cięciwowych trzeciego i czwartego stopnia. W tym celu użyto dwóch testów. Jeden z nich polegał na pomiarze ilości danych przesyłanych w różnych strukturach sieciowych przy pomocy protokołu HTTP, natomiast w drugim mierzona była jakość odebranych obrazów w strumieniach video metodą porównawczą SSIM (Structural SIMilarity). Testy były wykonane według opracowanej przez autora koncepcji polegającej na wykorzystaniu zbioru maszyn wirtualnych połączonych pomiędzy sobą wirtualną siecią o topologii pierścieni cięciwowych trzeciego i czwartego stopnia.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.