Graph (discrete mathematics): Difference between revisions

Revision as of 10:32, 21 September 2024

Revision as of 20:15, 22 September 2024

Line 7:

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.

Graphs are the basic subject studied by graph theory. The word "graph" was first used in this sense by [[James Joseph Sylvester|J. J. Sylvester]] in 1878 due to a direct relation between mathematics and [[chemical structure]] (what he called a chemico-graphical image).<ref>See:

Graph theory is the theoretical foundation of [[network science]], which is the application of graph theory to various real-life domains of applications (social, biological, power grid networks...)<ref name=barabasi_network>{{cite book

| last1=Barabási

| first1=Albert-László

| last2=Pósfai

| first2=Márton

| author-link1=Albert-László Barabási

| date=2016

| title=Network science

| url=http://networksciencebook.com/

| ___location=Cambridge, United Kingdom

| publisher=Cambridge University Press

| page=456

| isbn=978-1-107-07626-6}}</ref>

Graphs are the basic subject studied by graph theory.

The origins of graph theory dates back to the mid 18th century with the [[Seven Bridges of Königsberg| bridges of Königsberg]] problem<ref name=barabasi_network></ref>, solved by [[Leonhard Euler]] using a mathematical proof that is considered to be the first to use the tools of graph theory<ref>{{cite journal

| last1 = Euler

| first1 = Leonhard

| author-link1=Leonhard Euler

| date = 1741

| title = Solutio problematis ad geometriam situs pertinentis

| url = https://archive.org/details/commentariiacade08impe/page/128/mode/2up

| journal = Commentarii academiae scientiarum Petropolitanae

| pages = 128-140

| access-date = 2024-09-21

}} English translation available at https://www.cantab.net/users/michael.behrend/repubs/maze_maths/pages/euler.html</ref>.

The word "graph" was first used in this sense by [[James Joseph Sylvester|J. J. Sylvester]] in 1878 due to a direct relation between mathematics and [[chemical structure]] (what he called a chemico-graphical image).<ref>See:

* J. J. Sylvester (February 7, 1878) [https://books.google.com/books?id=KcoKAAAAYAAJ&q=Sylvester&pg=PA284 "Chemistry and algebra"], {{Webarchive|url=https://web.archive.org/web/20230204142956/https://books.google.com/books?id=KcoKAAAAYAAJ&vq=Sylvester&pg=PA284 |date=2023-02-04 }} ''Nature'', ''17'' : 284. {{doi|10.1038/017284a0}}. From page 284: "Every invariant and covariant thus becomes expressible by a ''graph'' precisely identical with a Kekuléan diagram or chemicograph."

* J. J. Sylvester (1878) [https://books.google.com/books?id=1q0EAAAAYAAJ&pg=PA64 "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices"], {{Webarchive|url=https://web.archive.org/web/20230204142957/https://books.google.com/books?id=1q0EAAAAYAAJ&pg=PA64 |date=2023-02-04 }} ''American Journal of Mathematics, Pure and Applied'', ''1'' (1) : 64–90. {{doi|10.2307/2369436}}. {{JSTOR|2369436}}. The term "graph" first appears in this paper on page 65.</ref><ref>{{Cite book

Line 53 ⟶ 27:

== 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 61 ⟶ 33:

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 = http://math.uchicago.edu/~shmuel/Network-course-readings/Strogatz,%20Exploring%20complex%20networks.pdf

| 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

| arxiv = cond-mat/0106096

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