Another Word For It Patrick Durusau on Topic Maps and Semantic Diversity

December 28, 2012

Graph Contraction and Minors [Merging by Another Name?]

Filed under: Graphs,Merging — Patrick Durusau @ 7:00 pm

Graph Contraction and Minors by Mark C. Chu-Carroll.

From the post:

Another useful concept in simple graph theory is *contraction* and its result, *minors* of graphs. The idea is that there are several ways of simplifying a graph in order to study its properties: cutting edges, removing vertices, and decomposing a graph are all methods we’ve seen before. Contraction is a different technique that works by *merging* vertices, rather than removing them.

Here’s how contraction works. Suppose you have a graph G. Pick a pair of vertices v and w which are adjacent in G. You can create a graph G’ which is a contraction of G by replacing v and w with a *single* vertex, and taking any edge in G which is incident on either v or w, and making it incident on the newly contracted node.

i-3ac4f4a9649d81b95317acdc3576e890-contractor.jpg

Not quite merging in the topic map sense because edges between vertexes are the basis for “merging.”

Instead of on the basis of properties of subjects the vertexes represent.

Still, deeply intriguing work.

This post was first published in July of 2007, so recent it’s not.

More resources you would suggest?

I first saw this in a tweet by Marko A. Rodriguez.

No Comments

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress