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. 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.
A graph is a collection of
nodes and
edges connecting those nodes.
2. Nodes and edges
Computer trees and graphs are collections of nodes (vertices) and edges (arcs) connecting those nodes.
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. Names
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.
5. 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.
6. 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".
7. Undirected graphs
An undirected graph has no direction on each edge.
8. Directed graph
9. 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.
10. 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 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.
11. Comparison
12. End of page
A directed graph has a direction on each edge.
