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

• Autorzy: Piątek, Ł.

Warianty tytułu

EN

Algorithm for finding cuts in undirected graph

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

graf; przekrój grafu; algorytm; przepływ w sieciach

EN

graph; graph cut; algorithm; flow in networks

• Czasopismo: Prace Naukowe Politechniki Śląskiej. Elektryka
• Rocznik: 2010
• Tom: z. 1
• Strony: 53-64
• Opis fizyczny: Bibliogr. 8 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. Shooman M.: Reliability of computer systems and networks. Fault tolerance analysis and design, John Wiley and Son, New York 2002..
• 4. Billinton R., Lian G., A new technique for active minimal cut set selection used in substation reliability evaluation. "Electric Power Systems Research" 1995, Vol. 35, No. 5, p. 797-805.
• 5. Filipiak S.: Metody oceny niezawodności stacji elektroenergetycznych WN/SN. Metody i Systemy Komputerowe w Automatyce i Elektrotechnice, Częstochowa 2005.
• 6. Ruskey F.: Combinatorial generation. Victoria 2003.
• 7. Stroustrup B.: Język C++. WNT, Warszawa 2002.
• 8. Baron B., Piątek Ł.: Metody numeryczne w C++. Wydawnictwo Politechniki Śląskiej, Gliwice 2004.