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

• Autorzy: Piątek, Ł.

Warianty tytułu

EN

Algorithm for finding one and two elements minimal cuts in undirected graph

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

graf; algorytm; przekrój; przepływ w sieciach; język programowania C++

EN

graph; algorithm; cut; flow in networks; C++ programming language

• Czasopismo: Prace Naukowe Politechniki Śląskiej. Elektryka
• Rocznik: 2010
• Tom: z. 3
• Strony: 131-150
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Piątek, Ł.

• Instytut Informatyki, Politechnika Częstochowska,

Bibliografia

• 1. Billinton R., Allan. R.: Reliability Evaluation of Engineering Systems, 2nd ed. Plenum Press, New York 1992.
• 2. Grabski F., Jaźwiński J.: Funkcje o losowych argumentach w zagadnieniach niezawodności, bezpieczeństwa i logistyki. WKŁ, Warszawa 2009.
• 3. Piątek Ł.: Algorytm znajdowania przekrojów w grafie o krawędziach niezorientowanych. Kwartalnik „Elektryka" 2010 z. 1, s. 53-64.
• 4. Grishkevich A.A.: Kombinatornye metody issledovanija ekstremalnych struktur matematiceskich modelej elektriceskich cepej i sistem. Izd. SUSU: Chelyabinsk 2004.
• 5. Grishkevich A.A.: Algorytm przeliczania dwuelementowych minimalnych przekrojów grafu skierowanego. „Informatyka Teoretyczna i Stosowana" 2006, R 6. nr 10, s. 85-100.
• 6. Grishkevich A., Piątek Ł.: Algorithm and Program for Finding Minimal and Quasi-Minimal Custs in Graphs. Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej 2008, nr 25, s. 49-52.
• 7. Ford L., Fullkerson D.: Flows in Networks, Princeton University Press. New Jork 1962
• 8. Stroustrup B.: Język C++. WNT, Warszawa 2002.
• 9. Billinton R., Lian. G.: A new technique for active minimal cut set selection used in substation reliability evaluation. "Journal of Microelectronics and Reliability" 1995, Vol. 35, No. 5, p. 797-805.
• 10. Piątek Ł.: Analiza niezawodności sieci sensorowych i akcyjnych. Kwartalnik „Elektryka" 2010, z. l,s. 61-68.