Graph (discrete mathematics): Difference between revisions

Revision as of 17:05, 20 October 2024

Latest revision as of 20:11, 12 August 2025

(23 intermediate revisions by 18 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.

Line 30:

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

[[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'').

Line 50:

=== Directed graph ===

{{main|Directed graph}}

[[File:Directed.svg|thumb|upright|A directed graph with three vertices and four directed edges, where (the double arrow represents antwo edgedirected edges in eachopposite direction)directions]]

A '''directed graph''' or '''digraph''' is a graph in which edges have orientations.

Line 68:

To avoid ambiguity, this type of object may be called precisely a '''directed multigraph'''.

A ''[[Loop (graph theory)|loop]]'' is an edge that joins a vertex to itself. Directed graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex <math>x</math> to itself is the edge (for a directed simple graph) or is incident on (for a directed multigraph) <math>(x,x)</math> which is not in <math>\{(x,y) \mid (x,y) \in V^2 \;\textrm{ and }\; x \neq y \}</math>. So to allow loops the definitions must be expanded. For directed simple graphs, the definition of <math>E</math> should be modified to <math>E \subseteq \{(x,y) \mid (x,y) \in V^2 \}</math>. For directed multigraphs, the definition of <math>\phi</math> should be modified to <math>\phi : E \to \{(x,y) \mid (x,y) \in V^2 \}</math>. To avoid ambiguity, these types of objects may be called precisely a '''directed simple graph permitting loops''' and a '''directed multigraph permitting loops''' (or a ''[[Quiver (mathematics)|quiver]]'') respectively.

The edges of a directed simple graph permitting loops {{mvar|G}} is a [[Binary relation#Homogeneous relation|homogeneous relation]] ~ on the vertices of {{mvar|G}} that is called the ''adjacency relation'' of {{mvar|G}}. Specifically, for each edge {{math|(''x'', ''y'')}}, its endpoints {{mvar|x}} and {{mvar|y}} are said to be ''adjacent'' to one another, which is denoted {{math|''x'' ~ ''y''}}.

Line 74:

=== Mixed graph ===

{{main|Mixed graph}}

[[File:Example of simple mixed graph.jpg|thumb|upright|A mixed graph with three vertices, two directed edges, and an undirected edge.]]

A ''mixed graph'' is a graph in which some edges may be directed and some may be undirected. It is an ordered triple {{math|1=''G'' = (''V'', ''E'', ''A'')}} for a ''mixed simple graph'' and {{math|1=''G'' = (''V'', ''E'', ''A'', ''ϕ{{sub|E}}'', ''ϕ{{sub|A}}'')}} for a ''mixed multigraph'' with {{mvar|V}}, {{mvar|E}} (the undirected edges), {{mvar|A}} (the directed edges), {{mvar|ϕ{{sub|E}}}} and {{mvar|ϕ{{sub|A}}}} defined as above. Directed and undirected graphs are special cases.

=== Weighted graph ===

[[File:Weighted_network.svg|thumb|upright=1.2|A weighted graph with ten vertices and twelve edges]]

A ''weighted graph'' or a ''network''<ref>{{Citation | last=Strang | first=Gilbert | title=Linear Algebra and Its Applications | publisher=Brooks Cole | edition=4th | year=2005 | isbn=978-0-03-010567-8 }}</ref><ref>{{Citation | last=Lewis | first=John | title=Java Software Structures | publisher=Pearson | edition=4th | year=2013 | isbn=978-0133250121 | page=405 }}</ref> is a graph in which a number (the weight) is assigned to each edge.<ref>{{cite book|last1=Fletcher|first1=Peter|last2=Hoyle|first2=Hughes|last3=Patty|first3=C. Wayne|title=Foundations of Discrete Mathematics|year=1991|publisher=PWS-KENT Pub. Co.| ___location=Boston| isbn=978-0-53492-373-0| pages=463 | edition=International student|quote=A ''weighted graph'' is a graph in which a number ''w''(''e''), called its ''weight'', is assigned to each edge ''e''.}}</ref> Such weights might represent for example costs, lengths or capacities, depending on the problem at hand. Such graphs arise in many contexts, for example in [[shortest path problem]]s such as the [[traveling salesman problem]].

Line 93 ⟶ 95:

=== Complete graph ===

{{main|Complete graph}}

[[File:Complete graph K5.svg|thumb|125pxupright|A complete graph with five vertices and ten edges. Each vertex has an edge to every other vertex.]]

A ''complete graph'' is a graph in which each pair of vertices is joined by an edge. A complete graph contains all possible edges.

Line 156 ⟶ 158:

== Properties of graphs ==

{{see also|Glossary of graph theory|Graph property}}

Two edgesvertices of a graph are called ''adjacent'' if they share a common vertexedge. Two edgesvertices of a directed graph are called ''consecutive'' if the head of the first one is the tail of the second one. Similarly, two vertices are called ''adjacent'' if they share a common edge (''consecutive'' if the first one is the tail and the second one is the head of an edge), in which case the common edge is said to ''join'' the two vertices. An edge and a vertex on that edge are called ''incident''.

The graph with only one vertex and no edges is called the ''trivial graph''. A graph with only vertices and no edges is known as an ''edgeless graph''. The graph with no vertices and no edges is sometimes called the ''[[null graph]]'' or ''empty graph'', but the terminology is not consistent and not all mathematicians allow this object.

Line 162 ⟶ 164:

Normally, the vertices of a graph, by their nature as elements of a set, are distinguishable. This kind of graph may be called ''vertex-labeled''. However, for many questions it is better to treat vertices as indistinguishable. (Of course, the vertices may be still distinguishable by the properties of the graph itself, e.g., by the numbers of incident edges.) The same remarks apply to edges, so graphs with labeled edges are called ''edge-labeled''. Graphs with labels attached to edges or vertices are more generally designated as ''labeled''. Consequently, graphs in which vertices are indistinguishable and edges are indistinguishable are called ''unlabeled''. (In the literature, the term ''labeled'' may apply to other kinds of labeling, besides that which serves only to distinguish different vertices or edges.)

The [[category theory|category]] of alldirected graphsmultigraphs permitting loops is the [[comma category]] Set ↓ ''D'' where ''D'': Set → Set is the [[functor]] taking a set ''s'' to ''s'' × ''s''.

== Examples ==

Line 168 ⟶ 170:

* The diagram is a schematic representation of the graph with vertices <math>V = \{1, 2, 3, 4, 5, 6\}</math> and edges <math>E = \{\{1, 2\}, \{1, 5\}, \{2, 3\}, \{2, 5\}, \{3, 4\}, \{4, 5\}, \{4, 6\}\}.</math>

* In [[computer science]], directed graphs are used to represent knowledge (e.g., [[conceptual graph]]), [[finite -state machine]]s, and many other discrete structures.

* A [[binary relation]] ''R'' on a set ''X'' defines a directed graph. An element ''x'' of ''X'' is a direct predecessor of an element ''y'' of ''X'' if and only if ''xRy''.

* A directed graph can model information networks such as [[Twitter]], with one user following another.<ref name="snatwitter">{{Cite journal| volume = 3| issue = 1| last = Grandjean| first = Martin| title = A social network analysis of Twitter: Mapping the digital humanities community| journal = Cogent Arts & Humanities| date = 2016| pages = 1171458| doi = 10.1080/23311983.2016.1171458| url = https://serval.unil.ch/resource/serval:BIB_81C2C68B1DF5.P001/REF| doi-access = free| access-date = 2019-09-16| archive-date = 2021-03-02| archive-url = https://web.archive.org/web/20210302190117/https://serval.unil.ch/resource/serval:BIB_81C2C68B1DF5.P001/REF| url-status = live}}</ref><ref name="twitterwtf">Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh [http://dl.acm.org/citation.cfm?id=2488433 WTF: The who-to-follow system at Twitter] {{Webarchive|url=https://web.archive.org/web/20190712002903/http://dl.acm.org/citation.cfm?id=2488433 |date=2019-07-12 }}, ''Proceedings of the 22nd international conference on World Wide Web''. {{doi|10.1145/2488388.2488433}}.</ref>