Algorithm and program for finding minimal and quasi-minimal cuts in graphs

• Autorzy: Grishkeyich A. , Piątek Ł.

Warianty tytułu

PL

Algorytm i program znajdowania minimalnych i quasi-minimalnych przekrojów grafu

• Konferencja: Zastosowanie komputerów w nauce i technice 2008. XVIII cykl seminariów zorganizowanych przez Oddział Gdański PTETiS (18 ; 2008 ; Gdańsk, Polska)
• Języki publikacji: EN

Abstrakty

EN

It was found, that the set of minimum cuts, separating two chosen vertices in graph, have the structure of distributive lattice. It was developed an effective procedure for finding the set of 1, 2 and 3 elements cuts in graph based on the consideration of distributive lattice of the set of minimum cuts. The procedure consists of first, the algorithm for finding indecomposable minimal cuts of distributive lattice. Second, algorithm for synthesis, using resulting subset from stage one, of the entire set of minimum cuts. The third, is the algorithm for describing the set of quasi-minimum (close to the minimum, next to minimum) cuts in the form of sum of distributive lattices of minimal cuts found for the modified function of weight. The computer program, implementing these algorithms, is presented with examples.

PL

Ustalono, że zbiór minimalnych przekrojów, rozdzielających dwa zadane wierzchołki grafu, z wprowadzonymi na i operacjami ma strukturę kraty dystrybutywnej. Opracowano skuteczną algorytmiczną procedurę znajdowania zbioru jed dwu i trzy elementowych przekrojów grafu bazującą na rozpatrzeniu dystrybutywnych krat zbioru minimalnych przekrojów grafu. Procedura składa się z, po pierwsze, algorytmu szukania nierozkładalnych minimalnych przekrojów Dystrybutywnej, po drugie, algorytmu syntezy po tym podzbiorze w kracie dystrybutywnej całego poszukiwanego zbioru minimalnych przekrojów i, po trzecie, algorytmu opisu zbioru quasi-minimalnych (bliskich do minimalnych, następnych po minimalnych) przekrojów w formie sumy krat dystrybutywnych minimalnych przekrojów, znalezionych dla zmodyfikowanej funkcji wagi. Przedstawiono zrealizowany program komputerowy i przedstawiono przykłady pracy programu.

Słowa kluczowe

EN

distributive lattice; indecomposable cut; one-, two-, three- elements cut

PL

krata dystrybutywna; przekrój nierozkladalny; jeden, dwu, trzy elementowy przekrój

• Wydawca: Wydział Elektrotechniki i Automatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej
• Rocznik: 2008
• Tom: Nr 25
• Strony: 49--52
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Grishkeyich A.

autor

Piątek Ł.

• Politechnika Częstochowska, al. Armii Krajowej 17, 42-200 Częstochowa Tel, fax:[phone],

Bibliografia

• 1. Ford L., Fulkerson D.: Flows in Networks Princeton University Press N. J., 1962, p. 194.
• 2. Grishkevich A. A.: Combinatorics methods of finding extreme structures of mathematic model of electric power transmission and systems Chelyabinsk Izd. SUSU 2004 (RU), p. 258, ISBN 5-696-02780-6.
• 3. Grishkevich A.A.: Distributive lattice of minimum cut sets of a directed graph, Informatyka teoretyczna i stosowana Vol. 4, Nr 7, Instytut matematyki informatyki Politechnika Częstochowska 2004, p. 7-22, ISSN 1643-2355.
• 4. Grishkevich A.A.: Algorithm for finding 2 elements minimal cut in directed graph, Informatyka Teoretycznal i Stosowana Vol. 6, Nr 10, Instytut matematyki i informatyki Politechnika Częstochowska 2006 (PL), p. 85-100, ISSN 1643-2355.
• 5. Grishkevich A.A., Piątek Ł.: Algorithm for fmding minimal 3 elements cuts in graph, Polish Journal Environmental Studies Vol. 16, No 4a, 2007, p. 218-222, ISSN 1230-1485.
• 6. Grishkevich A.A., Piątek Ł.: Program of Enumeration of set l, 2 and 3 element cuts - Accession number OFAP 10263, number of state registration (accession number YNTIC) 50200800673, 2008 Moskow (RU).
• 7. Billinton R., Lian G.: A new technique for active minimal cut set selection used in substation reliabilityl evaluation, Electric Power Systems Research, Vol. 35, No. 5, 1995, p. 797-805, ISSN 0026-2714.
• 8. Filipiak S.: Methods of reliability estimations high/medium voltage electrical substations, Numerical Methods and Computer Systems in Automatic Control and Electrical Engineering, Częstochowa University of Technology, 2005 (PL), p. 97-102, ISBN 83-7193-288-X.
• 9. Uschakov I.A.: The Estimation, forecasting maintenance of reliability of networks of COMPUTER Moscow Mechanical engineering, 1989 (RU), p. 71, ISBN 5-217-00704-4.
• 10. Ramirez-Marquez J.E., Coit D.W. : A Monte-Carlo simulation approach for approximating multi-state terminal reliability, Reliability Engineering and System Safety, Vol. 87, 2005, p. 253-264