Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: graf całkowity

Sortuj według:

Ogranicz wyniki do:

On generating 4-regular integral graphs

Balińska K., Simić K., Zwierzyński K.

Studia z Automatyki i Informatyki

2006

T. 31

7-16

A graph is called integral if all eigenvalues of its adjacency matrix are integers. Exact and randomized algorithms for generating 4-regular graphs and sieving integral graphs are defined. All connected 4-regular integral graphs of order 12 < n < 20 generated by a computer search are presented and some of their properties are indicated. A new algorithm for constructing 4-regular integral graphs of order n ≥ 20 based on the experimental results is proposed.

Graf nazywamy całkowitym, jeżeli wszystkie wartości własne jego macierzy przyległości są liczbami całkowitymi. Określono algorytmy, dokładny i zrandomizowany, generowania spójnych grafów 4-regularnych i odsiewania grafów całkowitych. Przedstawiono struktury wszystkich spójnych 4-regularnych grafów całkowitych rzędu 12 < n < 20, wygenerowanych z wykorzystaniem opracowanych algorytmów oraz zbadano ich wybrane niezmienniki liczbowe i strukturalne. Wykorzystując wyniki eksperymentów obliczeniowych zaprojektowano nowy algorytm generowania grafów tej klasy rzędu n ≥ 20.

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

Niwińska M.

Studia z Automatyki i Informatyki

2005

T. 30

95--100

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.

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.