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

Generacja cykli fundamentalnych metodą dynamicznego budowania drzewa grafu

nr katalogowy: 56714

Wyszukiwanie minimalnych cykli fundamentalnych jest mocno związane z analizą układów elektronicznych i elektrycznych [8], jak również z ich testowaniem [6]. Podstawowym problemem przy wyznaczaniu takich cykli jest określenie odpowiedniego drzewa grafu. Zgodnie z zależnością Cayleya ilość możliwych drzew w grafie o k węzłach osi k k-2. Przeanalizowanie wszystkich możliwych drzew, a następnie sprawdzenie, który zbiór cykli fundamentalnych zawiera najmniejszą liczbę gałęzi przy grafach o dużej liczbie gałęzi, mogłoby trwać bardzo długo, a w niektórych przypadkach stać się nie możliwe. W literaturze znane są podejścia, w których wyszukuje się optymalne drzewo grafu poprzez zastosowanie algorytmów DFS(deep-first search) [1], BFS (breadth-first search) [3], and MS (mixed search) [2]. Interesująca modyfikacją algorytmu BFS z heurystycznym wyborem kolejnego wierzchołka została przedstawiona w [4]. Kolejne ciekawe podejście polegające na zamianie gałęzi drzewa z gałęziami łączącymi przedstawiono w [7]. Prezentowany algorytm nie opiera się na znajdowaniu optymalnego drzewa grafu a na dopasowaniu struktury drzewa do zestawu najmniejszych cykli. Proponowany algorytm Niech G = (V, E) będzie grafem nieskierowanym zawierającym n gałęzi i k węzłów. Definiujemy drzewo grafu jako podgraf T grafu G, który jest acyklicznym grafem zawierającym k-1 gałęzi zwanych gałęziami drzewa. Dołożenie dowolnej gałęzi ze zbioru G\T (gałęzie łączące) spowoduje, że pod-graf T będzie zawierał dokładnie jeden cykl. Cyklem fundamentalnym nazywamy zbiór cykli zawierających dokładnie jedną gałąź łączącą i dowolną liczbę gałęzi drzewa. Liczba cykli fundamentalnych wynosi n-k+1. Zdefiniowano także dwa dodatkowe pojęcia gałęzie charakterystyczne i gałęzie nadmiarowe. Gałęzie charakterystyczne to zbiór gałęzi unikalnych dla danego cyklu (nie występują w żadnym innym cyklu). Gałęzie nadmiarowe to zbiór gałęzi określonych jako różnica pomiędzy sumą gałęzi w wyznaczon[...]

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

Publikacja


e-Publikacja (format pdf) - nr 56714 "Generacja cykli fundament..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - e-zeszyt (pdf) 2010-12 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-12

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma