This page provides some Graph Theory (GT) resources.
Good website about intro to GT.
- Graph theory at tutorialspoint.com
- Graph theory at mathworld
- Graph Data Structure And Algorithms at geeksforgeeks.org
- TBA
GT – Basics
-
-
- GT – Basic Properties (PDF)
- GT – Types of Graphs (PDF)
- Mathematics | Graph Theory Basics – Set 1 (PDF)
- Mathematics | Graph Theory Basics – Set 2 (PDF)
- TBA
-
G properties
- G properties at mathworld
-
-
- The eccentricity
of a graph vertex
in a connected graph
is the maximum graph distance between
and any other vertex
of
. For a disconnected graph, all vertices are defined to have infinite eccentricity (West 2000, p. 71).The maximum eccentricity is the graph diameter. The minimum graph eccentricity is called the graph radius.
-
- The radius of a graph is the minimum graph eccentricity of any graph vertex in a graph. A disconnected graph therefore has infinite radius (West 2000, p. 71).
- West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
-
- A disconnected graph has infinite diameter (West 2000, p. 71).
-
-
- A topological space decomposes into its connected components. The connectedness relation between two pairs of points satisfies transitivity, i.e., if
and
then
. Hence, being in the same component is an equivalence relation, and the equivalence classes are the connected components.Using pathwise-connectedness, the pathwise-connected component containing
is the set of all
pathwise-connected to
. That is, it is the set of
such that there is a continuous path from
to
.Technically speaking, in some topological spaces, pathwise-connected is not the same as connected. A subset
of
is connected if there is no way to write
with
and
disjoint open sets. Every topological space decomposes into a disjoint union
where the
are connected. The
are called the connected components of
.The connected components of a graph
are the set of largest subgraphs of
that are each connected.
- Bridges in a graph (with py code)
- An edge in an undirected connected graph is a bridge iff removing it disconnects the graph.For a disconnected undirected graph, definition is similar, a bridge is an edge removing which increases number of disconnected components.
-
- Graph Bridge
- A bridge of a connected graph is a graph edge whose removal disconnects the graph (Chartrand 1985, p. 45; Skiena 1990, p. 177). More generally, a bridge is an edge of a not-necessarily-connected graph
whose removal increases the number of components of
(Harary 1994, p. 26). An edge of a connected graph is a bridge iff it does not lie on any cycle.A bridge is also known as an isthmus, cut-edge, or cut arc.Every edge of a tree is a bridge. A connected cubic graph contains a bridge iff it contains an articulation vertex (Skiena 1990, p. 177), i.e., if it is not a biconnected graph.A graph containing one or more bridges is said to be a bridged graph, while a graph containing no bridges is called a bridgeless graph.
-
- The center of a graph
is the set of vertices of graph eccentricity equal to the graph radius (i.e., the set of central points). In the illustration below, center nodes are shown in red.
- The radius of a graph is the minimum eccentricity among all vertices in the graph, and a center
of a graph is a vertex with eccentricity equal to the radius. For a general graph, there may be several
centers and a center is not necessarily on a diameter.
-
- The periphery of a graph
is the subgraph of
induced by vertices that have graph eccentricities equal to the graph diameter.
- for example, for the following graph, its periphery is: [0, 1, 2, 9]
radius: 4 diameter: 7 eccentricity: {0: 7, 1: 7, 2: 7, 3: 6, 4: 5, 5: 4, 6: 4, 7: 5, 8: 6, 9: 7} center: [5, 6]
-
- The distance
between two vertices
and
of a finite graph is the minimum length of the paths connecting them (i.e., the length of a graph geodesic). If no such path exists (i.e., if the vertices lie in different connected components), then the distance is set equal to
. In a grid graph the distance between two vertices is the sum of the “vertical” and the “horizontal” distances (right figure below).The matrix
consisting of all distances from vertex
to vertex
is known as the all-pairs shortest path matrix, or more simply, the graph distance matrix.
-
- TBA
-
- GT Basic Properties at tutorialspoint.com
- The concept of “strongly connected” and “weakly connected” graphs are defined for directed graphs.
A digraph is strongly connected if every vertex is reachable from every other following the directions of the arcs (i.e., for every pair of distinct vertices u and v there exists a directed path from u to v).
A digraph is weakly connected if when considering it as an undirected graph it is connected (i.e., for every pair of distinct vertices u and v there exists an undirected path (potentially running opposite the direction on an edge) from u to v).
In both cases, it requires that the undirected graph be connected, however strongly connected requires a stronger condition. If a digraph is strongly connected, it is also weakly connected.
For example, the following graph is not a directed graph and so ought not get the label of “strongly” or “weakly” connected, but it is an example of a connected graph. As soon as you make your example into a directed graph, however, regardless of orientation on the edges, it will be weakly connected (and possibly strongly connected based on choices made).
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction between sparse and dense graphs is rather vague, and depends on the context.
where E is the number of edges and V is the number of vertices in the graph. The maximum number of edges for an undirected graph is |V|(|V|-1)/2, so the maximal density is 1 (for complete graphs) and the minimal density is 0 (Coleman & Moré 1983).
The density is 0 for a graph without edges and 1 for a complete graph. The density of multigraphs can be higher than 1.
Self loops are counted in the total number of edges so graphs with self loops can have density higher than 1.
Coleman, Thomas F.; Moré, Jorge J. (1983), “Estimation of sparse Jacobian matrices and graph coloring Problems”, SIAM Journal on Numerical Analysis, 20 (1): 187–209, doi:10.1137/0720013.
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.
The adjacency matrix, sometimes also called the connection matrix, of a simple labeled graph is a matrix with rows and columns labeled by graph vertices, with a 1 or 0 in position according to whether
and
are adjacent or not. For a simple graph with no self-loops, the adjacency matrix must have 0s on the diagonal. For an undirected graph, the adjacency matrix is symmetric.
The illustration below shows adjacency matrices for particular labelings of the claw graph, cycle graph , and complete graph
.
Since the labels of a graph may be permuted without changing the underlying graph being represented, there are in general multiple possible adjacency matrices for a given graph.
The eigenvalues of a graph are defined as the eigenvalues of its adjacency matrix. The set of eigenvalues of a graph is called a graph spectrum.
The largest eigenvalue absolute value in a graph is called the spectral radius of the graph, and the second smallest eigenvalue of the Laplacian matrix of a graph is called its algebraic connectivity.
The numerically second smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix of a graph is known as the algebraic connectivity of the graph. This eigenvalue is greater than 0 iff
is a connected graph.
The spectral radius of a finite graph is defined as the largest absolute value of its graph spectrum, i.e., the largest absolute value of the graph eigenvalues (eigenvalues of the adjacency matrix).
The set of graph eigenvalues of the adjacency matrix is called the spectrum of the graph. (But note that in physics, the eigenvalues of the Laplacian matrix of a graph are sometimes known as the graph’s spectrum.) The spectrum of a graph with
-fold degenerate
http://mathworld.wolfram.com/topics/GraphTheory.html
The vertex connectivity of a graph
is the minimum number of nodes whose deletion disconnects it. Vertex connectivity is sometimes called “point connectivity” or simply “connectivity.”
A graph with is said to be connected, a graph with
is said to be biconnected (Skiena 1990, p. 177), and in general, a graph with vertex connectivity
is said to be
-connected.
A block is a maximal biconnected subgraph of a given graph . In the illustration below, the blocks are
,
, and
.
If a graph is biconnected, then
itself is called a block (Harary 1994, p. 26) or a biconnected graph (Skiena 1990, p. 175).
Skiena, S. “Biconnected Components.” §5.1.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 175-177, 1990.
The coarseness of a graph
is the maximum number of edge-disjoint nonplanar subgraphs contained in a given graph
. The coarseness of a planar graph
is therefore
.
The number of nodes in a graph is called its order.
A graph is planar if it can be drawn in a plane without graph edges crossing (i.e., it has graph crossing number 0). The number of planar graphs with , 2, … nodes are 1, 2, 4, 11, 33, 142, 822, 6966, 79853, … (OEIS A005470; Wilson 1975, p. 162), the first few of which are illustrated above.
- TBA
GT – Matchings
Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.
- GT matching at tutorialspoint.com (PDF)
-
-
-
- Matching
- Maximal Matching
- Maximum Matching
- Perfect Matching
-
-
- Matching (GT) at geeksforgeeks (PDF)
- Matchings at mathworld
- TBA at mathworld
References and further reading list:
- Graph Theory at mathworld.wolfram.com
- NetworkX resources
- (Deep) machine learning on graphs
- A note on Eccentricities, diameters, and radii∗ (by Bang Ye Wu and Kun–Mao Chao) — PDF
- Graph measurements: length, distance, diameter, eccentricity, radius, center — PDF
- Eccentricity, Center, Radius, Diameter – FAU Math — PDF
- Graph Theory at MathWorld
- Math Insight
- Discrete Mathematics: An Open Introduction, 3rd edition
- Graph Theory Glossary (PDF)
- Introduction to Graph Theory (PDF)
- Graph Theory Bascis (PDF or PDF copy)