Glossary of graph theory

From Wikipedia, the free encyclopedia
  (Redirected from Weighted graph)
Jump to: navigation, search

This is a glossary of graph theory, the study of graphs, systems of nodes or vertices connected in pairs by edges. For more information on this subject, see graph theory.

!$@[edit]

[]
G[S] is the induced subgraph of a graph G for vertex subset S.

A[edit]

arc
An edge of a directed graph, also sometimes called an arrow.
arrow
See arc.
adjacency matrix
The adjacency matrix of a graph is a matrix whose rows and columns are both indexed by vertices of the graph, with a one in the cell for row i and column j when vertices i and j are adjacent, and a zero otherwise.
adjacent
The relation between two vertices that are both endpoints of the same edge.

C[edit]

complement
The complement graph \bar{G} of a simple graph G is another graph on the same vertex set as G, with an edge for each two vertices that are not adjacent in G.

D[edit]

degree
The degree of a vertex in a graph is its number of incident edges. The degree of a graph (or maximum degree) is the maximum of the degrees of its vertices. Degree is sometimes called valency; the degree of v in G may be denoted dG(v), d(G), or deg(v).
directed
A directed graph is one in which the edges have a distinguished direction, from one vertex to another. In a mixed graph, a directed edge is again one that has a distinguished direction; directed edges may also be called arcs or arrows.

E[edit]

E
See edge set.
edge
An edge is (together with vertices) one of the two basic units out of which graphs are constructed. Each edge has two (or in hypergraphs, more) vertices to which it is attached, called its endpoints. Edges may be directed or undirected, but directed edges are also called arcs. In an undirected simple graph, an edge may be represented as the set of its vertices, and in a directed simple graph it may be represented as an ordered pair of its vertices. An edge that connects vertices x and y is sometimes written xy.
edge set
The set of vertices of a given graph G, sometimes denoted by E(G).
edgeless graph
The edgeless graph on a given set of vertices is the graph that has no edges. It is sometimes called the empty graph, but this term can also refer to a graph with no vertices.
empty graph
1.  An edgeless graph on a set of vertices.
2.  The graph with no vertices and no edges.
endpoint
One of the two vertices incident to a given edge.

F[edit]

factor
A factor of a graph is a spanning subgraph: a subgraph that includes all of the vertices of the graph. The term is primarily used in the context of regular subgraphs: a k-factor is a factor that is k-regular.
factorization
A graph factorization is a partition of the edges of the graph into factors; a k-factorization is a partition into k-factors. For instance a 1-factorization is the same thing as an edge coloring.
finite
A graph is finite if it has a finite number of vertices and a finite number of edges. Many sources assume that all graphs are finite without explicitly saying so. A graph is locally finite if each vertex has a finite number of incident edges. An infinite graph is a graph that is not finite: it has infinitely many vertices, infinitely many edges, or both.
first order
The first order logic of graphs is a form of logic in which variables represent vertices of a graph, and there exists a binary predicate to test whether two vertices are adjacent.
forbidden
A forbidden graph characterization is a characterization of a set of graphs as being the graphs that do not have certain other graphs as subgraphs, induced subgraphs, or minors.
full
See induced.

G[edit]

graph
The fundamental object of study in graph theory, a system of vertices connected in pairs by edges. Often subdivided into directed graphs or undirected graphs according to whether the edges have an orientation or not. Mixed graphs include both types of edges.

H[edit]

H-coloring
An H-coloring of a graph G (where H is also a graph) is a homomorphism from H to G.
H-free
A graph is H-free if it does not have an induced subgraph isomorphic to H, that is, if H is a forbidden induced subgraph. The H-free graphs are the set of all graphs (or, often, all finite graphs) that are H-free.[1] For instance the triangle-free graphs are the graphs that do not have a triangle graph as a subgraph.
homomorphic equivalence
Two graphs are homomorphically equivalent if there exist two homomorphisms, one from each graph to the other graph.
homomorphism
A graph homomorphism is a mapping from the vertex set of one graph to the vertex set of another graph that maps adjacent vertices to adjacent vertices. This type of mapping between graphs is the one that is most commonly used in category-theoretic approaches to graph theory.
hyperedge
An edge in a hypergraph, having any number of endpoints, in contrast to the requirement that edges of graphs have exactly two endpoints.
hypergraph
A hypergraph is a generalization of a graph in which each edge (called a hyperedge in this context) may have more than two endpoints.

I[edit]

incidence matrix
The incidence matrix of a graph is a matrix whose rows are indexed by vertices of the graph, and whose columns are indexed by edges, with a one in the cell for row i and column j when vertex i and edge j are incident, and a zero otherwise.
incident
The relation between an edge and one of its endpoints.
induced
An induced subgraph or full subgraph of a graph is a subgraph formed from a subset of vertices and from all of the edges that have both endpoints in the subset. Special cases include induced paths and induced cycles, induced subgraphs that are paths or cycles.
infinite
See finite.
isomorphic
See isomorphism.
isomorphism
A graph isomorphism is a one-to-one incidence preserving correspondence of the vertices and edges of one graph to the vertices and edges of another graph. Two graphs related in this way are said to be isomorphic.

