A graph is an ordered pair of disjoint sets such that is a subset of the set of unordered pairs of . and are always assumed to be finite, unless explicitly stated otherwise. The set is the set of vertices (sometimes called nodes) and is the set of edges. If is a graph, then is the vertex set of , and is the edge set. Typically, is defined to be nonempty. If is a vertex of , we sometimes write instead of .
An edge (with ) is said to join the vertices and and is denoted by . One says that the edges and are equivalent; the vertices and are the endvertices of this edge. If , then and are adjacent, or neighboring, vertices of , and the vertices and are incident with the edge . Two edges are adjacent if they have at least one common endvertex. Also, means that the vertex is adjacent to the vertex .
Notice that this definition allows pairs of the form , which would correspond to a node joining to itself. Some authors explicitly disallow this in their definition of a graph.
Note: Some authors include multigraphs in their definition of a graph. In this notation, the above definition corresponds to that of a simple graph. A graph is then simple if there is at most one edge joining each pair of nodes.
Adapted with permission of the author from by Béla Bollobás, published by Springer-Verlag New York, Inc., 1998.
|Date of creation||2013-03-22 11:57:54|
|Last modified on||2013-03-22 11:57:54|
|Last modified by||mathcam (2727)|