Algorytm przeliczania dwuelementowych minimalnych przekrojów grafa skierowanego

• Autorzy: Grishkevich A.A.
• Języki publikacji: PL

Abstrakty

PL

Zaproponowano sposób kodowania kraty dystrybutywnej minimalnych przekrojów grafu. Opracowano algorytm przeliczania minimalnych dwuelementowych przekrojów grafu w kracie dystrybutywnej minimalnych przekrojów. Zaprezentowano przykład działania algorytmu.

EN

Coding of the distributive lattice of the minimal cuts graphs is offered. Enumerating algorithm of the minimal two-element cuts of the graph in a distributive lattice of the minimal cuts is developed. The example of work of the algorithm is presented.

Słowa kluczowe

PL

graf; minimalny przekrój; przekrój dwuelementowy; krata dystrybutywna; algorytm

EN

graph; minimum cut; two-element cut; distributive lattice; algorithm

• Wydawca: Wydawnictwo Politechniki Częstochowskiej
• Czasopismo: Informatyka Teoretyczna i Stosowana
• Rocznik: 2006
• Tom: R. 6, nr 10
• Strony: 85--100
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Grishkevich A.A.

• Instytut Informatyki, Wydział Elektryczny, Politechnika Częstochowska al. Armii Krajowej 17,42-200 Częstochowa

Bibliografia

• [1] Grishkevich A.A., Distributive lattice of minimum cut sets of a directed graph, Informatyka Teoretyczna i Stosowana 2004, 4, 7, 7-22.
• [2] Grishkevich A.A., Distributive lattices in the problems of structural analysis for complex systems, Informatyka Teoretyczna i Stosowana 2005, 5, 8, 19-27.
• [3] Allan R.N., Billinton R., De Oliveira M.F., An efficient algorithm for deducing the minimal cuts and reliability indices of a general network configuration, IEEE Trans. 1976, R-25, 4, 226-233.
• [4] Yuanlong S., A new simple algorithm for enumerating all minimal paths and cuts of a graph, Microelectron. Reliab. 1995, 35, 6, 973-976.
• [5] Billinton R., Guangbin L., A new technique for active minimal cut set selection used in substation reliability evaluation, Microelectron. Reliab. 1995, 35, 5, 797-805.
• [6] Al-Ghanim A.M., A heuristic tehnique for generating minimal path and cutsets of a general network, Computers & Industrial Engieneering 1999, 36, 45-55.
• [7] Электротехнический справочник: В 4 т. Т.3. Производство, передача и распределение электрической энергии. Под обшей ред. профессоров МЭИ В.Г. Герасимова и др. (гл. ред. А.И. Попов). 8-е изд., испр. и депо Издательство МЭИ, Москва 2002, 964 с.
• [8] Curet N.D., DeVinney J., Gaston M.E., An efficient network flow code for finding all minimum cost s-t cutsets, Computers & Operation Research 2002, 29, 205-219.
• [9] Ford L., Fuilkerson D., Przepływy w sieciach, Warszawa 1969.
• [10] Grishkevich A.A., Extreme structures of electrical circuits and systems mathematical models combinatorial methods research: Monography. Publishing house SUSU, Chelyabinsk 2004, 258 p. 2004, 258 р. (Гришкевич А.А.: Комбинаторные методы исследования экстремальных структур математических моделей электрических цепей и систем: Монография. Издательство ЮУрГУ, Челябинск 2004, 258 с.).
• [11] Aigner M., Combinatorial theory, Springer-Verlag 1979.
• [12] Ore O., Theory of graphs, Rhode Island 1962. (Ope O, 1 Теория графов. Издательство Наука, Москва 980, 336 c.).
• [13] Hu T., Integer programming and Network Flows. Addison-Wesley. Reading 1969.