Czasopismo | PRZEGLĄD ELEKTROTECHNICZNY | Rocznik 2012 - zeszyt 1b

Partial Inverse Most Unbalanced Spanning Tree Problem

Qin WANG

nr katalogowy: 65416

Fig.1. Graph G and the forest 1 2 3 F  C C C 112 PRZEGLĄD ELEKTROTECHNICZNY (Electrical Review), ISSN 0033-2097, R. 88 NR 1b/2012 Suppose that there are k components of F denoted by Ci , i 1,..., k (see Fig. 1). Contract each component i C of F into a single vertex, denote the resulting graph by G' (see Fig. 2). Obviously, G' is connected since G is connected. Fig.2. Graph G' We have the following Theorem: Theorem 1 There exists an optimal solution w* such that for any edge ie E , *( ) { ( ) | } i j j w e  w e e E . Proof. It is easy to see that there exists an optimal solution (T*,w* ) such that min{ ( ) | } * ( ) j j i w e e E  w e  max{ ( ) | } j j w e e E for each ie E , for otherwise, we can modify *( ) i w e to min{ ( ) | } j j w e e E or max{ ( ) | } j j w e e E , then T* is still a most unbalanced spanning tree containing F and the total modification cost is minimum. Suppose that there exists *( ) i w e such that ( ) * ( ) ( ) l i k w e  w e  w e , where ( ) max{ ( ) | ( ) * ( )} l j j i w e  w e w e  w e and ( ) min{ ( ) | ( ) * ( )} k j j i w e  w e w e  w e . Then we can set *( ) ( ) i l w e  w e when ( ) * ( ) i i w e  w e and set *( ) ( ) i k w e  w e when ( ) * ( ) i i w e  w e . The total modification cost is still minimum. This completes the proof of Theorem 1. ■ Denote the maximum edge weight and the minimum edge weight of G under w be max{ ( ) | } GL j j w  w e e E and min{ ( ) | } GS j j w  w e e E , respectively. And denote {( , ) | ( , ) \ ( ), , , 1,..., } i j i j i j l I  v v v v  G E F v v  C l  k . By Theorem 1, for each pair ( , ) i j w w , i j w  w , let * GL j w  w , * GS i w  w . Then we modify the edge weights accord[...]

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

Publikacja


e-Publikacja (format pdf) - nr 65416 "Partial Inverse Most Unba..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


PRZEGLĄD ELEKTROTECHNICZNY - e-zeszyt (pdf) 2012-1b 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-1b

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma