Wednesday, February 20, 2013

Graphs

Graphs consist of vertices and edges. Vertices, also called nodes, can be pictured as the dots while edges are the lines connecting them. Graphs can be directed or undirected. Directed graphs have ordered pairs of endpoints (there is a head and tail) while undirected graphs do not.

Graphs are used ubiquitously. An obvious example is a map. The places are the vertices while the roads connecting them are the edges. Graphs can also be used to set precedence. That is, you can show which things are prerequisites for others, such as course prereqs.

A cut of a graph (V, E) is a partition of a graph into two non-empty sets A and B. Each set contains only the vertices that connect one vertex in the set to another in the set. Meanwhile, there are also edges connecting the vertices from set A to set B and vice versa.

In a graph with n nodes, you can either put them in set A, or set B. This gives us 2n cuts of the graph. However, since each set must be nonempty, it is actually 2n-2. Meanwhile, a crossing edge of a cut (A, B) is an edge whose endpoint is in A and head is in B.

A graph in one piece with n nodes must have at least n-1 edges. You start out with n distinct pieces and by adding an edge between two edges, you now have n-1 distinct pieces. To get to one piece, you need to do this n-1 times. This graph will have a maximum number of edges when every vertex is connected to every other vertex. Then there will n(n-1)/2 total edges because this is the number of ways of choosing 2 vertices from n of them.

If we let n be the # of vertices and m be the # of edges, we have that m is Omega(n) and O(n2). A graph is "sparse" if it is closer to the lower bound and "dense" if it is closer to the upper bound.

No comments:

Post a Comment