Graph (discrete mathematics): Difference between revisions

Revision as of 21:37, 19 July 2025

Latest revision as of 20:11, 12 August 2025

(2 intermediate revisions by 2 users not shown)

Line 3:

[[File:6n-graf.svg|thumb|A graph with six vertices and seven edges]]

In [[discrete mathematics]], particularly in [[graph theory]], a '''graph''' is a structure consisting of a [[Set (mathematics)|set]] of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called ''[[Vertex (graph theory)|vertices]]'' (also called ''nodes'' or ''points'') and each of the related pairs of vertices is called an ''edge'' (also called ''link'' or ''line'').<ref name=":0">{{cite book|last=Trudeau|first=Richard J.|title=Introduction to Graph Theory|year=1993|publisher=Dover Pub.|___location=New York|isbn=978-0-486-67870-2|pages=19|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|access-date=8 August 2012|quote=A graph is an object consisting of two sets called its ''vertex set'' and its ''edge set''.|archive-date=5 May 2019|archive-url=https://web.archive.org/web/20190505192352/http://store.doverpublications.com/0486678709.html|url-status=live}}</ref> 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.