If so I guess that was an anticlimax but most people are more familiar with the Cartesian Plane where you've got each axis representing a variable and you want to see for what points a particular solution involving those variables holds true.
Well in this kind of graph you've only got two things to worry about: vertices and edges. Fun fact: why the hell is the plural of vertex 'vertices' I mean did anybody else see that e become an i. Anyway this is no time for linguistics (save that for the theory of computation)!
An edge is just a link or a 'relationship' between two vertices. They can be represented as {u,v} where u is the first vertex and v is the second. Whether this pair is ordered or not (i.e. {u,v}!={v,u}) depends on whether the graph is directed (ordered) or undirected (not-ordered). Undirected: if there's a road going from A to B then that same road is going from B to A. Directed: if John slaps Bill you can have an edge going from John to Bill (basically an arrow) and this will clearly be different to an edge going from Bill to John. Some graphs are 'mixed' which means some edges are directed and some are undirected.
As for graphs themselves, they can be a simple graph i.e. you'll never have more than one edge between two vertices and there aren't any loops, or a multigraph (which includes at least one of those features). By the way a loop is an edge connecting a vertex to itself (see image) whereas a link is an edge connecting two different vertices
They can also contain circuits (not sure if there's a single word that describes whether a graph contains circuits). A circuit is a path starting and ending at the same vertex with no edges or vertices crossed twice. The length of a circuit is the number of edges so the loop shown in the picture above is actually a circuit of length 1 and the circuit in the green circle has a length 2. I can count about seven other circuits in the picture but I might have double-counted (hey there's probably an algorithm to count how many circuits are in a graph, I think I'll do that in the next blog)
Edges can be weighted meaning they each have a value like length-of-road or pettiness-of-slap. This can be useful in finding the shortest path from A to B (in fact there's an algorithm for that too called Dijkstra's Algorithm which I'll handle in an upcoming blog).
Graphs can also be connected (there's a path from any one vertex to any other) or disconnected. Also a complete graph is one in which every pair of vertices has an edge between them e.g. a pentagram (we'll look more into pentagrams when we get into quantum computing. Not really.)
Any non-directed graph can be represented as G = (V,E) where V is the set of vertices and E is the set of edges which themselves are in the form of the non-ordered set {u,v}. A directed graph is basically the same but we use A instead of E and the edges in A will be ordered pairs rather than a non-ordered set. You could also define a mixed graph as G=(V,E,A) so E has the undirected edges and A has the directed ones. You could also add an element to the edges for the weight (w) but that means for undirected edges you'd need to keep the weight and the two vertex parameters separated e.g. ({u,v},w) or just {u,v,w} but this could make your algorithm a little trickier because instead of searching for a vertex by just going through the edges you'll need to specifically scan the first-two parameters.
Shamelessly ripped out of Wikipedia, here's a possible representation of a graph where G=(V,E)
V = {1, 2, 3, 4, 5, 6} E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6}}. 
Shamelessly ripped out of Wikipedia, here's a possible representation of a graph where G=(V,E)
Notice the actual placement of the vertices is arbitrary and that 6 could be moved down to the left of the 3 and the information is in no way compromised. Also notice the graph almost resembles a house which has fallen down. You better be writing this down.
Alright so a quick recap: graphs can be directed/undirected, simple/multigraph, weighted/unweighted, connected/disconnected and complete/incomplete. There are a few others but if we ever need to actually consider them then we can pat ourselves on the back for getting that deep in graph theory.
Next up, Dijkstra's Algorithm which is very cool and very clever (not surprising for an algorithm made by a Walter White lookalike.)
No comments:
Post a Comment