Graph (discrete mathematics)

A graph with six vertices and seven edges

In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line).^[1] Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person A can shake hands with a person B only if B also shakes hands with A. In contrast, if an edge from a person A to a person B means that A owes money to B, then this graph is directed, because owing money is not necessarily reciprocated.

Graphs are the basic subject studied by graph theory. The word "graph" was first used in this sense by J. J. Sylvester in 1878 due to a direct relation between mathematics and chemical structure (what he called a chemico-graphical image).^[2]^[3]

^ Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 19. ISBN 978-0-486-67870-2. Archived from the original on 5 May 2019. Retrieved 8 August 2012. A graph is an object consisting of two sets called its vertex set and its edge set.
^
See:
- J. J. Sylvester (February 7, 1878) "Chemistry and algebra", Archived 2023-02-04 at the Wayback Machine Nature, 17 : 284. doi:10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."
- J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices", Archived 2023-02-04 at the Wayback Machine American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. doi:10.2307/2369436. JSTOR 2369436. The term "graph" first appears in this paper on page 65.
^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 35. ISBN 978-1-58488-090-5. Archived from the original on 2023-02-04. Retrieved 2016-02-16.

[:0-1] Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 19. ISBN 978-0-486-67870-2. Archived from the original on 5 May 2019. Retrieved 8 August 2012. A graph is an object consisting of two sets called its vertex set and its edge set.

[2] See:
J. J. Sylvester (February 7, 1878) "Chemistry and algebra", Archived 2023-02-04 at the Wayback Machine Nature, 17 : 284. doi:10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."

J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices", Archived 2023-02-04 at the Wayback Machine American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. doi:10.2307/2369436. JSTOR 2369436. The term "graph" first appears in this paper on page 65.

[3] J. J. Sylvester (February 7, 1878) "Chemistry and algebra", Archived 2023-02-04 at the Wayback Machine Nature, 17 : 284. doi:10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."

[4] J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices", Archived 2023-02-04 at the Wayback Machine American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. doi:10.2307/2369436. JSTOR 2369436. The term "graph" first appears in this paper on page 65.

[3] Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 35. ISBN 978-1-58488-090-5. Archived from the original on 2023-02-04. Retrieved 2016-02-16.

[1]

[2]

[3]