Content deleted Content added
Undid revision 1256325482 by Kkddkkdd (talk) this is true but it is an extremely minor detail and does not merit this prominent positon in the introduction |
Undid revision 1305550508 by EulerianTrail (talk) the sentence doesn't make sense with "simply" moved like that; the second form is the simple one |
||
| (14 intermediate revisions by 14 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
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 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
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 158:
== Properties of graphs ==
{{see also|Glossary of graph theory|Graph property}}
Two
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 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
== Examples ==
Line 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
* 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>
| |||