close

Вход

Забыли?

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

код для вставкиСкачать
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
Add the smallest nontree
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/--страниц
Пожаловаться на содержимое документа