Wyniki wyszukiwania - BazTech

1

Zwarte końcówkowe kolorowanie grafów

Janczewski R., Małafiejska A., Małafiejski M.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2007

|

T. 13

481-488

PL

W pracy rozważamy nowy model kolorowania grafów, mianowicie zwartego kolorowania końcówek (incydencji) grafu. W klasycznym zwartym kolorowaniu krawędzi grafu staramy się zapewnić, aby zbiór kolorów krawędzi sąsiednich do danego wierzchołka tworzył przedział (zwarty zbiór). Podobny warunek można nałożyć na zbiór kolorów incydencji wychodzących z wierzchołka w końcówkowym kolorowaniu grafu. W pracy, obok zdefiniowania problemu i wskazania potencjalnych zastosowań, wyznaczone zostały oszacowania dolne i górne na wartość szukanego kryterium, ponadto zaproponowane zostały dokładne wartości zwartego końcówkowego indeksu chromatycznego dla wybranych klas grafów: ścieżek, cykli, gwiazd, 2-gwiazd, k-gwiazd, wachlarzy, kół, grafów pełnych, pełnych dwudzielnych oraz pełnych k-dzielnych.

EN

In the paper we present a new model of consecutive incidence graph coloring arising from two previous known models: consecutive (interval) edge coloring and incidence coloring. We formulate the problem and present same applications. We proposed same lower and upper bounds for consecutive incidence chromatic index and constructed polynomial time algorithms solving the problem for same classes of graphs: paths, cycles, stars and k-stars, wheels, fang, complete graphs and complete k-partite graphs.

2

Porównywanie topologii drzew i sieci filogenetycznych z wykorzystaniem metryki błędu

Bogdanowicz D., Małafiejska A.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2007

|

T. 12

117-124

PL

Podstawowymi modelami historii ewolucji organizmów są drzewa i sieci filogenetyczne. Ponieważ algorytmy konstrukcji filogenów zwracają różne wyniki dla tych samych danych wejściowych, powstaje problem oceny, który filogen najlepiej reprezentuje historię ewolucji dla zadanego zbioru gatunków. W pracy podano definicję metryki dla przestrzeni drzew o n liściach, zwanej metryką błędu. Dokonano przeglądu miar odległości na przestrzeni sieci filogenetycznych, bazujących na metryce wprowadzonej dla drzew, wraz z analizą modelu, dla które-go miary te spełniają nierówność trójkąta. Z wykorzystaniem programu phylonet przeprowadzono porównanie przykładowych topologii zarówno drzew, jak i sieci, oraz dokonano oceny, na ile wprowadzone miary odzwierciedlają rzeczywistość.

EN

Phylogenetic trees and networks are based models of evolution history. Because algorithm for constructions phylogenies output different values for the same input data, there is a problem of which one from phylogenies is the best representation of history of evolution for given set of species. There is given a metric definition for n-leaves tree space called error metric in this paper. For phylogenetic network space, there are defined few distance funcion based on error metric for trees, which satisfy triangle inequality only in specific case of networks. Using phylonet software there is made a comparison between topology of trees and networks, and a conclusion about reality of each metric function.

3

Metryczny problem komiwojażera z warunkiem czterech punktów

Małafiejska A.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2007

|

T. 13

473-480

PL

Metryczny problem komiwojażera polegający na znalezieniu najkrótszej trasy między zadanymi obiektami jest znanym zagadnieniem z klasy problemów trudnych. W pracy rozważany jest szczególny przypadek tego problemu, gdy macierz odległości między punktami spełnia warunek czterech punktów. Warunek ten jest określony dla każdych czterech punktów, i mówi tyle, że dobierając pary na trzy możliwe sposoby, dwie sumy odległości w parach muszą być równe i większe od trzeciej. W pracy podano algorytm wielomianowy dla rozwiązania tego problemu oraz jego możliwe zastosowania.

EN

Metric traveling-salesman problem is based on finding the shortest way between given objects and it is one of the well known NP-hard problem. In this article it is considered a specific subproblem of MTSP, where distance ma-trix between objects satisfy the four point condition. This condition is given for every four points and tells that taking three possible pairs of points, two of sum of pair distance most be equal and greater then the third one. In this article it is given a polynomial-time algorithm for solving this subproblem and there are written Some useless of this solution