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.
One of the best ways of modelling a transport network is to use a graph with vertices and edges. They represent nodes and arcs of such network respectively. Graph theory gives dozens of parameters or characteristics, including a connectivity, spanning trees or the different types of domination number and problems related to it. The main aim of the paper is to show graph theory methods and algorithms helpful in modelling and optimization of a transportation network. Firstly, the descriptions of basic notations in graph theory are introduced. Next, the concepts of domination, bondage number, edge-subdivision and their implementations to the transportation network description and modeling are proposed. Moreover, the algorithms for finding spanning tree or maximal flow in networks are presented. Finally, the possible usage of distinguishing concepts to exemplary transportation network is shown. The conclusions and future directions of work are presented at the end of the paper.
PL
Jednym z najlepszych sposobów modelowania sieci transportowej jest użycie grafu z wierzchołkami i krawędziami. Reprezentują one odpowiednio węzły i łuki takiej sieci. Teoria grafów daje możliwość użycia dziesiątek parametrów lub charakterystyk, w tym spójności, drzew spinających lub różnych typów liczb dominowania i związanych z tym problemów. Głównym celem artykułu jest przedstawienie metod i algorytmów teorii grafów pomocnych w modelowaniu i optymalizacji sieci transportowej. Po pierwsze, wprowadzono opisy podstawowych pojęć w teorii grafów. Następnie zaprezentowano koncepcje dominowania, liczby zniewolenia czy podziału krawędzi grafu oraz ich implementacji do opisu i modelowania sieci transportowej. Ponadto przedstawiono algorytmy do wyszukiwania drzewa opinającego i maksymalnego przepływu w sieciach. Wreszcie pokazano możliwe sposoby wykorzystania wyróżnionych koncepcji do przykładu sieci transportowej. Na zakończenia przedstawiono wnioski i przyszłe kierunki prac.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Probabilistic properties of dates of winter, summer and annual maximum flows were studied using circular statistics in three catchments differing in topographic conditions; a lowland, highland and mountainous catchment. The circular measures of location and dispersion were used in the long-term samples of dates of maxima. The mixture of von Mises distributions was assumed as the theoretical distribution function of the date of winter, summer and annual maximum flow. The number of components was selected on the basis of the corrected Akaike Information Criterion and the parameters were estimated by means of the Maximum Likelihood method. The goodness of fit was assessed using both the correlation between quantiles and a version of the Kuiper’s and Watson’s test. Results show that the number of components varied between catchments and it was different for seasonal and annual maxima. Differences between catchments in circular characteristics were explained using climatic factors such as precipitation and temperature. Further studies may include circular grouping catchments based on similarity between distribution functions and the linkage between dates of maximum precipitation and maximum flow.
In the article presented above the seasonal and multiannual variation and spatial differentiation of a few parameters were studied. These specifications were obtained on the basis of maximum discharges registered for 71 water-gauges in central Poland in the second half of the 20th century (1951-2002) (Table 1). In particular, seasonal and spatial regularities of maximum outflows, maximum discharges (WWQs and WWQs) and Françou-Rodier Flood Ratings (K) appearance were established. The greatest number of WWQs (WWQs) in central Poland was registered during the cold half-year (months: January and March) and in the summer (July and August). In autumn and early winter months (from September till December) maximum outflows were not registered. In central Poland the maximum unit runoffs are not very differentiated as they range from 23 to 228 dm3∙s-1 km-2. These values can be assumed as the representatives of the regional extremes. Regression equations between catchment surface areas and maximum discharges (unit runoffs) were also calculated - equation 1 (Fig. 4) and equation 2 (Fig. 6). In the catchments of the region, the maximum unit runoffs values (WWQ) decrease very slowly with increasing catchment areas (compare with Fig. 6). Spatial differentiation of Françou-Rodier Flood Indexes (K, equation 3) was under investigation. Moreover, the regional equation of the relationship between WWQ and K (equation 4, Fig. 8) was computed. Due to the Françou-Rodier Flood Indexes (K), the risk of precipitation and snowmelt/rainfall floods in the small and large central Poland river valleys is of minor importance. In general, some previously identified patterns, which describe the relationships between WWQ, WWQ, K and A in the global, continental and national scale are also visible considering the regional scale (central Poland area). The aim of this study was also to investigate the multiannual variability of the Flood Indexes (IWW K) – equation 5 and Fig. 9, which were calculated for central Poland area. In the second half of the 20th century the IWW indexes, which were determined in this region were continuously declining. It proves that the scale and the frequency of floods in the rivers of the particular area are getting reduced. The relationships and linkages between annual North Atlantic Oscillation Indexes (NAO) and Flood Indexes (WWQ) were also studied, and it can be stated that they are unclear and statistically insignificant (Fig. 10) and cannot be treated as simple statistical correlations.
In this paper problem of graph-based image segmentation was regarded. Specifically, min-cut/max-flow approach proposed by Boykov and Jolly was investigated. The influence of functions describing boundary and regional conditions on results of image segmentation of various images were presented and discussed.
PL
W artykule rozważono problem segmentacji obrazu opartej na grafach. W szczególności skupiono się na metodzie maksymalnego przepływu, którą zaproponowali Boykov i Jolly. Główną uwagę skupiono na analizie wpływu funkcji opisujących relacje pomiędzy sąsiadującymi pikselami na wyniki segmentacji obrazów. Dyskusję przeprowadzono na podstawie testowych obrazów o różnych właściwościach.
W zadaniach maksymalnego przepływu poszukujemy największej z możliwych ilości przesyłanego medium. Realne sytuacje pozwalają stwierdzić, że zarówno przepustowości jak i przepływy mają charakter rozmyty to znaczy, że nie można dokładnie oszacować z góry ich wartości w konkretnych momentach realizacji przesyłu. Analiza powstałych zagrożeń może dotyczyć niedowartościowania lub przewartościowania znaczenia przepustowości i realnego przepływu. Algorytmy maksymalnego przepływu (Forda-Fulkersona, Edmondsa-Karpa [9]) pozwalają znaleźć rozwiązanie na podstawie wybieranych kolejno ścieżek przepływowych. Wybór kolejności przepływów decyduje o uzyskanym rozwiązaniu. Na wybór kolejności ścieżek przepływu ma wpływ także rozmytość zarówno przepustowości jak i samego przepływu. Celem pracy jest wypracowanie strategii ustalenia kolejności przepływów w warunkach rozmytości parametrów.
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ć.