A Vertex of a Graph is a connection point.
A Graph has a set of Vertices, usually shown as V = {v1, v2, ..., vn}
V = {A, B, C} or V = {1, 2, ... N}
The number of Vertices in a graph is |V|
but is somtimes written in equations as just V.
A Vertex may have no connections, one connection or many connections.
A vertex may have any number of properties such as a name or a color.
An Edge in a graph is a connection between vertices.
Given vertices v1 and v2 in a Graph,
the edge between them may be written
as (v1,v2) or sometimes [v1,v2].
A Graph has a set of Edges usually denoted E.
E = {(v1,v2), (v2,v3)}
The number of Edges in a graph is |E|
but is somtimes written in equations as just E.
A Graph is called Undirected if the edges have no implied direction.
(v1,v2) is the same as (v2,v1), the edge just connects v1 to v2.
A Graph is called Directed if the edges have a direction.
(v1,v2) means an edge starting at v1 and goint to v2.
(v1,v2) is NOT the same as (v2,v1).
A Weighted Graph has edges with an additional property, a weight.
Weights may be integers, real numbers, gallons per minute or
any type of quantity. (v1,v2,10GPM) would indicate an Edge from
vertex v1 to v2 with a flow of 10 gallons per minute. There are
special cases that may not allow zero or negative weights.
An Edge Colored Graph has edges with an additional property,
a color. In general, an Edge can have many properties that
depend on what the graph represents. (v1,v2,10GPM,green)
A general graph may have a self loop which is an edge that goes
from a vertex to itself, e.g. (v3,v3).
A multi-graph may have more than one edge between the same
pair of vertices, e.g. E = {(v1,v2), (v1,v2), (v2,v3)}
Note: in a Directed Graph (v1,v2) and (v2,v1) is not a
multi-graph, just two edges going different directions.
In an Undirected Graph sometimes (v1,v2) and (v2,v1) may
be included even though they are redundant and the Graph
may not be considered a multi-graph.
A cutset (one word) is a set of edges, which when removed,
disconnect source vertices from sink vertices.
The Edge Connectivity of an Undirected Graph is the minimum
number of edges that must be removed to "disconnect the graph."
This is a number. A value of zero means the given graph has at
least one pair of vertices x, y in V such that there is no
path connecting x and y.
A Graph is a set of Vertices and a set of Edges. G = (V, E)
There seems to be no standard definition for the properties
of a Graph when it is just called a "graph" yet many types
of graphs are defined by a sequence of qualifiers:
Directed - the edges have a direction, usually drawn with an
arrow head at one end. A DAG, Directed Acyclic Graph is a
restricted case with no cycles (no loops following direction
of edges.)
Undirected - usually the default if nothing else said. The edges
do not have direction.
Acyclic - no cycles, there is no Path that includes at least
one edge that can return to the starting vertex.
Planar - The Graph can be drawn on a plane (paper, flat surface)
with no Edge crossing another Edge. Note: "can be drawn" but it
may be drawn with edges crossing.
Non planar - A Graph that is impossible to draw on a plane
without an Edge crossing.
Dense - |E| is close to |V|**2
close is usually not defined precisely but for
algorithms it means |E| is O(|V|**2)
Connected - There are no unconnected verticies and no isolated
groups of vertices. In an Undirected Graph there is
a Path from every vertex to every other vertex.
Fully connected - every vertex has an edge to every other vertex.
Clique - Fully connected component - a subset of the vertices of
a Graph that are fully connected.
Strongly connected - For a Directed Graph, for every pair of vertices
x, y in V a path from x to y implies a path
from y to x. (Use DFS to check)
Tree - a restricted form of a graph where one vertex is called
the root and all verticies have a Path to the root and
the graph is undirected and acyclic.
Bipartite - a Graph with a set of vertices that can be divided
into exactly two non empty subsets such that no edge
connects two vertices within a subset and every vertex
in one subset has at least one Edge to a vertex in
the other subset.
Definition Data Structure AlgorithmTopological Sort of a DAG.
Given a graph G = (V, E) that is directed and acyclic, list the vertices in an order such that for every edge (u,v) u is listed before v. Algorithm: Run DFS on the graph putting finished vertices on the front of the list.
Last updated 1/7/99