## 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!

## No comments:

## Post a Comment