Czasopismo | PRZEGLĄD ELEKTROTECHNICZNY | Rocznik 2012 - zeszyt 11a

Modele i metody kolorowania grafów. Część II

Marek KUBALE

nr katalogowy: 72082

Niniejszy artykuł jest drugą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano różne kryteria i ograniczenia modyfikujące kolorowanie klasyczne. Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podano oszacowania na liczbę chromatyczną (indeks chromatyczny) oraz podano potencjalne zastosowania rozważanych modeli w problemach naukowo-technicznych. Abstract. This is the second of a couple of review papers on models and methods of graph coloring. We present herein the main models of graph coloring from a practical point of view. In particular, we show various criteria and modifications of classical coloring model. Since graph coloring is NP-hard in various modifications and variants, we give simple bounds on the chromatic number (chromatic index) as well as we give potential applications of the chromatic methods in science and technology. (Models and methods of graph coloring - part II). Słowa kluczowe: kolorowanie grafu, liczba chromatyczna, indeks chromatyczny, NP-trudność, algorytm wielomianowy Keywords: graph coloring, chromatic number, chromatic index, NP-hardness, polynomial algorithm Wstęp Problemy kolorowania grafów należą do najtrudniejszych problemów kombinatorycznych w sensie złożoności obliczeniowej. Wykazano, że skonstruowanie algorytmu aproksymacyjnego o polilogarytmicznej funkcji dobroci jest NP-trudne, chyba że P = NP [1]. Z tego względu jednym z kluczowych zagadnień teorii kolorowania grafów jest określenie granicy pomiędzy przypadkami obliczeniowo łatwymi, tj. wielomianowymi, które tworzą klasę P oraz trudnymi, czyli tzw. NP-zupełnymi (NPC). Zagadnienia te są ściśle związane z naczelnym problemem współczesnej informatyki teoretycznej, jakim jest pytanie milenijne o to, czy P = NP. Najczęściej w problemie kolorowania grafów bada się dwa za[...]

Jeśli masz wykupiony/przyznany dostęp - zaloguj się. Skorzystaj z naszych propozycji zakupu!

Publikacja


e-Publikacja (format pdf) - nr 72082 "Modele i metody kolorowan..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


PRZEGLĄD ELEKTROTECHNICZNY - e-zeszyt (pdf) 2012-11a licencja: Osobista Produkt cyfrowy	55.00 zł

Prenumerata

PRZEGLĄD ELEKTROTECHNICZNY - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

762.00 zł

PRZEGLĄD ELEKTROTECHNICZNY - PAKIET prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD ELEKTROTECHNICZNY - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	1002.00 zł brutto 927.78 zł netto 74.22 zł VAT (stawka VAT 8%)

1002.00 zł

PRZEGLĄD ELEKTROTECHNICZNY - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD ELEKTROTECHNICZNY - papierowa prenumerata roczna	960.00 zł brutto 888.89 zł netto 71.11 zł VAT (stawka VAT 8%)
PRZEGLĄD ELEKTROTECHNICZNY - pakowanie i wysyłka	42.00 zł brutto 34.15 zł netto 7.85 zł VAT (stawka VAT 23%)

1002.00 zł

Zeszyt

2012-11a

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma