An Insight into Graphs - The Theory
(Page 2 of 4 )
Now, despite what you might think from the title, I will not embark on a deep adventure into the waters related to the theory shores. Following the quote starting this article, I will try to keep everything as simple as possible -- but not a bit simpler. This is the starting point of an article series, throughout which I will endeavor to explain the main points of interest of the graphs in use to this day.
I will try to present all of this from the point of view of the programmer, putting the mathematical parts in the background. So you'll see no mathematical theory proofs here, sorry. However, every presentation of an algorithm will be accompanied by some pure code snippet in the language of C (maybe mixed in with a little C++; nevertheless, there will be no object-oriented programming involved).
Regardless, we still need some minimal theoretical knowledge to understand the future articles, so here it goes, as compressed and straightforward as possible.
Every graph is composed of n vertexes (objects) and m edges (links between the objects). Edges that have the same starting point and ending point are called loop edges. You can see one in the graph below at vertex number 3. Multiple edges are the ones that have the same start and end, just like the two between vertexes one and five on the image below:
Simple graphs are those that contain no loop or multiple edges. Two vertexes are considered neighbors if an edge exists between them. For example, on the upper graph, vertex one and two are neighbors.
Isolated vertexes are vertexes that have no edge attached to them (vertex 6 is the correct illustration for this). Further, we can declare in and out degrees for vertexes. This will show how many edges come into (in) and go out from a specific vertex. For instance the vertex four has an in-degree of two (edges coming from vertices three and five) and out-degree of one (edge towards vertex five).
The in- and out-degree of a vertex will be equal if the graph's edges are not directed. A graph is k regular if every vertex has a degree equivalent to k. A walk is a consecutive sequence of edges between two points. If this sequence will not go through any of the vertexes twice, it is called a road. A circuit is a closed road (aka the start and the end are the same). If none of the edges stays twice in the succession, we're talking about a trail.
We can also define the complement of a graph, sub graph and complete graph, as the three images below illustrates.
--Graph A--
--Graph B --
--Graph C --
-Graph C -
A complete graph is one inside which there exists an edge between all of the vertexes, as in the Graph C. Graph A and Graph B are sub-graphs of Graph C, as we can obtain them by removing an arbitrary number of edges or vertices and the edges related to them. Graph A is the complement of Graph B and vice versa, because if we put the two together, they will provide a complete graph.
Inside a connected graph, there exists a road between any two of the points. Here the graph is not directed. In a strongly connected graph (which is also directed), there exists a road in both directions between any two vertices. Graphs inside which there are no circles are called forests. The ones that are also connected are simply called referred. Inside a tree, vertexes that have only one edge attached to them are leafs.
Next: Graphs and programming >>
More Code Examples Articles
More By Gabor Bernat
