Send
Close Add comments:
(status displays here)
Got it! This site "creationpie.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.
Graphs and graph theory
1. Charts and graphs
Some people confuse
charts which are graphical depictions of data and data relationships with
graphs which are a set of nodes and edges connecting nodes.
2. Graphs and graph theory
Graph theory is a mathematical and computer science area that has to do with the properties and algorithms for processing a graph of nodes (or vertices) and edges (or arcs) connecting those nodes (vertices).
The size and importance of nodes and edges may or may not be displayed in a diagram of the graph because nodes can be placed anywhere. It is the type of node and the relationships between nodes that is important.
Computer trees and graphs are collections of nodes (vertices) and edges (arcs) connecting those nodes.
Mathematicians often call nodes
vertices and edges
arcs.
Computer scientists often like when names (as in variables) have the same number of letters. The words "
node" and "
edge" each have four letters. And the letter "
v" is often used for "
variables" so it is already taken as an abbreviation.
3. Facebook graph
The Facebook graph is a data structure of users and who they know, are friends with, etc.
The Facebook graph is huge, with hundreds of millions of nodes (people, groups, organizations, etc.) and billions of edges connecting those nodes.
4. Undirected edge
An undirected edge (arc) connects two nodes (vertices) without a direction on the edge (arc).
In the Facebook graph, the "
friend" relation goes both ways. Both sides need to agree or accept that relation. It is an undirected edge in the Facebook graph.
5. Directed edge
A directed edge (arc) connects two nodes (vertices) with a direction on the edge (arc).
In the Facebook graph, a "
like" is a relation that goes one way. It is a directed edge. What is "
liked" does not have to return the "
like".
6. Undirected graphs
An undirected graph has no direction on each edge.
7. Directed graph
8. Tree structures
A connected graph with no cycles (directed or undirected) can always be represented as a tree structure. In such cases, one node can be designated as the root node. All other nodes with only one edge connection are leaf nodes.
9. Comparison and cross edges
Note that cross-edges in what looks like a tree is what is called a
DAG.
A common type of
DAG structure would be your family tree.
What you might think of as a tree going back in time is actually a
DAG since, at some point, some of your ancestors would be the same person. This may be easier to visualize from the other end where, at some point, some descendant of an earlier ancestor would marry and have children to another descendant of an earlier ancestor.
10. Family trees
A
tree is a
connected graph with
no cycles.
Each level of a tree increases the number of
nodes in the tree.
There are more and more ancestors in the family tree as one goes back in time. How then does one go back to just two people (i.e., Adam and Eve) at the start?
Geometric increase has to do with integer numbers (counts) such as 1, 2, 4, 8, 16, etc.
Exponential increase has to do with real numbers (measures) such as 1.2, 2.4, 4.8, etc.
11. A family tree is not a tree
The population
doubles at each generation. That is,
2,
4,
8,
16, etc. This is a geometric increase.
In computer science terms, the family tree is
not a (pure)
tree structure. A
tree is a
connected graph with
no cycles. The family tree structure is what is called a
DAG. The corresponding
unconnected graph has cycles.
12. A family tree is not a tree
Simple (degenerate) view (where siblings marry siblings):
1. The first generation has two boys and two girls. They marry each other.
2. The second generation has two boys and two girls. They marry each other.
3. The third generation has two boys and two girls. They marry each other.
Note:
The population doubling in each generation as 2, 4, 8, 16, etc.
Going back, one has one set of parents, one set of grandparents, one set of great-grandparents, all the way to the original two (e.g., Adam and Eve).
... more to be added ...
13. End of page
A directed graph has a direction on each edge. A DAG (Directed Acyclic Graph) is a directed graph which has no cycles.
