Czasopismo | ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA | Rocznik 2010 - zeszyt 9

Sprzętowa implementacja zachłannego algorytmu kolorowania grafu

BERNARD WYRWOŁ

nr katalogowy: 54260

Metody podziału zbioru A, zawierającego n elementów, na rozłączne podzbiory Ak zwykle bazują na algorytmach kolorowania grafów [3, 4]. W tym przypadku wierzchołkom V={v1, v2, …, vn} grafu nieskierowanego G={V, E, ψ} przyporządkowuje się elementy zbioru, natomiast krawędzie łączące te wierzchołki E={e1, e2, …, em} określają czy dwa elementy zbioru A mogą znaleźć się w jednym podzbiorze Ak (w przypadku grafu zgodności) czy też nie (w przypadku grafu niezgodności). Funkcja incydencji ψ określa, która para wierzchołków (vi , vj) połączona jest krawędzią el (i, j =1, …, n; i ≠ j; l =1, …, m). Przykład grafu nieskierowanego pokazany został na rys. 1. W podanym algorytmie wierzchołki V={v1, v2, …, vn} kolorowane są po kolei, począwszy od v1. Przydzielanie danemu wierzchołkowi vi (i =1, …, n) najniższego legalnego koloru odbywa się w ten sposób, że z całej dostępnej palety kolorów K={k1, k2, …, kn} usuwane są te kolory, którymi pokolorowane są wierzchołki sąsiednie. Z pozostałych na palecie kolorów wybiera się ten o najniższym indeksie. Schemat blokowy algorytmu zachłannego kolorowania grafu przedstawia rys. 3. Rys. 1. Przykład grafu nieskierowanego Fig. 1. Example undirected graph Rys. 2. Pseudokod zachłannego algorytmu kolorowania grafu Fig. 2. Graph greedy coloring algorithm pseudo code Rys. 3. Ogólny schemat blokowy zachłannego algorytmu kolorowania grafu Fig. 3. Graph greedy coloring algorithm general diagram v1 v2 v4 v3 e1 e2 e3 e4 V={v1, v2, v3, v4} E={e1, e2, e3, e4} ψ(e1)={v1, v2} ψ(e2 )={v2, v3} ψ(e3 )={v3, v4} ψ(e4 )={v2, v4} Kolorowanie właściwe wierzchołków grafu G polega na znalezieniu funkcji C: V→K przyporządkowującej wierzchołkom V kolory ze skończonego zbioru K={k1, k2, …, kn} w taki sposób, że jeśli vi i vj sąsiadują, to wierzchołki muszą posiadać różne kolory C(vi ) ≠ C(vj ). Maksymalna liczba kolorów niezbę[...]

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

Publikacja


e-Publikacja (format pdf) - nr 54260 "Sprzętowa implementacja z..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - e-zeszyt (pdf) 2010-9 licencja: Osobista Produkt cyfrowy	35.00 zł

Prenumerata

ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

420.00 zł

ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - papierowa prenumerata roczna	528.00 zł brutto 488.89 zł netto 39.11 zł VAT (stawka VAT 8%)
ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - pakowanie i wysyłka	42.00 zł brutto 34.15 zł netto 7.85 zł VAT (stawka VAT 23%)

570.00 zł

ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - PAKIET prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	636.00 zł brutto 588.89 zł netto 47.11 zł VAT (stawka VAT 8%)

636.00 zł

Zeszyt

2010-9

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma