In Graph theory, there are a number of terms which may seem informal but contain a very specific meaning. This list includes definitions of the most common terms and is arranged alphabetically for ease of reference. The definitions here have been written as clear and succinctly as possible; for a fuller treatment of each subject, see Graph (mathematics), Graph theory, or Glossary of graph theory.
Words in boldface are defined elsewhere in this list.
- acyclic graph
- A graph is acyclic if it contains no cycles.
- adjacent
- Two vertices are adjacent if there is an edge connecting them.
- bridge
- An edge is a bridge if its removal would cause the graph to become disconnected.
- chromatic number
- The chromatic number of a graph is the number of colors that would be necessary if each vertex were to be painted a different color from each of its adjacent vertices.
- circumference
- The circumference of a graph is the length of the longest cycle within that graph.
- clustering coefficient
- A measure of edge density. It can be global or local.
- complete graph
- A graph is complete if there is an edge joining every pair of vertices.
- connected
- A graph is connected if there is a path between every pair of vertices.
- connectivity
- The connectivity of a graph is the number of vertices that would have to be removed for the graph to become disconnected.
- cycle
- A cycle is a path which returns to its starting vertex
- degree
- The degree of a vertex is the number of edges connected to that vertex.
- diameter
- The diameter of a graph is the maximum eccentricity of vertices in that graph.
- directed graph
- The edges of a directed graph have a direction or flow.
- disconnected graph
- A graph is disconnected if there is no path between at least one pair of vertices.
- distance
- The distance between two vertices is the length of the shortest path between those vertices.
- eccentricity
- The eccentricity of a vertex is the maximum distance between that vertex and any other.
- edge
- An edge connects two vertices.
- edge connectivity
- The edge connectivity of a graph is the number of edges that would have to be removed for the graph to become disconnected.
- girth
- The girth of a graph is the length of the shortest cycle within that graph.
- graph
- A graph is a collection of vertices connected by edges.
- hypergraph
- A hypergraph is a graph were edges may connect more than two vertices.
- knot
- A knot is a group of vertices in a directed graph which have no edges flowing away from the group.
- leaf
- A leaf is a vertex of degree 1. Usually used only for trees.
- loop
- A loop is an edge that connects a vertex to itself.
- matching
- A matching or independent edge set in a graph is a set of edges without common vertices.
- maximal matching
- A maximal matching is a matching M of a graph G with the property that if any edge not in M is added to M, it is no longer a matching, that is, M is maximal if it is not a proper subset of any other matching in graph G.
- maximum matching
- A maximum matching is a matching that contains the largest possible number of edges.
- multigraph
- In a multigraph, each pair of vertices may be connected by more than one edge. (aka pseudograph)
- near-perfect matching
- A near-perfect matching is a matching in which exactly one vertex is unmatched. This can only occur when the graph has an odd number of vertices, and such a matching must be maximum.
- order
- The order of a graph is the number of vertices in that graph.
- path
- A path is a list of adjacent vertices.
- perfect matching
- A perfect matching is a matching which matches all vertices of the graph. That is, every vertex of the graph is incident to exactly one edge of the matching.
- planar graph
- A graph is planar if it can be drawn without any crossing edges.
- pseudograph
- See: multigraph.
- radius
- The radius of a graph is the mimimum eccentricity of vertices in that graph.
- root
- A root is a specific vertex of a tree, often drawn at the top of the tree.
- sink
- A sink is a vertex in a directed graph which has only edges directed towards it.
- size
- The size of a graph is the number of edges in that graph.
- source
- A source is a vertex in a directed graph which has only edges directed away from it.
- subgraph
- A subgraph is a group of vertices and edges selected from the vertices and edges of another graph.
- traceable
- A graph is traceable if it has a path which visits all vertices exactly once.
- trail
- A trail is a walk which doesn't use any edge more than once.
- traversable
- A graph is traversable if it has a path which uses each edge exactly once.
- tree
- A tree is any connected, acyclic graph, often thought of as a directed graph with edges flowing from the root to the leaves.
- unicyclic
- A graph is unicyclic of it contains exactly one cycle.
- vertex
- A vertex is a node of a graph.
- walk
- A walk is an ordered list of adjacent vertices.
- weighted graph
- In a weighted graph, each edge has a value associated with it.
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
