ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 12 May 2013 12:42:50 -0500Why does graph minor not work with multiple edges?http://ask.sagemath.org/question/10114/why-does-graph-minor-not-work-with-multiple-edges/When $H$ has multiple edges, and we ask whether it is a minor of another graph $G$, using the method:
G.minor(H)
the multiple edges are ignored. As a result, it can return `True`, when $H$ is not actually a minor of $G$.
Here is a small example of this incorrect behavior.
----------
Let $H$ be a triangle with a double edge, and let $G$ be a square. Clearly, $H$ is **not** a minor of $G$.
H = Graph()
H.allow_multiple_edges(True)
H.add_edges([(0,1), (0,1), (0,2), (1,2)])
G = Graph()
G.allow_multiple_edges(True)
G.add_edges([(0,1), (0,3), (1,2), (2,3)])
G.minor(H)
The output is:
{0: [0], 1: [1], 2: [2, 3]}
**Is there a work-around?**Sat, 11 May 2013 14:30:09 -0500http://ask.sagemath.org/question/10114/why-does-graph-minor-not-work-with-multiple-edges/Answer by Nathann for <p>When $H$ has multiple edges, and we ask whether it is a minor of another graph $G$, using the method:</p>
<pre><code>G.minor(H)
</code></pre>
<p>the multiple edges are ignored. As a result, it can return <code>True</code>, when $H$ is not actually a minor of $G$.</p>
<p>Here is a small example of this incorrect behavior.</p>
<hr/>
<p>Let $H$ be a triangle with a double edge, and let $G$ be a square. Clearly, $H$ is <strong>not</strong> a minor of $G$.</p>
<pre><code>H = Graph()
H.allow_multiple_edges(True)
H.add_edges([(0,1), (0,1), (0,2), (1,2)])
G = Graph()
G.allow_multiple_edges(True)
G.add_edges([(0,1), (0,3), (1,2), (2,3)])
G.minor(H)
</code></pre>
<p>The output is:</p>
<pre><code>{0: [0], 1: [1], 2: [2, 3]}
</code></pre>
<p><strong>Is there a work-around?</strong></p>
http://ask.sagemath.org/question/10114/why-does-graph-minor-not-work-with-multiple-edges/?answer=14913#post-id-14913I would say that if you split all edges of both graph by adding adding a new vertex b joined to a and c where there was an edge from a to c (this is a way to transform a graph with multiple edges into a normal graph), then checking that one is a minor of the other would give you the good definition.
I expect it to be slower, though.
And the explanation to your question "why aren't multiple edges considered by the ``minor`` function" is very easy and natural : why should it ? Things get implemented if somebody who cares about them takes the time to do it. Otherwise, they are not implemented.
NathannSun, 12 May 2013 11:06:14 -0500http://ask.sagemath.org/question/10114/why-does-graph-minor-not-work-with-multiple-edges/?answer=14913#post-id-14913Comment by Sammy Black for <p>I would say that if you split all edges of both graph by adding adding a new vertex b joined to a and c where there was an edge from a to c (this is a way to transform a graph with multiple edges into a normal graph), then checking that one is a minor of the other would give you the good definition.</p>
<p>I expect it to be slower, though.</p>
<p>And the explanation to your question "why aren't multiple edges considered by the <code>minor</code> function" is very easy and natural : why should it ? Things get implemented if somebody who cares about them takes the time to do it. Otherwise, they are not implemented.</p>
<p>Nathann</p>
http://ask.sagemath.org/question/10114/why-does-graph-minor-not-work-with-multiple-edges/?comment=17713#post-id-17713Yeah. I had already done that, but it was too slow. Thank you, though.Sun, 12 May 2013 12:42:50 -0500http://ask.sagemath.org/question/10114/why-does-graph-minor-not-work-with-multiple-edges/?comment=17713#post-id-17713