Ulepszony algorytm poszukiwania grafów o całkowitym spektrum w wielkich zbiorach grafów

• Autorzy: Niwińska M.

Warianty tytułu

EN

An improved algorithm for finding integral graphs in huge sets of graphs

• Języki publikacji: PL

Abstrakty

PL

Graf jest nazywany całkowitym, jeżeli wszystkie wartości własne należące do spektrum jego macierzy przyległości są liczbami całkowitymi. Rozważa się problem wyszukiwania spójnych grafów całkowitych w wielkich zbiorach grafów o danej liczbie wierzchołków i krawędzi. Proponuje się algorytm cgen1(n, k) generowania grafów o n wierzchołkach i o k krawędziach oraz dwustopniowego sprawdzania, czy dany graf jest całkowity. Ocenia się jego przydatność do znalezienia wszystkich spójnych grafów całkowitych na 13 wierzchołkach.

EN

A graph is called integral if the spectrum of its adjacency matrix consists of integers. A problem of finding all connected integral graphs in huge sets of graphs of order n and size k is considered. An improved algorithm cgen1(n, k) for generating these graphs is proposed. Its usefulness for finding all connected integral graphs on 13 vertices is tested.

Słowa kluczowe

PL

graf całkowity; algorytm grafowy

EN

integral graph; graph algorithm

• Wydawca: Poznańskie Towarzystwo Przyjaciół Nauk
• Czasopismo: Studia z Automatyki i Informatyki
• Rocznik: 2005
• Tom: T. 30
• Strony: 95--100
• Opis fizyczny: Bibliogr. 5 poz., tab.

Twórcy

autor

Niwińska M.

• Politechnika Poznańska, Instytut Automatyki i Inżynierii Informatycznej, Zakład Technologii i Systemów Informatycznych, pl. M. Skłodowskiej-Curie 5, 60-965 Poznań

Bibliografia

• [1] Balińska K.T., Zwierzyński K.T., Projektowanie algorytmów grafowych, Poznań, Wydawnictwo Politechniki Poznańskiej 2004.
• [2] Fortuna Z., Macukow B., Wąsowski J., Metody numeryczne, Warszawa, Wydawnictwo Naukowo--techniczne, Warszawa 1982.
• [3] Marciniak A., Gregulec D., Kaczmarek J., Podstawowe procedury numeryczne w języku Turbo Pascal, Poznań, Wydawnictwo Nakom 1997.
• [4] McKay B.D., http://cs.anu.edu.au/people/bdm/index.html.
• [5] Niwińska M.A., Ocena przydatności metody potęgowej w algorytmie testowania całkowitości spektrum wielkich zbiorów grafów, raport techniczny nr 503, Instytut Automatyki i Inżynierii Informatycznej, Politechnika Poznańska 2004, s.1-18.