Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Graph (discrete mathematics)
open-in-new
<p>In <a href="/facts/Discrete_mathematics/XdRUnzUL">discrete mathematics</a>, particularly in <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a graph is a structure consisting of a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called <i><a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a></i> (also called <i>nodes</i> or <i>points</i>) and each of the related pairs of vertices is called an <i>edge</i> (also called <i>link</i> or <i>line</i>). Typically, a graph is depicted in <a href="/facts/Diagrammatic_form/H0PKEUrI">diagrammatic form</a> as a set of dots or circles for the vertices, joined by lines or curves for the edges. </p><p>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 <i>A</i> can shake hands with a person <i>B</i> only if <i>B</i> also shakes hands with <i>A</i>. In contrast, if an edge from a person <i>A</i> to a person <i>B</i> means that <i>A</i> owes money to <i>B</i>, then this graph is directed, because owing money is not necessarily reciprocated. </p><p>Graphs are the basic subject studied by graph theory. The word "graph" was first used in this sense by <a href="/facts/James_Joseph_Sylvester/6NNurKJH">J. J. Sylvester</a> in 1878 due to a direct relation between mathematics and <a href="/facts/Chemical_structure/r5rT1Lj4">chemical structure</a> (what he called a chemico-graphical image). </p>