Re: What databases have taught me
Date: Sat, 24 Jun 2006 22:00:15 -0600
Marshall <marshall.spight_at_gmail.com> wrote:
> First I need to know what a "graph" is. (Don't laugh.)
> I think of the term as meaing "nodes and edges" but it
> appears for this paticular problem, we need faces as
> well. Yes/no? What are these faces? Are they collections
> of edges? Do the nodes have a position? If so, what
> must be the position of the nodes in the dual? If
> it's not specified, then how can we say the dual of
> the dual of the graph is the graph? Apparently it's okay
> to leave some things out, but it's not clear what.
> Then I need to know what "dual" is. Etc.
In case this helps, if you are planning to try this.
- You don't need faces; just a (unordered) nodes and edges.
- These are standard graphs (actually pseudographs... see below); position doesn't matter.
- To find a dual geometrically (the easiest to understand) by hand, you
would do the following:
- Draw the graph on a sheet of paper, without crossing any edges. If
you can't do that, then the graph doesn't have a dual.
- Identify all of the regions. Regions are the empty spaces on your paper, and are separated by edges from the graph. The blank space outside of where you've drawn the graph DOES count as a region, so there is always at least one. If the graph is a tree, for example, then there is only one region, so the dual only has one vertex.
- On a different sheet of paper for the dual graph, draw a node for each of those regions.
- Now draw the edges of the original graph onto the dual, but draw them between the dual vertices that represent the regions on each side of the edge. Note that some edges may actually have the same region on both sides, so that the edge becomes a loop (it connects a vertex to itself). As an extreme case, the dual of a tree is just a single node with a whole bunch of loops on it.
- Draw the graph on a sheet of paper, without crossing any edges. If you can't do that, then the graph doesn't have a dual.
And you're done. As a simple example, take this graph:
O ----------- O
| / | | A / | | / | | / | C | / B | | / |
O ----------- O
There are three regions (two inside, and then the "outside" region) which I've labelled A, B, and C. The dual therefore has three vertices. There are two edges that separate A from C (the top and left edges), so there are two edges from A to C in the dual. Following the same pattern, the dual has two edges from B to C, and one edge from A to B. The dual is:
A /|\ | | | \| | C | /| | | | | \|/ B
- Here is a definite possible subtlety. All graphs have duals, but all duals are not graphs. In fact, the dual constructed above is not a graph. Rather, it is a multigraph. More generally, we also need to allow loops as well, so a dual is a pseudo-graph.
Even more generally (though you can probably ignore this detail) duals are relationships between planar embeddings of graphs -- which means ways to draw the graph in the plane without crossing edges. So, if you did step 1 differently above, you might get a different dual. In practice, it is normal to say something like "a graph may have more than one dual", when it would probably be more correct to say "each planar embedding of a graph has one and only one dual, which is itself a planar embedding of a graph."
- Yes, there is always some way of finding the dual of a dual of a graph that can get you back to the original graph. However, since a graph has multiple duals, there may be other paths that don't do so. (Technically, the unique dual of the unique dual of a planar embedding of a graph does bring you reliably back to the original, but assuming you don't plan to store information about the planar embedding, that's not really relevant.)
Finally, I'm not convinced that merely guaranteeing that the graph is planar is sufficient to find the dual of a graph. What you need is some specific planar embedding of the graph. Otherwise, you'll need to calculate a planar embedding for step #1, and that's just as hard as proving that the graph is planar... i.e., knowing in advance that it's planar doesn't actually get you anywhere. I actually don't know offhand what a common way is to describe a planar embedding. Obviously you could ask for a list of the regions, which would make your job somewhat easier.
-- Chris Smith - Lead Software Developer / Technical Trainer MindIQ CorporationReceived on Sun Jun 25 2006 - 06:00:15 CEST