Ask Your Question
0

Why does graph minor not work with multiple edges?

asked 2013-05-11 21:30:09 +0200

Sammy Black gravatar image

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?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2013-05-12 18:06:14 +0200

Nathann gravatar image

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.

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.

Nathann

edit flag offensive delete link more

Comments

Yeah. I had already done that, but it was too slow. Thank you, though.

Sammy Black gravatar imageSammy Black ( 2013-05-12 19:42:50 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-05-11 21:30:09 +0200

Seen: 298 times

Last updated: May 12 '13