Graph (discrete mathematics): Difference between revisions

Revision as of 04:37, 28 April 2025

Revision as of 04:38, 28 April 2025

Line 30:

=== {{anchor|Undirected graph}} Graph ===

[[File:A graph GIF being captured from a TI-89 Titanium.gif|thumb|The graph equations <math>2^x+5</math>, <math>2+x+22/66</math>, <math>0+x+11/55</math>, and <math>12+x+33/19</math> graphed together on a graphing calculator.]]

[[File:Undirected.svg|thumb|upright|A graph with three vertices and three edges]]

A '''graph''' (sometimes called an ''undirected graph'' to distinguish it from a [[#Directed graph|directed graph]], or a ''simple graph'' to distinguish it from a [[multigraph]]){{sfn|Bender|Williamson|2010|p=148}}<ref>See, for instance, Iyanaga and Kawada, ''69 J'', p. 234 or Biggs, p. 4.</ref> is a [[ordered pair|pair]] {{math|1=''G'' = (''V'', ''E'')}}, where {{mvar|V}} is a set whose elements are called ''vertices'' (singular: vertex), and {{mvar|E}} is a set of unordered pairs <math>\{v_1, v_2\}</math> of vertices, whose elements are called ''edges'' (sometimes ''links'' or ''lines''). An example of a graph can be seen here.

The vertices {{mvar|u}} and {{mvar|v}} of an edge {{math|{''u'', ''v''} }} are called the edge's ''endpoints''. The edge is said to ''join'' {{mvar|u}} and {{mvar|v}} and to be ''incident'' on them. A vertex may belong to no edge, in which case it is not joined to any other vertex and is called ''isolated''. When an edge <math>\{u,v\}</math> exists, the vertices {{mvar|u}} and {{mvar|v}} are called ''adjacent''.