Graphs

This article page is a stub, please help by expanding it.

“Is the null-graph a pointless concept?”—Frank Harary, Ronald C. Read.

“(...) the only good null graph is a dead null graph.”—Brendan McKay.

Graphs are mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context is a pair, i.e. ordered 2-tuple, consisting of a collection of "vertices" (or "nodes") and a collection of "edges" that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another.

Graphs, with applications in mathematics and computer science, the objects of study in graph theory, is one of the most important branches in discrete mathematics.

Undirected graphs

Undirected graphs are graphs where there is no distinction between the two vertices associated with each edge, i.e. edges have no orientation.

Example of an undirected graph

G = (V, E )

, where

V

is a set of vertices and

E

is a set of edges (multisets with two vertices, or sets with two distinct vertices if no loops are allowed):

V = {1, 2, 3, 4, 5, 6}

E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 3}, {3, 4}, {4, 5}, {4, 6}}

Directed graphs

Directed graphs (digraphs) are graphs where we distinguish between the two vertices associated with each edge, i.e. edges are oriented.

Example of a directed graph

G = (V, E )

, where

V

is a set of vertices and

E

is a set of edges (pairs, i.e. ordered 2-tuples, with two vertices, distinct if no loops are allowed):

V = {1, 2, 3, 4, 5, 6}

E = {(1, 2), (1, 5), (2, 3), (2, 5), (3, 3), (3, 4), (4, 3), (4, 5), (4, 6), (5, 1)}

Directed acyclic graphs

Directed acyclic graphs (DAGs) are directed graphs without cycles.

Graph properties

Some graph properties are

• Degree
  • Minimum degree
  • Average degree
  • Maximum degree
• Number of edges
• Number of vertices

External links

• Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur, Hadrien Mélot, House of Graphs: a database of interesting graphs, arXiv:1204.3549, 2012.
• G. Brinkmann, J. Goedgebeur, H. Mélot and K. Coolsaet, House of Graphs: a database of interesting graphs, Discrete Applied Mathematics, 161:311-314, 2013. Available at http://hog.grinvin.org