• 12:59 A.M.
  Almost!

Sunday, sunday, sunday. I spent Sunday reading about graphs. Graphs are a logical concept, a bunch of nodes (though they call them "vertices" in the book, probably cause "nodes" is a special term meaning vertices that are part of a rooted tree, which is a specific type of graph) and a list of node pairs, called "edges". I find the term "edges" unnecessarily exciting-sounding, especially since "edge" was such a hot word this past year or so (witness the renaming of part of downtown Seattle to "West Edge (anything but dull!)"). Anyway. So you've got a bunch of nodes and a bunch of connections between nodes. The way everyone visualizes this is as a bunch of dots with straight lines between them. The dots are the nodes, see? Nodes that are paired get a line between them. There are a few special conditions that give a graph more names. If the lines ever form a loop, you have a cyclic graph. Otherwise, it's acyclic. You can specify that the "edges" only exist in one direction between nodes. (You can draw a little arrowhead on them to represent this). This is a directed graph, or digraph. If you have lines tracing paths you can follow from node to node in order to get to any node, the graph is called "connected". Digraphs can be connected, too, but the requirement is more stringent. Since there are one way paths, if you can follow these links from node to node to get from any node to any other, it gets a more stringent-sounding name: "strongly connected".

I knew this stuff already, sorta, but the only way to really burn it in is to use it, or to try to teach it to someone. So that's what's with this. Ah yeah, graphs can also be related to other graphs with a few words. Two graphs that have the same number of nodes and the same relative pairings between nodes are called "isomorphic". A graph that uses some or all of the elements and edges of another is a "subgraph" of it. A couple more special kinds of graphs :a "complete" graph, which looks really messy if you draw it. Basicaly, it looks like obsessive connect the dots where you connect each dot directly to every single other dot, making a bunch of overlapping asterisk things until your picture looks like a spirograph. As many edges as possible, given a set of nodes. An acyclic, undirected, and connected graph is a "free tree" (no loops, one big constellation looking thing, no gaps), if it's not connected (i.e. there are nodes or groups of nodes not attached to each other at all) it's a "forest". A bunch of trees, cute huh?

There are a bunch of algorithms that use free trees, cause they have some useful properties. I'm getting tired, but I remember reading the spanning tree algorithm used to eliminate loops in bridged networks, which cause really, extremely bad and exponential traffic feedback. That was in the Radia Perlman book, I think. My understanding of this topic is pretty lame, so I'm just going to repeat it to everyone I know until they stop telling me which parts I have wrong. Sorry guys, I'm learning.