Generacja cykli fundamentalnych metodą dynamicznego budowania drzewa grafu

• Autorzy: Pułka A. , Golly Ł.

Warianty tytułu

EN

Fundamental cycles generation based on dynamic constructing of graph trees

• Języki publikacji: PL

Abstrakty

PL

Tematem artykułu jest oryginalny algorytm umożliwiający wyznaczanie najmniejszych cykli fundamentalnych w grafie nieskierowanym. Zaprezentowane podejście wykorzystuje specyficzną reprezentację grafu w postaci trójkątnej macierzy sąsiedztwa. Na podstawie wyznaczonych cykli algorytm buduje drzewo grafu dodając kolejno wyznaczone w poprzednim kroku cykle. Zaprezentowano kolejne kroki algorytmu wraz z przykładem oraz porównano go z innymi metodami. Na koniec, przedstawiono wyniki eksperymentalne oraz wnioski pokazujące zalety zastosowanej metody.

EN

The paper introduces the original algorithm of finding minimal fundamental cycles in the undirected graph. The presented approach uses a specific graph representation of the triangular neighborhood matrix for finding minimal cycles. Then the algorithm generates the graph tree by adding these cycles. The methodology is described step by step on examples and compared to other approaches in the field. Finally, the results of some tests and conclusions emphasizing the advantages of the algorithm summarize the work.

Słowa kluczowe

PL

teoria grafów; analiza analogowych układów elektronicznych; teoria obwodów; analiza symboliczna

EN

graph theory; analog electronic circuits analysis; circuit theory; symbolic analysis

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2010
• Tom: Vol. 51, nr 12
• Strony: 75--77
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Pułka A.

autor

Golly Ł.

• Politechnika Śląska, Instytut Elektroniki, Gliwice

Bibliografia

• [1] Tarjan R. E., „Depth-first search and linear graph algorithms", In: SIAM Journal on Computing. Vol. 1 (1972), No. 2, pp. 146-160.
• [2] Deo N., "Breadth and depth first searches in graph theoretic algorithms" Journal on Computing Soc India 4 (1974), pp. 1-8.
• [3] Deo N., "Minimum-length fundamental cycle set", IEEE Transactions on Circuits and Systems, Vol. 26 (1979), pp. 894-895.
• [4] Deo N., Prabhu G., Krishnamoorthy M., "Algorithms for generating fundamental cycle in a graph", ACM Transactions o Mathematical Software (8), (1982), pp. 26-42.
• [5] Balakrishnan, V. K., "Graph Theory" (1st ed.). McGraw-Hill, 1997.
• [6] A. Brambilla, A. Premoli, "Rigorous event-driven (red) analysis of large-scale nonlinear rc circuits", IEEE Transactions on Circuit and systems-I: Fundamental theory and applications, Vol. 48 (8), (2001) pp. 938-946.
• [7] E. Amaldi, L. Libretti, F. Maffioli, N. Maculan, "Algorithms for finding fundamental cycles in graphs", Electronic Notes in Mathematics Vol. 17 (2004), pp. 29-33.
• [8] A. Pułka, Ł. Golly, "A Heterogenous Approach to Symbolic Calculations Based on Structural Numbers", Proceedings of IEEE ICECS 2009 Conference, Medina-Hammamet, TUNISIA, Dec. 13-16, pp. 163-166.
• [9] Graph Benchmarks from Web Site: http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm.