List of graph theory terms
From Wikipedia, the free encyclopedia
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 (graph theory)
- A cycle is a path which returns to its starting vertex
- degree (graph theory)
- 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 any 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 (graph_theory)
- The girth of a graph is the length of the shortest cycle within that graph.
- graph (mathematics)
- 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 (graph theory)
- A loop is an edge that connects a vertex to itself.
- multigraph
- In a multigraph, each pair of vertices may be connected by more than one edge. (aka pseudograph)
- order (graph theory)
- The order of a graph is the number of vertices in that graph.
- path (graph theory)
- A path is a list of adjacent vertices.
- 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 (graph theory)
- 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 (graph theory)
- 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.
