This site is supported by donations to The OEIS Foundation.
Graphs
- “Is the null-graph a pointless concept?”—Frank Harary, Ronald C. Read.[1][2][3]
- “(...) the only good null graph is a dead null graph.”—Brendan McKay.[2]
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.
Contents
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 graphG = (V, E ) |
V |
E |
-
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 graphG = (V, E ) |
V |
E |
-
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
Notes
- ↑ F. Harary and R. C. Read, "Is the null-graph a pointless concept?," pp. 37– 44 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
- ↑ 2.0 2.1 Weisstein, Eric W., Null Graph, from MathWorld—A Wolfram Web Resource.
- ↑ Weisstein, Eric W., Empty Graph, from MathWorld—A Wolfram Web Resource.
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