## Вход

Забыли?

#### вход по аккаунту

код для вставкиСкачать
```Algorithms for Enumerating All
Spanning Trees of Undirected
and Weighted Graphs
Sanjiv Kapoor and H.Ramesh
Presented by
R97922102 李孟哲
R97922104 陳翰霖
R97922124 張仕明
Index
•
•
•
•
•
Introduction
Computation Tree
Algorithm 1
Algorithm 2
Algorithm 3
Introduction
• Spanning tree enumeration in undirected graphs
is an important issue in network and circuit
analysis
• In this paper, author enumerate spanning trees
by the computation tree
• Every node in the computation tree represent a
spanning tree
Algorithms Introduction
• We use this way to enumerate all the spanning tree on
undirected and weighted graphs.
• Algorithm 1
– O(N+V+E)
– O(V2E)
time
space
• Algorithm 2
– O(N+V+E)
– O(VE)
time
space
• Algorithm 3 (with sorting)
– O(NlogV+VE) time
– O(N+VE)
space
Spanning Tree
• The original graph G
Spanning Tree
• A Spanning tree of G
Spanning Tree
• add a edge to the tree
Spanning Tree
• get a cycle (fundamental cycle)
Spanning Tree
• remove a edge on the cycle
Spanning Tree
• get a new spanning tree of G
Spanning Tree
• From this cycle, we can obtain several spanning
trees.
Computation Tree
Computation tree
• First, we start off with a spanning tree T, and
generate all other spanning trees form T by
replacing edges in T by edges outside T
• For every node x, Sx is the spanning tree
corresponding to this node
• To ensure that each spanning tree is generated
exactly once, we use 2 edge set INx and OUTx
for every node x
IN and OUT
• The set INx consist of edges which are always
included in node x and it’s descendants
• The set OUTx consist of edges which are always
not included in node x and it’s descendants
• The IN and OUT set of the root are both empty
Computation tree
1
2
3
Arbitrary choose a spanning tree
4
1
5
2
3
5
4
In =[ ,
Out=[ ,
S =[ 1,2,4
]
]
]
Computation tree
1
2
3
5
1
4
2
3
5
4
In =[ ,
Out=[ ,
S =[ 1,2,4
]
]
]
Computation tree
1
2
3
1
4
2
5
3
5
In =[ ,
Out=[ ,
S =[ ,
] In =[ ,
] Out=[ ,
] S =[ ,
4
In =[ ,
Out=[ ,
S =[ 1,2,4
] In =[ ,
] Out=[ ,
] S =[ ,
]
]
]
] In =[ ,
] Out=[ ,
] S =[ ,
]
]
]
Computation tree
1
2
3
1
4
2
3
5
4
5
(-2,+5)
(-1,+5)
1
2
3
In =[ ,
Out=[ ,
S =[ 1,2,4
(-4,+5)
1
1
4
5
In =[ ,
Out=[ ,
S =[ 1,4,5
2
3
4
5
] In =[ ,
] Out=[ ,
] S =[ 2,4,5
]
]
]
2
3
4
5
] In =[ ,
] Out=[ ,
] S =[ 1,2,5
1
2
3
4
5
] In =[ ,
] Out=[ ,
] S =[ 1,2,4
]
]
]
Computation tree
1
2
3
1
4
2
3
5
4
5
(-2,+5)
(-1,+5)
1
2
3
In =[ ,
Out=[ ,
S =[ 1,2,4
(-4,+5)
1
1
4
5
In =[ ,
Out=[ 2,
S =[ 1,4,5
2
3
4
5
] In =[ ,
] Out=[ 1,
] S =[ 2,4,5
]
]
]
2
3
4
5
] In =[ ,
] Out=[ 4,
] S =[ 1,2,5
1
2
3
4
5
] In =[ ,
] Out=[ 5,
] S =[ 1,2,4
]
]
]
Computation tree
1
2
3
1
4
2
3
5
4
5
(-2,+5)
(-1,+5)
1
2
3
In =[ ,
Out=[ ,
S =[ 1,2,4
(-4,+5)
1
1
4
5
In =[ 5,
Out=[ 2,
S =[ 1,4,5
2
3
4
5
] In =[ 5,
] Out=[ 1,
] S =[ 2,4,5
]
]
]
2
3
4
5
] In =[ 5,
] Out=[ 4,
] S =[ 1,2,5
1
2
3
4
5
] In =[ ,
] Out=[ 5,
] S =[ 1,2,4
]
]
]
Computation tree
1
2
3
1
4
2
3
5
4
5
(-2,+5)
(-1,+5)
1
2
3
In =[ ,
Out=[ ,
S =[ 1,2,4
(-4,+5)
1
1
4
5
In =[ 5,
Out=[ 2,
S =[ 1,4,5
2
3
4
5
] In =[ 5,2,
] Out=[ 1,
] S =[ 2,4,5
]
]
]
2
3
5
4
1
2
3
4
5
] In =[ 5,2,1, ] In =[ ,
] Out=[ 4,
] Out=[ 5,
] S =[ 1,2,5 ] S =[ 1,2,4
]
]
]
Computation tree
1
2
3
5
1
4
2
3
5
4
In =[ ,
Out=[ 5,
S =[ 1,2,4
]
]
]
Computation tree
1
2
3
1
4
2
5
3
In =[ ,
Out=[ 5,
S =[ 1,2,4
4
5
(-1,+3)
(-2,+3)
1
2
3
]
]
]
1
4
5
In =[ ,
Out=[ 5,
S =[ 2,3,4
2
3
1
4
5
] In =[ ,
] Out=[ 5,
] S =[ 1,3,4
2
3
4
5
] In =[ ,
] Out=[ 5,3
] S =[ 1,2,4
]
]
]
Computation tree
1
2
3
1
4
2
5
3
In =[ ,
Out=[ 5,
S =[ 1,2,4
4
5
(-1,+3)
(-2,+3)
1
2
3
]
]
]
1
4
5
In =[ 3,
Out=[ 5,1
S =[ 2,3,4
2
3
1
4
5
] In =[ 1,3,
] Out=[ 5,2
] S =[ 1,3,4
2
3
4
5
] In =[ ,
] Out=[ 5,3
] S =[ 1,2,4
]
]
]
Computation tree
1
2
3
5
4
Computation tree C’(G)
Appear not only once
• The last son and its parent are the same
Another Computation tree C’(G)
G
C’(G)
1
C(G)
2
3
5
4
Another Computation tree C’(G)
Computation tree C(G)’s
property
• The son has zero or one edge differ from its
parent.
• The number of sons equals to the length of the
fundamental cycle
Computation tree C’(G)’s
property
• The son has one edge differ from its parent.
• The number of sons equals to the sum of the
length of all fundamental cycles
Lemma 1
• The computation tree has at its internal nodes
and leaves all the spanning trees of G
• [Proof]
• Following from induction and inclusion/exclusion
principle
• Let A be a node of computation tree C(G),
B1,...,Bk+1 be the son of A
A
B1
B2
…
…
e1
…
…
e2
Bk
Bk+1
…
f
ek
computation tree
• All spanning trees in B1,…, Bk contain edge f
• All spanning trees in Bk+1 don’t contain edge f
• The spanning trees as Bj ‘s descendants contain
edges e1,…,ej-1, but the edge ej
• e1,…,ek and f form a cycle
Algorithm 1
The Algorithm 1
Generate a random spanning
tree and initialize some data
structures.
…
Prepare and modify the
data structures.
Recursively call the algorithm.
Possible problem in algorithm
• How to maintain the IN , OUT, S ?
• How to find the fundamental cycles?
Possible problem in algorithm
• How to maintain the IN , OUT, S ?
– S is easy, just add a edge and delete another one.
– We use a data structure AG to maintain IN, OUT.
– We would choose edges from AG
– Initial: AG is the graph itself.
Possible problem in algorithm
– Modify AG
– Adding a edge into IN
– Contract the edge
1
1
2
2
3
3
Possible problem in algorithm
– Modify AG
– Add a edge into OUT
– Delete the edge
1
1
2
2
3
3
Modify the fundamental cycle
• After we exchange the edges, the fundamental
cycles of this tree would change
• We need to modify the fundamental cycles
e1
e1
e2
e2
e3
e2
f
f
f
e1
e3
e3
Modify the fundamental cycle
• Author uses the data structure C to maintain the
fundamental cycles
• C maintains the fundamental cycles
corresponding to the current tree
• There are 3 operations to construct computation
tree:
1. After deleting edge ei in AG, merge the fundamental
cycles contain ei
2. After contracting edge e in AG, contract edge e in C
3. Delete the nontree edge for the last son
Merge the fundamental cycles
• Use 4 pointer to modify the cycles
• This operation takes time proportional to the size
of resulting cycle
Contract edge in C
• This operation takes time proportional to
fundamental cycles containing the contracted
edge
Delete the nontree edge in C
• If the nontree edge is a part of a multiedge, then
do nothing
• else delete the fundamental cycle containing the
nontree edge
• This operation takes time proportional to the size
of its fundamental cycle
AG and C
• When some edge e is added to set IN:
– Contract e in AG and C
• When some edge e is added to set OUT:
– Delete e in AG and C
– Merge the fundamental cycles containing e
Lemma 1.2
• The algorithm done at each node A of C(G) is
O(|s(A)|+|g(A)|)
• Where s(A) is the set of sons of A in C(G), g(A)
is the set of sons in C’(G) of nodes in s(A)
Proof
• When replace tree edge ei by f , We need to
– Contract f in AG:
constant time
– merge fundamental cycles in C containing ei:
it takes time proportional to the sum size of resulting
cycle ( O(|g(A)|) )
– Contract ei in C:
it takes time proportional to the number of cycles
contain ei ( O(|g(A)|) )
– Contract ei in AG:
it takes time proportional to the number of multiedges
incident to the endpoints of ei ( O(|g(A)|) )
Proof
• Before operating the node is the last son, then
– Delete f in AG:
constant time
– Delete f in C:
time proportional to the size of its fundamental cycle
( O(s(A)) )
• Every node takes O(|s(A)|+|g(A)|) time
Theorem 1.3
• All spanning trees can be correctly generated in
O( N + V + E ) time by Algorithm 1
• [Proof]
– First, construct a spanning tree and setup it’s
data structure
• require O( V + E ) time
– Every node in computation tree C(G) takes
O(|s(A)|+|g(A)|) time
– Summing overall nodes of C(G) is O(N)
Theorem 1.4
• The space requirement of the spanning tree
enumeration Algorithm 1 is O( V2E )
• [Proof]
– At each node of C(G), take O( VE ) space
– The height of C’(G) is at most V
…
…
…
Algorithm 2
Algorithm 2
• We play two tricks to reduce the space
complexity from O(V2E) to O(VE)
– DFS tree
– Biconnected components
DFS tree
• The first spanning tree is generated by depth
first search.
– Nontree edges are back edges
• It is easy to find the fundamental cycle of the
depth first search tree
Why it’s easier at DFS tree
• To find a fundamental cycle, we just need to
trace the back edge
• We can reduce the space requirement since we
don’t have to maintain the fundamental cycle set
Maintaining the d.f.s invariant
• For a node A of C(G), SA is a d.f.s tree of GA
• Assume the vertices of SA are numbered by a
post-order traversal
1
root
8
7
2
3
6
5
4
Maintaining the d.f.s invariant
• Select the nontree edge whose upper endpoint
has the smallest number (upper is the endpoint
closer to the root)
• This edge is the replacement edge
1
root
8
7
2
3
6
5
4
Maintaining the d.f.s invariant
• Replace the tree in order of the post-order
number
• The new graph’s spanning tree is still a d.f.s tree
8
1
1
3
2
6
5
4
8
1
7
7
2
8
7
3
6
5
2
4
3
6
5
Biconnected components
Biconnected components
Biconnected components
Biconnected components
G2
G4
G1
G3
G5
• The red edges (bridges) must be chosen in each
spanning tree of G.
• Let nST(G) be the number of spanning trees in G.
• Then nST(G) = nST(G1)*nST(G2)*…..nST(Gn)
Biconnected components
• No change in time and space complexity in
analysis, but make the algorithm efficiency in
most cases.
Bridge
• When exchange edges, there may be some tree
edges which is not contained by any
fundamental cycles
– We call those edges bridges
– A bridge must be in this spanning tree
How to detect bridge
• Bridge only occurs on a fundamental cycle when
we exchange 2 edges
• Since x4 has a branch in current
e5
graph GA ,e4 is a bridge when
x4
we delete e3
e
4
e3
e2
e1
Lemma 2.1
• The work done at each node A of C(G) is
O(|s(A)|+|g(A)|)
• Proof :
– Removing bridges spends time in O(|s(A)|)
– Exchanging and contracting edges spend
O(g|A|)
Theorem 2.2
• All spanning tree can be correctly generated in
O( N + V + E ) time by Algorithm 2
• [Proof]
– First, we construct a spanning and setup it’s
data structure
• require O( V + E ) time
– Every node in computation tree C(G) takes
O(|s(A)|+|g(A)|) time
– Summing overall nodes of C(G) takes O(N)
time
Theorem 2.3
• The space requirement in Algorithm 2 is O( VE )
• [Proof]
– At each node of C(G), takes O( E ) space
– The height of C’(G) is at most V
…
…
…
Algorithm 3
Algorithm 3
• If we want to show all the spanning trees in
increasing order.
– Generate all the trees
– Sorting all the trees
O(N+V+E)
O(NlogN)
• Algorithm 3 generates sorted order in
O(NlogV+VE)time
Algorithm 3
• We create M queues, M = (V-1)(E-V+1)=O(VE)
and indexed by “exchange”
…
Algorithm 3
• We create a priority queue (heap) whose size is
equal to M=O(VE), and height is O(logVE)
• This heap maintains the first element of each
queue.
….
…
Algorithm 3
We sort all the nontree
edges by increasing order.
…
Algorithm 3
Minimum spanning tree
Output this one
…
Algorithm 3
edge and delete a tree edge.
…
We can generate the sons
Algorithm 3
…
Insert these nodes into
queue corresponding to
“exchange”
Algorithm 3
….
…
Get the minimum cost tree
from the heap.
Output this tree.
Do the algorithm again
Algorithm 3
…
Insert these nodes into
queues corresponding to
“exchange”
Algorithm 3
We choose the minimum cost tree from the heap again,
These blue vertices are possible to be chosen.
…
Analysis of algorithm 3
• [Lemma 3.1] Any child’s cost is larger than
parent’s.
Tree edges
= {e1,e2….en}
Nontree edges = {f1,f2…..fm}
…
This node’s cost must be larger
than( or equal to) parent’s.
Analysis of algorithm 3
• [Lemma 3.1] Any child’s cost is larger than
parent’s.
Tree edges
= {e1,e2….en}U{f1}
Nontree edges = {f2…..fm}
…
This node’s cost must be larger
than( or equal to) parent’s.
Analysis of algorithm 3
• [Lemma 3.2] The spanning trees enter the
queue for each of the exchanges in sorted order.
• Blue one is smaller than red one.
…
Analysis of algorithm 3
• Those two nodes are in queue, which implies their
parents have been output.
• Blue one is in front, because its parent outputs earlier
than dark red one.
• Because they have same
“exchange”, so
blue one < red one.
…
Analysis of algorithm 3
• Time complexity
–
–
–
–
–
–
Sorting edges: O(ElogE) time
Generation: O(N+V+E) time
O(VE) queues, N trees
Create a heap: O(VE) time.
One operation in heap: O(logVE) time
N operation in heap: O(NlogVE) time
– O(N logVE) + O(ElogE) + O(N+V+E) + O(VE)
=O(N logV3 + ElogE + N + V + E + VE)
=O( N logV + VE)
Analysis of algorithm 3
• Space complexity
– O(N) trees
– O(VE) queues
– O(N+VE) space
```
1/--страниц
Пожаловаться на содержимое документа