Content deleted Content added
Added context on graph theory Tag: Reverted |
Added a paragraph on random graphs Tag: Reverted |
||
Line 53:
== Definitions ==
{{See also|Glossary of graph theory}}
Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related [[mathematical structure]]s.
Line 59 ⟶ 61:
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'').
A '''[[random graph]]''' is a graph where edges are distributed randomly between nodes (by opposition to [[regular graphs]])<ref name=strogatz_exploring>{{cite journal
| last1 = Strogatz
| first1 = Steven H.
| author-link1 = Steven Strogatz
| date = 2001
| title = Exploring complex networks
| url = https://www.nature.com/articles/35065725
| journal = Nature
| volume = 410
| issue = 6825
| pages = 268-276
| doi = 10.1038/35065725
| access-date = 2024-09-11
}}</ref>
<ref name=albert_statistical>{{cite journal
| last1 = Albert
| first1 = Réka
| last2 = Barabási
| first2 = Albert-László
| author-link1 = Réka Albert
| author-link2 = Albert-László Barabási
| date = 2002
| title = Statistical mechanics of complex networks
| url = https://link.aps.org/doi/10.1103/RevModPhys.74.47
| journal = Reviews of Modern Physics
| volume = 74
| issue = 1
| pages = 47-97
| doi = 10.1103/RevModPhys.74.47
| access-date = 2024-09-02
}}</ref>, first studied by [[Paul Erdős]] and [[Alfréd Rényi]] in the 1950s<ref name=erdos_>{{cite journal
| last1 = Erdős
| first1 = Paul
| last2 = Rényi
| first2 = Alfréd
| author-link1 = Paul Erdős
| author-link2 = Alfréd Rényi
| date = 1959
| title = On random graphs
| url = https://publi.math.unideb.hu/load_doi.php?pdoi=10_5486_PMD_1959_6_3_4_12
| journal = Publicationes Mathematicae
| volume = 6
| issue = 3-4
| pages = 290-297
| doi = 10.5486/PMD.1959.6.3-4.12
| access-date = 2024-04-26
}}</ref>.
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''.
| |||