Katana VentraIP

Graph (discrete mathematics)

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects are represented by abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line).[1] 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.

This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For other uses, see Graph (disambiguation).

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 J. J. Sylvester in 1878 due to a direct relation between mathematics and chemical structure (what he called a chemico-graphical image).[2][3]

V, a of vertices (also called nodes or points);

set

E, a of edges (also called directed edges, directed links, directed lines, arrows, or arcs), which are ordered pairs of distinct vertices: .

set

Types of graphs[edit]

Oriented graph[edit]

One definition of an oriented graph is that it is a directed graph in which at most one of (x, y) and (y, x) may be edges of the graph. That is, it is a directed graph that can be formed as an orientation of an undirected (simple) graph.


Some authors use "oriented graph" to mean the same as "directed graph". Some authors use "oriented graph" to mean any orientation of a given undirected graph or multigraph.

The diagram is a schematic representation of the graph with vertices and edges

In , directed graphs are used to represent knowledge (e.g., conceptual graph), finite state machines, and many other discrete structures.

computer science

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

binary relation

A directed graph can model information networks such as , with one user following another.[12][13]

Twitter

Particularly regular examples of directed graphs are given by the of finitely-generated groups, as well as Schreier coset graphs

Cayley graphs

In , every small category has an underlying directed multigraph whose vertices are the objects of the category, and whose edges are the arrows of the category. In the language of category theory, one says that there is a forgetful functor from the category of small categories to the category of quivers.

category theory

unary operations

edge contraction

binary operations

disjoint union of graphs

There are several operations that produce new graphs from initial ones, which might be classified into the following categories:

Generalizations[edit]

In a hypergraph, an edge can join any positive number of vertices.


An undirected graph can be seen as a simplicial complex consisting of 1-simplices (the edges) and 0-simplices (the vertices). As such, complexes are generalizations of graphs since they allow for higher-dimensional simplices.


Every graph gives rise to a matroid.


In model theory, a graph is just a structure. But in that case, there is no limitation on the number of edges: it can be any cardinal number, see continuous graph.


In computational biology, power graph analysis introduces power graphs as an alternative representation of undirected graphs.


In geographic information systems, geometric networks are closely modeled after graphs, and borrow many concepts from graph theory to perform spatial analysis on road networks or utility grids.

Conceptual graph

Graph (abstract data type)

Graph database

Graph drawing

List of graph theory topics

List of publications in graph theory

Network theory

Balakrishnan, V. K. (1997). Graph Theory (1st ed.). McGraw-Hill.  978-0-07-005489-9.

ISBN

Bang-Jensen, J.; Gutin, G. (2000). . Springer.

Digraphs: Theory, Algorithms and Applications

Bender, Edward A.; Williamson, S. Gill (2010). .

Lists, Decisions and Graphs. With an Introduction to Probability

Berge, Claude (1958). Théorie des graphes et ses applications (in French). Paris: Dunod.

Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge University Press.  978-0-521-45897-9.

ISBN

Bollobás, Béla (2002). Modern Graph Theory (1st ed.). Springer.  978-0-387-98488-9.

ISBN

Diestel, Reinhard (2005). (3rd ed.). Berlin, New York: Springer-Verlag. ISBN 978-3-540-26183-4.

Graph Theory

Graham, R.L.; Grötschel, M.; Lovász, L. (1995). Handbook of Combinatorics. MIT Press.  978-0-262-07169-7.

ISBN

Gross, Jonathan L.; Yellen, Jay (1998). Graph Theory and Its Applications. CRC Press.  978-0-8493-3982-0.

ISBN

Gross, Jonathan L.; Yellen, Jay (2003). Handbook of Graph Theory. CRC.  978-1-58488-090-5.

ISBN

Harary, Frank (1995). Graph Theory. Addison Wesley Publishing Company.  978-0-201-41033-4.

ISBN

Iyanaga, Shôkichi; Kawada, Yukiyosi (1977). . MIT Press. ISBN 978-0-262-09016-2.

Encyclopedic Dictionary of Mathematics

Zwillinger, Daniel (2002). CRC Standard Mathematical Tables and Formulae (31st ed.). Chapman & Hall/CRC.  978-1-58488-291-6.

ISBN

Trudeau, Richard J. (1993). (Corrected, enlarged republication. ed.). New York: Dover Publications. ISBN 978-0-486-67870-2. Retrieved 8 August 2012.

Introduction to Graph Theory

Media related to Graph (discrete mathematics) at Wikimedia Commons

"Graph". MathWorld.

Weisstein, Eric W.