L[edit]

label
Information associated with a vertex or edge of a graph. A labeled graph is a graph whose vertices or edges have labels. A graph in which the vertices and edges are indistinguishable from each other is called unlabeled. The terms vertex-labeled or edge-labeled may be used to specify which objects of a graph have labels. Graph labeling refers to several different problems of assigning labels to graphs subject to certain constraints.
local
A local property of a graph is a property that is determined only by the neighbourhoods of the vertices in the graph. For instance, a graph is locally finite if all of its neighbourhoods are finite.
loop
A loop or self-loop is an edge both of whose endpoints are the same vertex. These are not allowed in simple graphs.

M[edit]

maximal
A subgraph of given graph G is maximal for a particular property if it has that property but no other supergraph of it that is also a subgraph of G also has the same property.
minimal
A subgraph of given graph is minimal for a particular property if it has that property but no proper subgraph of it also has the same property.
mixed
A mixed graph is a graph that may include both directed and undirected edges.
multigraph
A multigraph is a graph that allows multiple adjacencies (and, often, self-loops); a graph that is not required to be simple.
multiple adjacency
A multiple adjacency or multiple edge is a set of more than one edge that all have the same endpoints (in the same direction, in the case of directed graphs). A graph with multiple edges is often called a multigraph.
multiplicity
The multiplicity of an edge is the number of edges in a multiple adjacency. The multiplicity of a graph is the maximum multiplicity of any of its edges.

N[edit]

N
See neighbourhood.
neighbour
A vertex that is adjacent to a given vertex.
neighbourhood
The open neighbourhood (or neighborhood) of a vertex v is the subgraph induced by all vertices that are adjacent to v. The closed neighbourhood is defined in the same way but also includes v itself. The open neighbourhood of v in G may be denoted NG(v) or N(v), and the closed neighbourhood may be denoted NG[v] or N[v]. When the openness or closedness of a neighborhood is not specified, it is assumed to be open.
non-edge
A pair of vertices that are not adjacent; the edges of the complement graph.
null graph
See empty graph.

O[edit]

order
The order of a graph G is the number of its vertices, |V(G)|. The variable n is often used for this quantity. See also size, the number of edges.

P[edit]

pseudograph
A graph or multigraph that allows self-loops.
proper
A proper subgraph is a subgraph that does not equal the whole graph.

Q[edit]

quiver
A quiver is a directed multigraph, as used in category theory.

R[edit]

regular
A graph is d-regular when all of its vertices have degree d. A regular graph is a graph that is d-regular for some d.

S[edit]

second order
The second order logic of graphs is a form of logic in which variables may represent vertices, edges, sets of vertices, and (sometimes) sets of edges. This logic includes predicates for testing whether a vertex and edge are incident, as well as whether a vertex or edge belongs to a set.
self-loop
See loop.
simple
1.  A simple graph is a graph with no loops and with no multiple adjacencies. That is, each edge connects two distinct endpoints and no two edges have the same endpoints. A simple edge is an edge that is not part of a multiple adjacency. In many cases, graphs are assumed to be simple unless specified otherwise.
2.  A simple path or a simple cycle is a path or cycle that has no repeated vertices (and no repeated edges).
size
The size of a graph G is the number of its edges, |E(G)|.[2] The variable m is often used for this quantity. See also order, the number of vertices.
spanning
A subgraph is spanning when it includes all of the vertices of the given graph. Important cases include spanning trees, spanning subgraphs that are trees, and perfect matchings, spanning subgraphs that are matchings. A spanning subgraph may also be called a factor, especially (but not only) when it is regular.
subgraph
A subgraph of a graph G is another graph formed from a subset of the vertices and edges of G. The vertex subset must include all endpoints of the edge subset, but may also include additional vertices. A spanning subgraph is one that includes all vertices of the graph; an induced subgraph is one that includes all the edges whose endpoints belong to the vertex subset.
supergraph
A graph formed by adding vertices, edges, or both to a given graph. If H is a subgraph of G, then G is a supergraph of H.

U[edit]

undirected
An undirected graph is a graph in which the two endpoints of each edge are not distinguished from each other. See also directed and mixed. In a mixed graph, an undirected edge is again one in which the endpoints are not distinguished from each other.
uniform
A hypergraph is k-uniform when all its edges have k endpoints, and uniform when it is k-uniform for some k. For instance, ordinary graphs are the same as 2-uniform hypergraphs.
universal
A universal graph is a graph that contains as subgraphs all graphs in a given set of graphs, or all graphs of a given size or order within a given set of graphs.

V[edit]

V
See vertex set.
valency
See degree.
vertex
A vertex (plural vertices) is (together with edges) one of the two basic units out of which graphs are constructed. Vertices of graphs are often considered to be atomic objects, with no internal structure.
vertex set
The set of vertices of a given graph G, sometimes denoted by V(G).
vertices
See vertex.

References[edit]

  1. ^ Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), "Chapter 7: Forbidden Subgraph", Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, pp. 105–121, ISBN 0-89871-432-X .
  2. ^ Harris, John M. (2000). Combinatorics and Graph Theory. New York: Springer-Verlag. p. 5. ISBN 0-387-98736-3.