Let G be ___________________ graph. A spanning tree T of G is a subgraph such that ___________________.___________________
Question:
Fill in the blanks from the following options:
(1) a directed
(1) an undirected
(2) T is a tree and V(G) = V(T)
(2) G[V(T)] is a tree.
(3) Every graph
(3) Every connected graph
(3) Not every connected graph
(4) T contains as few edges as possible.
(4) the edges of T have as little total weight as possible.
(5) is exactly one minimum spanning tree of G
(5) is exactly one minimum spanning tree of G (counting isomorphic trees as the same)
(5) could be multiple minimum spanning trees of G
Match the words to their definitions.
Matching ___________________
Perfect matching ___________________
Maximum matching ___________________
Bipartite graph ___________________
Bipartition of a graph G ___________________
Augmenting path of a graph G with respect to a matching ___________________
A. A graph whose vertex set can be partitioned into two sets A and B which each contain no edges
B. A collection of disjoint edges which is as large as possible
C. A collection of disjoint edges which covers every vertex in the graph
D. A pair (A, B) of disjoint sets with V(G) = A U B such that neither A nor B contain any edges of G.
E. A collection of disjoint edges
F. A path in G which alternates between matching and non-matching edges, and which begins and ends with unmatched vertices.
Fundamentals of Electric Circuits
ISBN: 9780073301150
3rd edition
Authors: Matthew Sadiku, Charles Alexander