Definition of light edge in graph?

1 answer

Answer

1151011

2026-04-30 21:30

+ Follow

"An edge is light edge crossing the cut if its weight is minimum of any edge crossing the cut"

So lets say you have a graph G = (V, E), and you partition the vertices in V into to sets A and B= V-A (neither A or B are empty sets). Then the light edges (u, v) in E where either u or v is in A and the other is in B, and where none of the other edges in E that fill this criteria have a shorter weight.

ReportLike(0ShareFavorite

Copyright © 2026 eLLeNow.com All Rights Reserved.