Graph (discrete mathematics)
In mathematics, and more specifically in graph theory, a graph is a representation of a set of objects where some pairs of objects are connected by links.
Contents
Description
The interconnected objects are represented by mathematical abstractions called vertices (also called nodes or points), and the links that connect some pairs of vertices are called edges (also called arcs or lines).[1] Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.
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 is an undirected graph, because if person A shook hands with person B, then person B also shook hands with person A.
In contrast, if there is an edge from person A to person B when person A knows of person B, then this graph is directed, because knowledge of someone is not necessarily a symmetric relation (that is, one person knowing another person does not necessarily imply the reverse; for example, many fans may know of a celebrity, but the celebrity is unlikely to know of all their fans).
The former type of graph is called an undirected graph and the edges are called undirected edges while the latter type of graph is called a directed graph and the edges are called directed edges. Graphs are the basic subject studied by graph theory.
Origin
The word "graph" was first used in this sense by J. J. Sylvester in 1878.
See also
- Conceptual graph
- Directed graph
- Flip graph - a graph whose vertices are combinatorial or geometric objects, and whose edges link two of these objects when they can be obtained from one another by an elementary operation called a flip.
- Graph theory
- Dual graph
- Glossary of graph theory
- Graph (abstract data type)
- Graph database
- Graph drawing
- Graph theory
- Hypergraph
- List of graph theory topics
- List of publications in graph theory
- Network theory
External links
- Graph (discrete mathematics) @ Wikipedia
