The minimum spanning tree cut property says: if a cut of a graph respects an edge set contained in some minimum spanning tree, a minimum-weight edge across that cut is safe to add to , meaning that some minimum spanning tree contains together with that edge. Respecting means no edge of crosses the cut. In particular, any lightest cut edge belongs to some minimum spanning tree; a uniquely lightest cut edge belongs to every minimum spanning tree.
For the exchange argument, take a minimum spanning tree containing . If it lacks the chosen edge , add to create its fundamental cycle. The remaining route between 's endpoints crosses the cut at some edge , with . Since the cut respects , . Replacing by preserves a spanning tree, retains , and cannot increase weight. Hence it is also minimum. Strict inequality would contradict minimality, which gives the unique-lightest assertion.
For an illustration, take a triangle with weights , , . Across the cut , is the unique lightest edge and must be in every minimum spanning tree. The minimum tree is , of weight . With tied light edges, the existence assertion need not mean that every minimum spanning tree contains the particular tied edge chosen.
Write each undirected edge with its smaller endpoint first. Kruskal's algorithm orders candidates first by weight and then lexicographically:Thus the requested addition order isand the minimum spanning tree has total weight . Five accepted edges connect all six vertices, so the remaining weight-four edges need not be scanned.
TakeIts longest strictly increasing subsequences have length two. A subsequence starting with can continue with or with , but cannot use both in increasing order; one starting at has only after it.
The specified greedy algorithm may choose the longest increasing subsequence . The remaining sequence is , which needs two singleton increasing subsequences. The algorithm then uses three subsequences in total.
However, and partition the original sequence into two increasing subsequences. One is impossible because the original sequence is not increasing. Hence two is optimal and the greedy choice is suboptimal. This establishes the counterexample to removing a longest increasing subsequence without relying on a tie-breaking rule: the problem asks for a longest choice that can fail.
Repeatedly remove vertices whose current degree is less than . Implement the deletions with an adjacency list, a queue and a degree counter for each active vertex:The requested subgraph is understood to be nonempty; otherwise an empty output would make the degree requirement vacuous or undefined. For , any nonempty input graph already qualifies.
active[v] = True for every v
count[v] = degree(v)
queue all v with count[v] < k
while the queue is nonempty:
remove v from the queue
if not active[v]: continue
active[v] = False
for each neighbour u of v:
if active[u]:
count[u] -= 1
if count[u] == k-1: queue u
return the subgraph induced by the active vertices,
or report failure if there is no active vertexThe correctness invariant is that every subgraph with minimum degree at least has all its vertices still active. Initially this is immediate. When is deleted, its degree in the whole active induced subgraph is less than . Any candidate subgraph on active vertices has at most that many incident edges at , so cannot contain it. Thus the invariant survives every deletion.
At termination, every active vertex has current degree at least , since every counter initially below the threshold or subsequently crossing it was queued. A nonempty surviving induced subgraph is therefore a valid answer. If none survives, the invariant rules out every possible answer, including ones omitting additional edges. The result is the k-core, with the k-core peeling invariant proving that deletion order cannot destroy a valid solution.
Each vertex is enqueued at most once when initially deficient or first crossing the threshold. Each adjacency list is scanned once when its vertex is deleted. The running time is , and storage is including the input graph.
Articles by others on the same topic
There are currently no matching articles.