ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 17 Aug 2021 05:22:35 +0200Nontrivial edge cutshttps://ask.sagemath.org/question/58472/nontrivial-edge-cuts/Hi there,
I wonder how I can produce nontrivial edge cuts in a graph. An edge cut is *trivial* is all its edges are incident with one vertex.
The commands edge_cut and edge_connectivity tend to produce trivial cuts, even if nontrivial ones exist.
I look forward to your answer.
Regards,
GuillermoSun, 15 Aug 2021 07:19:36 +0200https://ask.sagemath.org/question/58472/nontrivial-edge-cuts/Answer by tmonteil for <p>Hi there,</p>
<p>I wonder how I can produce nontrivial edge cuts in a graph. An edge cut is <em>trivial</em> is all its edges are incident with one vertex. </p>
<p>The commands edge_cut and edge_connectivity tend to produce trivial cuts, even if nontrivial ones exist. </p>
<p>I look forward to your answer.</p>
<p>Regards,
Guillermo</p>
https://ask.sagemath.org/question/58472/nontrivial-edge-cuts/?answer=58478#post-id-58478You might have more chance by using the 'LP' algorithm that does not take care of the geometry of the graph (but we need your actual graph to check).
Another trick would be to add a very small amount of positive weight to the edges adjacent to the source and sink vertices ("very small" means that the ordering between two unequal cuts will not be modified, but the ordering between trivial cuts and other cuts with the same value will change).
Sun, 15 Aug 2021 18:00:56 +0200https://ask.sagemath.org/question/58472/nontrivial-edge-cuts/?answer=58478#post-id-58478Comment by guillermo for <p>You might have more chance by using the 'LP' algorithm that does not take care of the geometry of the graph (but we need your actual graph to check).</p>
<p>Another trick would be to add a very small amount of positive weight to the edges adjacent to the source and sink vertices ("very small" means that the ordering between two unequal cuts will not be modified, but the ordering between trivial cuts and other cuts with the same value will change).</p>
https://ask.sagemath.org/question/58472/nontrivial-edge-cuts/?comment=58490#post-id-58490Hi @tmontell,
Thank you for your comments. But I need to process a large number of graphs, and so this is impractical.
Regards,
GuillermoTue, 17 Aug 2021 05:22:35 +0200https://ask.sagemath.org/question/58472/nontrivial-edge-cuts/?comment=58490#post-id-58490