Wyniki wyszukiwania dla: KOLOROWANIE KONTRASTOWE

• Kontrastowe kolorowanie grafów

  Publikacja

  • R. Janczewski

  - Rok 2002

  Niniejszy rozdział omawia kontrastowe kolorowanie grafów. Podana zostałajego definicja i podstawowe własności, zastosowania oraz złożoność oblicze-niowa problemów rozważanych w ramach tej dziedziny.

• Uogólnione algorytmy zachłanne w kontrastowym kolorowaniu grafów.

  Publikacja

  • R. Janczewski

  - Rok 2004

  Niniejszy referat poświęcony jest uogólnionym algorytmom zachłannym. Zawiera ich opis, krótką analizę ich własności oraz wyniki testów komputerowych którym zostały poddane.

• O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach

  Publikacja

  • K. Giaro
  • R. Janczewski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Rok 2002

  Niniejszy artykuł poświęcony jest złożoności obliczeniowej problemu przydziału częstotliwości. Zawiera dowód tego, że jest on NP-trudny nawet dla grafów interferencji, będących grafami dwudzielnymi, oraz wielomianowy algorytm rozwiązujący ten problem dla grafów interferencji, będących częściowymi k-drzewami.

• Kolorowanie hipergrafów

  Publikacja

  • M. Kubale
  • K. Piwakowski
  • P. Obszarski

  - Rok 2006

  Hipergraf to struktura stanowiąca pewne uogólnienie grafu. Oprócz tradycyjnych krawędzi dwuelementowych dopuszcza ona także krawędzie, które zawierają inną, przeważnie większą liczbę wierzchołków. W tej pracy pokażemy kilka modeli kolorowania hipergrafów, takich jak kolorowanie krawędzi, kolorowanie wierzchołków i tzw. CD-kolorowanie, przedstawimy ich podstawowe własności oraz wskażemy zastosowania.

• Kolorowanie końcówkowe multidrzew

  Publikacja

  • R. Janczewski
  • M. Małafiejski

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

  W pracy przedstawiono nowy model kolorowania grafów, mianowicie kolorowanie końcówkowe. Naszkicowano związki łączące ten model z klasycznymi modelami kolorowania oraz przedstawiono wielomianowy algorytm optymalnie końcówkowo kolorujący multidrzewa.

• Cyrkularne kolorowanie grafów

  Publikacja

  • A. Nadolski

  - Rok 2002

  Rozdział zawiera definicje oraz większość znanych własności cyrkularnego ko-lorowania grafów w wersji wierzchołkowej oraz krawędziowej. Podano znanezwiązki tego rodzaju kolorowania z innymi modelami kolorowania grafów. Wpracy zawarto także przykłady możliwych zastosowań cyrkularnego kolorowaniaw szeregowaniu zadań.

• Sprawiedliwe kolorowanie grafów

  Publikacja

  • H. Furmańczyk

  - Rok 2002

  Kolorowanie sprawiedliwe jest kolorowaniem klasycznym z dodatkowym ograni-czeniem: chcemy, aby krotności użycia kolorów różniły się co najwyżej o je-den. W pracy przedstawiamy wyniki dotyczące sprawiedliwego kolorowania wie-rzchołków, krawędzi oraz obu tych elementów jednocześnie. Ponieważ problemjest NP-zupełny w ogólnym przypadku, poszukuje się algorytmów przybliżonych.Przedstawiamy dwa takie algorytmy.

• Harmoniczne kolorowanie grafów

  Publikacja

  • M. Kubale

  - Rok 2002

  W rozdziale omówiono tzw. harmoniczne kolorowanie grafów, które jest odmia-ną klasycznego kolorowania wierzchołków grafów. Podano najważniejsze własno-ści tego sposobu kolorowania grafów i jego potencjalne zastosowanie w radio-komunikacji lotniczej i projektoaniu funkcji mieszających. Podano równieżtzw. algorytm degresywny, który koloruje każdy graf za pomocą liczby kolorównie przekraczającej w dwójnasób harmonicznej liczby...

• Listowe kolorowanie grafów

  Publikacja

  • K. Piwakowski

  - Rok 2002

  W klasycznym modelu kolorowania grafów,kolor przydzielany wierzchołkowi jestograniczony przez regułę zakazującą pokolorowania dwóch sąsiednich wierz-chołków tym samym kolorem. Kolorowanie listowe wprowadza dodatkowe ograni-czenie: każdy wierzchołek posiada z góry określony zbiór dopuszczalnych ko-lorów. Rozważamy jak duża może być różnica pomiędzy liczbą chromatyczną ilistową liczbą chromatyczną oraz dla jakich klas grafów...

• Zwarte kolorowanie krawędzi

  Publikacja

  • K. Giaro

  - Rok 2002

  Praca omawia model zwartego kolorowania grafów i jego zastosowania w szere-gowaniu zadań. Podano podstawowe właściwości kolorowania zwartego, a takżegrafów dających się w ten sposób kolorować. przedstawiono szereg rodzin gra-fów dwudzielnych posiadających zwarte pokolorowania. Zdefiniowano też pewnąmiarę ''niezwartości'' kolorowania krawędziowego zwaną stratnością.