Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: flow in networks

Sortuj według:

Ogranicz wyniki do:

Algorytm znajdowania przekrojów w grafie o krawędziach niezorientowanych

Piątek Ł.

Prace Naukowe Politechniki Śląskiej. Elektryka

2010

z. 1

53-64

Do szukania zbioru przekrojów w grafie o krawędziach niezorientowanych wykorzystano enumeracyjny algorytm znajdujący takie podziały zbioru wierzchołków grafu, które stanowią przekrój grafu. Algorytm wykorzystuje równoważność przekroju w grafie o krawędziach niezorientowanych rozumianego jako podzbiór krawędzi lub jako podział zbioru wierzchołków grafu. Na podstawie tej równoważności w toku działania algorytmu znajdowany jest zbiór przekrojów grafu w postaci zbioru podzbiorów zbioru krawędzi. Zaprezentowano program komputerowy implementujący algorytm oraz porównano czas znajdowania zbioru przekrojów w wybranych grafach.

For finding cut set in undirected graph an enumerative algorithm is used. The algorithm finds such divisions of vertices which are a graph cut. The algorithm utilizes equivalence of cut representation in an undirected graph either as a division of vertices or a subset of the graph edge set. With use of this equivalence the graph cut set as a set of graph edges is found. A computer program implementing the algorithm is presented and comparison of work time in chosen undirected graphs is performed.

Algorytm znajdowania jedno- i dwuelementowych minimalnych przekrojów w grafie niezorientowanym

Piątek Ł.

Prace Naukowe Politechniki Śląskiej. Elektryka

2010

z. 3

131-150

Opracowano nowy algorytm znajdowania jedno- i dwu-elementowych minimalnych przekrojów w grafie o krawędziach nieskierowanych. Algorytm wykorzystuje unikalną metodę przeszukania grafu. W trakcie znajdowania przekrojów jednoelementowych są wyznaczane podgrafy, w których nie istnieją żadne przekroje jednoelementowe. Podgrafy te są następnie poddawane unikalnej metodzie przeszukania. Jest znajdowany podział grafu na te obszary, gdzie każda z krawędzi tworzy przynajmniej jeden przekrój dwuelementowy oraz te obszary, gdzie żadna z krawędzi nie wchodzi w skład jakiegokolwiek przekroju. Obszary grafu, w których krawędzie wchodzą w skład przekrojów, są używane do konstrukcji pełnego zbioru minimalnych przekrojów dwuelementowych.

A new algorithm for finding one and two elements cuts in undirected graph was given. The algorithm is based on an unique method for searching the graph. During the finding of one element cuts such subgraphs are found, in which there are no one element cut. These subgraphs are then searched separately by an unique method. A division of the graph into areas is found. One type of the area is such that each edges in it is in at least one minimal two elements cut. The second type is such that not any edge is in a minimal two elements cut. Areas of the graph where edges are in cuts are used to construct the full set of two elements minimal cuts.