A graph is a collection of vertices or nodes, connected by edges. A tree is technically a special type of graph.
Formally, a graph is a set of pairs of edges and vertices such as, where G is a graph, V is vertices and E is the edges.
V is a set of vertices (representing potentially anything):
E is a set of edges {e1, e2, … en} where each ei is a pair of vertices ei is in V x V
Terminology
Directed
If each edge is an ordered pair that is not commutative, i.e
then the graph is directed, otherwise the graph is undirected. Directed graphs are sometimes alternatively called digraphs.
Simple
A graph is simple if it does not allow for self-loops and multiple edges to the same vertices.
Subgraph
A subgraph is a portion of the original graph. Importantly, you cannot have hanging edges where an edge doesn’t connect to anything.
Degree
The degree of a graph is the amount of edges in connection with a vertex. Degrees are only relative to a vertex, the degree of a graph is not standard terminology.
Path
A sequence of vertices connected by edges. A simple path is a special type of path with no repeated vertices.
Cycle
A cycle in a graph is a path with the same start and end vertex.
Weighted graphs
A weighted graph is a graph where the edges are weighted in some way or another, for example in CSPC 110 we effectively had the travelling salesman problem with the edges of a graph having distances being the cost in between nodes on a graph.
Complete graph
A complete graph is a graph where all vertices are connected with each other. This can for example be represented by a pentagram. In this case, the amount of edges, and in general the maximum amount of edges for a certain graph is (where n is the amount of vertices):
If the graph is directed, half that if it is undirected.
Connected
An undirected graph is connected if there is a path between any two vertices.
Properties
A connected graph has at minimum n - 1 edges.
Strongly connected
Directed graphs are strongly connected if there is a directed path from any vertex to any other.
Applications
Graphs are generally used for storing and computing things that are “networks” by nature. Things like road networks, airline flights, connections etc. Compilers are also an example. Where call graphs are which functions call which others. Graphic meshes are also another example of a graph.
Exam scheduling is an example of an np-complete problem that is solvable with graphs, or the famous travelling salesman.
Handshaking theorem
The handshaking lemma is the statement that in every finite undirected graph, the number of vertices that touch an odd number of edges is even. This is because the sum of the degrees equals twice the number of edges. Since this is the case, the number of vertices that have an odd degree must be even, since the product of an even an odd number is even.
Graph density
A sparse graph has O(|V|) edges, while a dense graph has Theta(|V^2|) edges.
For example the above is a sparse graph.
While this would be considered a dense graph, though it seems exactly what defines a sparse as opposed to a dense graph is not always agreed upon, though asymptotically it is generally defined as above.
Properties
The sum of all degrees in a graph is equal to twice the number of edges. Formally, where m is the amount of edges: