Brief-introduction-to-graphs

One page introduction to Graphs.

A Graph is a collection of Dots and lines, connected in a manner that represents some physical or logical phenomenon. 

The Dots are also under some circumstances called either a Node or a Vertex (Vertices for more than one).

The line, or Edge is the action or thing that connects two Dots. If we were to represent the fact that on social media I am friends with you, but you are not friends with me, this is a directed edge.

If many people consider themselves friends with you, you have a high number of incoming lines, or in-degrees.

If you consider yourself to have lots of friends, you have a high out-degree. 

The Degree or total-degree of a node is the number of combined in and out degree connections. 

A path is either a finite or infinite sequence of edges which connect a sequence of vertices.

A walk is a sequence of vertices and edges where each edges endpoints are the preceding and following vertex in the sequence. A walk is closed if the first and last vertex is the same, and the walk is open if the first and last vertex is not the same. A walk that starts and ends at the same vertex, but has no other repeated vertices or edges is called a cycle.

A trail is a walk in which all edges are distinct. 

These concept of trails and walks will become important on this blog as we discuss Data Structure Graphs, and the application of Graph theory to the concepts of data modeling, and data architecture. 

By labeling edges consistently in certain large graphs, we are able to see some patterns that may be difficult otherwise. If we label the edges of my walk as edge_label := ‘doug’s walk’, and that walk is a->b->c->d->e in a graph full of vertices, then we can easily pull that particular walk out of the  overall image. 

To the right is a small graph with vertices named a-z. I created a number of walks throughout this graph, the source data for this image is walk_demo.csv at: https://github.com/dougneedham/Data-Structure-Graph-Book/blob/master/Data/Input

I uploaded the walk_demo.csv file to my Shiny Application at: DSG Shiny then selected dougs walk from the drop down. 

The master graph is displayed above, and the graph of my walk through these nodes is : 

This makes it easy to see the path I took through the crowd. If you download this file and experiment for yourself you can see some of the other paths described with the csv file.

Each of these terms or concepts are the foundation of much further discussion. I will be using these definitions as I explore more about Data Structure Graphs. 

Graph on!