Wyniki wyszukiwania - BazTech

1

A method involving constraint programming for generating integral graphs without ± 1 in the spectrum : a case study

Zwierzyński K., Meissner A., Niwińska M.

Studia z Automatyki i Informatyki

|

2010

|

T. 35

105-114

EN

We consider a method where the constraint programming over finite domains is used for describing relationships among some properties of graphs. The process of constraint solving results in the set of values, which act as input parameters for the graph generation algorithm. In this way, the space of possibly generated graphs is reduced. We present a case study of the application of this approach to the problem of finding all connected, integral, non-regular and bipartite graphs, with a maximum vertex degree four not containing ± 1 in the spectrum (i.e., SL4-graphs).

PL

W artykule rozważa się wariant metody konstruowania grafów poprzez generowanie a następnie przeszukiwanie klas grafów, do których należą rozpatrywane grafy. Proponuje się przy tym zastosowanie metodyki programowania z więzami (ang. constraint programming over finite domains) do opisywania zależności, jakie zachodzą między niektórymi właściwościami grafów. W ten sposób ogranicza się a zarazem precyzuje zbiór parametrów algorytmu generującego grafy. W konsekwencji, zostaje zredukowana przestrzeń, którą należy przeszukiwać. Praca zawiera analizę przykładu zastosowania tego ujęcia do skonstruowania wszystkich spójnych, nieregularnych, dwudzielnych grafów całkowitych o maksymalnym stopniu wierzchołków równym 4 niezawierających ± 1 w spektrum.

2

On generating graphs with bounded degree and a given chromatic number

Balińska K., Quintas L., Zwierzyński K.

Studia z Automatyki i Informatyki

|

2007

|

T. 32

7-16

EN

The distribution of the chromatic number χ of random graphs with bounded degree (f-graphs) of order n generated in the G (n, f) model is studied. Introducing the predominant chromatic number results in determining values of parameters f and n that can be chosen in this model to generate graphs with a given χ.

PL

Rozważa się zależność rozkładu prawdopodobieństwa liczby chromatycznej χ grafów losowych G (n, f) od parametrów modelu n (liczba wierzchołków) i f (ograniczenie stopnia). Grafy generowane w tym modelu są to maksymalne (krawędziowo) grafy z ograniczonym stopniem (f-grafy) odpowiadające stanom końcowym losowego procesu grafowego RfGP. W obszernym eksperymencie obliczeniowym wykorzystano algorytm generowania grafów G (n, f) i wprowadzając pojęcie dominującej liczby chromatycznej określono wartości f i n, przy których generowane są f-grafy o danej wartości χ.

3

On generating 4-regular integral graphs

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

Studia z Automatyki i Informatyki

|

2006

|

T. 31

7-16

EN

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.

PL

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.