Difference between revisions of "Graph theory"
(Created page with "A '''graph''' is a mathematical object with ''vertices'', discrete objects, and ''edges'', relationships between pairs of objects. Because of the wide variety of objects and rela...") |
|||
| Line 1: | Line 1: | ||
| − | A '''graph''' is a mathematical object with ''vertices'', discrete objects, and ''edges'', relationships between pairs of objects. Because of the wide variety of objects and relationships that may be abstracted as vertices and edges, graphs are highly versatile, and may be used to model a great number of different real-world entities, such as cities and highways, social networks, and the positions of the Rubik's Cube. Likewise, many interesting problems in computer science concern graphs themselves. The subdiscipline of mathematics and computer science concerning graphs is known as ''graph theory''. | + | A '''graph''' is a mathematical object with '''vertices''' (also known as '''nodes'''), discrete objects, and '''edges''', relationships between pairs of objects. Because of the wide variety of objects and relationships that may be abstracted as vertices and edges, graphs are highly versatile, and may be used to model a great number of different real-world entities, such as cities and highways, social networks, and the positions of the Rubik's Cube. Likewise, many interesting problems in computer science concern graphs themselves. The subdiscipline of mathematics and computer science concerning graphs is known as ''graph theory''. |
| − | ==Basic structure== | + | ==Structure of a graph== |
| − | Although some graphs may have additional components, all graphs have at least a set of vertices, <math>V</math>, and a set of edges, <math>E</math>. Each edge is a pair of vertices, say, <math>u</math> and <math>v</math>, and indicates that some relationship exists between <math>u</math> and <math>v</math>. We say that this edge is ''between'' the vertices <math>u</math> and <math>v</math>, that it is ''incident upon'' <math>u</math> and <math>v</math>, or that <math>u</math> and <math>v</math> are ''connected by'' the edge. If there is no edge between <math>u</math> and <math>v</math>, then no such relationship exists. Take as examples those mentioned in the introduction: | + | ===Basic structure=== |
| + | Although some graphs may have additional components, all graphs have at least a set of vertices, <math>V</math>, and a set of edges, <math>E</math>. Each edge is a pair of vertices, say, <math>u</math> and <math>v</math>, and indicates that some relationship exists between <math>u</math> and <math>v</math>. We say that this edge is '''between''' the vertices <math>u</math> and <math>v</math>, that it is '''incident upon''' <math>u</math> and <math>v</math>, or that <math>u</math> and <math>v</math> are '''connected by''' the edge, and that the two vertices are '''adjacent''' and are '''neighbors'''. If there is no edge between <math>u</math> and <math>v</math>, then no such relationship exists. Take as examples those mentioned in the introduction: | ||
* Given a collection of cities, make each of these cities into a vertex, and if two cities are connected by a highway, connect the two corresponding vertices by an edge. You now have a graph that encodes the network of cities and highways in an abstract way. | * Given a collection of cities, make each of these cities into a vertex, and if two cities are connected by a highway, connect the two corresponding vertices by an edge. You now have a graph that encodes the network of cities and highways in an abstract way. | ||
* Given a group of people, make each person a vertex, and if two people are friends, connect the two corresponding vertices by an edge. You now have a graph that encodes this social network in an abstract way. | * Given a group of people, make each person a vertex, and if two people are friends, connect the two corresponding vertices by an edge. You now have a graph that encodes this social network in an abstract way. | ||
| Line 8: | Line 9: | ||
We usually give vertices names, or ''labels'' (often non-negative integers), so that we can distinguish them and remember which vertex is which. Often, to help visualize a problem, we will want to draw a graph on paper. Generally this is done by drawing a dot or a circle for each vertex and drawing a line segment between a pair of dots or pair of circles if and only if there is an edge connecting the corresponding vertices. If we choose to represent the vertices by dots, we generally draw their labels somewhere close by; using circles, we can place them inside, if they are small integers or letters (and hence don't take up too much space.) | We usually give vertices names, or ''labels'' (often non-negative integers), so that we can distinguish them and remember which vertex is which. Often, to help visualize a problem, we will want to draw a graph on paper. Generally this is done by drawing a dot or a circle for each vertex and drawing a line segment between a pair of dots or pair of circles if and only if there is an edge connecting the corresponding vertices. If we choose to represent the vertices by dots, we generally draw their labels somewhere close by; using circles, we can place them inside, if they are small integers or letters (and hence don't take up too much space.) | ||
| − | ==Directed and undirected graphs== | + | ===Directed and undirected graphs=== |
| + | Some relationships are two-way, but some are only one-way. For example, suppose that in the social network example given in the preceding section, we place an edge between the vertices representing two people if and only if one of them has a crush on the other. The trouble here is that clearly, Alice having a crush on Bob is different than Bob having a crush on Alice, and hence these two scenarios ought to be represented by ''different graphs''. In order to arrange this, we stipulate that each edge also has a ''direction'', and that an edge from <math>u</math> to <math>v</math> is not the same as an edge from <math>v</math> to <math>u</math>. A graph that encodes this one-way information is known as a '''directed graph''', whereas one that does not is an '''undirected graph'''. When an edge from <math>u</math> to <math>v</math> is drawn in the diagram of a graph, generally an arrowhead is added on the end of the line segment representing that edge near <math>v</math>, so that the segment "points" from <math>u</math> to <math>v</math>. Note that it is possible for two-way relationships to be represented by directed graphs; maybe Alice and Bob secretly have a crush on each other. This would be represented by both edges existing in <math>E</math> and a double-ended arrow. The point is that directed graphs must be used when it is not guaranteed that all relationships will be bidirectional. An edge from <math>u</math> to <math>v</math> is said to '''enter''' <math>v</math> and '''leave''' <math>u</math>. | ||
| + | |||
| + | ===Weighted graphs=== | ||
| + | We can endow a graph, be it directed or undirected, with even more structure if we assign a real number to each edge, which is known as a '''weight''', or, depending on the application, '''length''' or '''cost'''. (The term ''weight'' is generic.) Here are some examples of how this may be useful: | ||
| + | * If vertices represent cities and edges represent highways, then let the weight of an edge be the length of time it takes to traverse the corresponding highway (''i.e.'', the time between the two cities corresponding to the vertices that the edge connects). | ||
| + | * If vertices represent warehouses and edges represent shipping routes, let the weight of an edge be the cost of shipping between the warehouses corresponding to the vertices connected by that edge. | ||
| + | A graph in which edges have weight is known as a '''weighted graph''', and one without this information is known as an '''unweighted graph'''. Unweighted graphs can often be modelled as weighted graphs in which each edge has weight 1. | ||
| + | |||
| + | In a directed, weighted graph, when edges exist from <math>u</math> to <math>v</math> and from <math>v</math> to <math>u</math>, these two edges do not necessarily have the same weight. | ||
| + | |||
| + | ===Simple graphs, multigraphs, and hypergraphs=== | ||
| + | We have glossed over two subtleties in the above discussion. | ||
| + | |||
| + | First, some graphs may have '''loops'''. A loop is an edge that connects a vertex to itself. In many applications of graph theory, loops will not be allowed, but if they are, they are usually not too much of a pain to deal with. (Note that a loop in a directed graph will be drawn with a single arrowhead, not two.) In the mathematical description in the previous section, an edge in an undirected graph with loops will have to be considered a multiset instead of a plain set, as it contains two of the same vertex. | ||
| + | |||
| + | More troublesome than loops are multiple edges connecting a given pair of vertices. In a directed graph, it is normal to have two edges between a pair of vertices, one in each direction, but multiple edges in undirected graphs, or multiple edges in directed graphs in the same direction, can cause problems. First, they cannot be adequately represented with adjacency matrices, although adjacency lists will handle them, and second, the definition of the weight function above will not work, and instead the weight function must be thought of as a function from <math>E</math> to <math>\mathbb{R}</math>. However, in many applications, multiple edges from one vertex to another can be treated as a single edge whose weight is either the sum, maximum, or minimum of the weights of the multiple edges. | ||
| + | |||
| + | An undirected graph with no loops and no multiple edges is known as a '''simple graph'''. A '''multigraph''' may have multiple edges, but whether it may contain loops depends on the context. | ||
| + | |||
| + | A '''hypergraph''' is a generalization of a graph in which the relationships may involve more than two nodes at a time. They are generally less useful than ordinary graphs. | ||
| + | |||
| + | ==Representation of graphs== | ||
| + | ===Mathematically=== | ||
| + | Mathematically, an unweighted graph is considered to be an ordered pair <math>G = (V,E)</math>, where <math>V</math> is the set of vertices and <math>E</math> is the set of edges. <math>V</math> and <math>E</math> need not be finite. Each element of <math>E</math> is, of course, a pair of elements from <math>V</math>. If the graph is directed, then it is an ''ordered pair'', so that <math>E \subseteq \{(u,v) \mid u, v \in V\}</math>. If the graph is undirected, then it is really an unordered pair, or a set, so that <math>E \subseteq \{\{u,v\} \mid u,v \in V\}</math>. A weighted graph has an additional component, so that <math>G = (V,E,\operatorname{wt})</math>, where <math>\operatorname{wt}</math> is the '''weight function''', <math>\operatorname{wt}:V \times V \to \mathbb{R}</math>. Here <math>\operatorname{wt}(u,v)</math> represents the weight of the edge from <math>u</math> to <math>v</math>, if such an edge exists; otherwise, it is either zero, infinite, or undefined (whichever is most convenient). Note that in an undirected graph, <math>\operatorname{wt}(u,v) = \operatorname{wt}(v,u)</math>. | ||
| + | |||
| + | ===Adjacency matrix=== | ||
| + | In programming, there are two main representations of graphs. A graph may be represented by a two-dimensional [[array]], or '''adjacency matrix''', with <math>|V|</math> rows and <math>|V|</math> columns, where the entry <math>A_{ij}</math> in row <math>i</math> and column <math>j</math> is 1 if an edge from <math>i</math> to <math>j</math> exists, 0 otherwise. In an adjacency matrix for an undirected graph, <math>A_{ij} = A_{ji}</math> for all <math>1 \leq i,j \leq |V|</math>. If the graph is weighted, we often have <math>A_{ij} = \operatorname{wt}(i,j)</math>. Thus the adjacency matrix contains enough information to completely reconstruct the graph, and takes up <math>\Theta(|V|^2)</math> space. It takes only <math>O(1)</math> time to determine whether two vertices are connected, but it takes <math>O(|V|)</math> time to retrieve all neighbors of a given vertex, as we have to scan an entire row or column. | ||
| + | |||
| + | ===Adjacency list=== | ||
| + | The other major representation of the graph is the '''adjacency list'''. An adjacency list is actually a collection of <math>|V|</math> [[Linked list|lists]] of vertices, each of which corresponds to one vertex. The vertex <math>v</math> will appear in the list of vertex <math>u</math> if and only if there is an edge from <math>u</math> to <math>v</math>. (If the graph is undirected, this means that <math>u</math> will also appear in <math>v</math>'s list.) Additional information, such as the weight of the edge, may be stored along with that node in the list. This will now only use <math>\Theta(E+V)</math> space, and all neighbors of a given node may be retrieved in linear time (''i.e.'', constant time per neighbor). The drawback is that it will take <math>O(|V|)</math> time to determine whether two given nodes are adjacent, since this would require searching through one of their lists. | ||
| + | |||
| + | In practice, linked lists are not often used; arrays can often be used instead, provided that they only take up as much space as they need to, instead of all having size <math>|V|</math> (which is the maximum size that one might have to be). This is easily accomplished using dynamic arrays, such as <code>std::vector</code> in C++. If edges are not added or deleted, this also makes it possible to determine whether two given nodes are neighbors in <math>O(\log |V|)</math> time, by [[sort]]ing each list and performing [[binary search]]. | ||
| + | |||
| + | ==Graph-theoretic concepts== | ||
| + | The '''degree''' of a vertex is the number of edges incident upon it. If the graph is directed, this can be split up into the '''in-degree''', which is the number of edges ''entering'' the vertex, and the '''out-degree''', the number of edges ''leaving'' it. | ||
| + | |||
| + | A '''path''' is a [[sequence]] of vertices <math>v_0, v_1, ..., v_n</math> such that for all <math>1 \leq i \leq n</math>, there is an edge from <math>v_{i-1}</math> to <math>v_i</math>. If such a sequence exists, we say it is a path ''from'' <math>v_0</math> to <math>v_n</math> or ''between'' <math>v_0</math> and <math>v_n</math>, or that <math>v_0</math> and <math>v_n</math> are ''connected'' by that path, or that <math>v_n</math> is '''reachable''' from <math>v_0</math>. Note that in a directed graph, saying there is a path from <math>u</math> to <math>v</math> is not the same as saying there is a path from <math>v</math> to <math>u</math>, and the same applies to reachability; if <math>u</math> and <math>v</math> are reachable from each other then they are said to be '''mutually reachable'''. We also say that the path '''visits''' each of the vertices <math>v_0, v_1, ..., v_n</math>. On a diagram of a graph, a path is obtained by "following" the edges (going only in the directions of arrowheads, if the graph is directed). The '''length''' of a path is the number of edges on that path (one less than the number of vertices), and the '''weight''' of the path, if the graph is weighted, is the sum of the weights of the edges along that path. (The definition must be slightly modified when multiple edges are allowed.) Note that in some cases ''length'' can actually mean ''weight'' in a weighted graph; mind the context. A path is said to be a '''simple path''' if it does not visit any vertex more than once. | ||
| + | |||
| + | A '''cycle''' is a path in which the first and last vertex are the same. By definition, a cycle can never be a simple path, but if it repeats no vertex other than the first and last, it is known as a '''simple cycle'''. An '''odd cycle''' is a cycle with odd length, whereas an '''even cycle''' is a cycle with even length. If a graph has no cycles, it is said to be '''acyclic'''. | ||
| + | |||
| + | ===Types of graphs=== | ||
| + | Given a graph, if we remove some (possibly zero) vertices and some (possibly zero) edges, we obtain a '''subgraph'''. (Note that when a vertex is removed, all edges incident upon it must be removed too.) | ||
| + | |||
| + | An undirected graph is said to be '''connected''' if and only if every vertex is reachable from every other vertex. A directed graph is said to be '''strongly connected''' if and only if each pair of distinct vertices is mutually reachable. If an undirected graph is not connected, it has two or more subgraphs called '''connected components'''. A connected component consists of a vertex and all the vertices reachable from it (and all the incident edges); if two vertices are reachable from each other than they will be in the same connected component, but if not, they will be in different connected components. Put another way, define an equivalence relation on the vertices of the graph so that two vertices are equivalent if and only if one is reachable from the other; then connected components are equivalence classes. If a directed graph is not strongly connected, it has two or more subgraphs called '''strongly connected components'''; these are analogous to connected components, and two vertices are in the same strongly connected component if and only if they are mutually reachable. Identifying the connected components of a graph can be easily accomplished in linear time ''via'' a [[graph search]]. Identifying strongly connected components is more challenging, but can still be accomplished in linear time ''via'' [[Kosaraju's algorithm]], [[Tarjan's algorithm]], or [[Gabow's algorithm]]. | ||
| + | |||
| + | A '''[[tree]]''' is an undirected graph that is both connected and acyclic. A '''forest''' is a graph that consists of one or more trees. If a graph is directed and acyclic, it is simply known as a '''[[directed acyclic graph]]''' or by the initialism '''DAG'''. A directed graph that is like a tree, but in which every edge points ''away'' from one of the tree's vertices, is called an '''arborescence'''. | ||
| + | |||
| + | A '''bridge''' or '''cut edge''' is an edge that, when removed, causes an increase in the number of connected components of a graph. If a connected graph has no bridges, then it remains connected when any edge is removed, and is said to be '''edge-connected'''. If a graph is not edge-connected, it has two or more '''edge-connected components''', defined analogously to connected components; two vertices are in the same edge-connected component if they remain connected when any edge is removed. A '''cut vertex''' or '''articulation point''' is a vertex that, when removed, causes an increase in the number of connected components. If a connected graph has no articulation points, then it remains connected when any vertex is removed, and is said to be '''biconnected'''. If a graph is not biconnected, it has two or more '''biconnected components''', defined analogously to edge-connected components. Cut vertices and edges may be identified in linear time using [[Detection of cut vertices and cut edges|an algorithm due to Hopcroft and Tarjan]]. | ||
| + | |||
| + | Edges may also be '''spliced''' or '''subdivided''', which refers to removing an edge and connecting its two vertices ''via'' a third vertex inserted "between" them (by adding two new edges). Splicing increases the number of vertices by one and the number of edges by one. If repeated splicing operations on a graph <math>G</math> yield graph <math>G'</math>, then <math>G'</math> is said to be a '''subdivision''' of <math>G</math>, and <math>G</math> is said to be a '''minor''' of <math>G'</math>. | ||
| + | |||
| + | A '''flow graph''' or '''flow network''' is a directed graph in which two distinct vertices are specifically denoted the '''source''', <math>s</math>, and the '''sink''', <math>t</math>, no edges enter <math>s</math>, and no edges leave <math>t</math>. An <math>s-t</math> cut is a set of edges which, when deleted from a flow graph, cause the sink to become unreachable from the source. As the name suggests, a flow graph is useful for modelling the flow of something (be it concrete or abstract) from the source to sink. | ||
| + | |||
| + | ==Problems in graph theory== | ||
Revision as of 00:38, 10 March 2011
A graph is a mathematical object with vertices (also known as nodes), discrete objects, and edges, relationships between pairs of objects. Because of the wide variety of objects and relationships that may be abstracted as vertices and edges, graphs are highly versatile, and may be used to model a great number of different real-world entities, such as cities and highways, social networks, and the positions of the Rubik's Cube. Likewise, many interesting problems in computer science concern graphs themselves. The subdiscipline of mathematics and computer science concerning graphs is known as graph theory.
Contents
Structure of a graph
Basic structure
Although some graphs may have additional components, all graphs have at least a set of vertices, 
, and a set of edges, 
. Each edge is a pair of vertices, say, 
and 
, and indicates that some relationship exists between and . We say that this edge is between the vertices and , that it is incident upon and , or that and are connected by the edge, and that the two vertices are adjacent and are neighbors. If there is no edge between and , then no such relationship exists. Take as examples those mentioned in the introduction:
- Given a collection of cities, make each of these cities into a vertex, and if two cities are connected by a highway, connect the two corresponding vertices by an edge. You now have a graph that encodes the network of cities and highways in an abstract way.
- Given a group of people, make each person a vertex, and if two people are friends, connect the two corresponding vertices by an edge. You now have a graph that encodes this social network in an abstract way.
- Let each legal position of the Rubik's Cube be a vertex, and if it is possible to get from one position to another in one move, then connect the two corresponding vertices with an edge. You now have a (very large) graph that encodes all the details of the puzzle.
We usually give vertices names, or labels (often non-negative integers), so that we can distinguish them and remember which vertex is which. Often, to help visualize a problem, we will want to draw a graph on paper. Generally this is done by drawing a dot or a circle for each vertex and drawing a line segment between a pair of dots or pair of circles if and only if there is an edge connecting the corresponding vertices. If we choose to represent the vertices by dots, we generally draw their labels somewhere close by; using circles, we can place them inside, if they are small integers or letters (and hence don't take up too much space.)
Directed and undirected graphs
Some relationships are two-way, but some are only one-way. For example, suppose that in the social network example given in the preceding section, we place an edge between the vertices representing two people if and only if one of them has a crush on the other. The trouble here is that clearly, Alice having a crush on Bob is different than Bob having a crush on Alice, and hence these two scenarios ought to be represented by different graphs. In order to arrange this, we stipulate that each edge also has a direction, and that an edge from to is not the same as an edge from to . A graph that encodes this one-way information is known as a directed graph, whereas one that does not is an undirected graph. When an edge from to is drawn in the diagram of a graph, generally an arrowhead is added on the end of the line segment representing that edge near , so that the segment "points" from to . Note that it is possible for two-way relationships to be represented by directed graphs; maybe Alice and Bob secretly have a crush on each other. This would be represented by both edges existing in and a double-ended arrow. The point is that directed graphs must be used when it is not guaranteed that all relationships will be bidirectional. An edge from to is said to enter and leave .
Weighted graphs
We can endow a graph, be it directed or undirected, with even more structure if we assign a real number to each edge, which is known as a weight, or, depending on the application, length or cost. (The term weight is generic.) Here are some examples of how this may be useful:
- If vertices represent cities and edges represent highways, then let the weight of an edge be the length of time it takes to traverse the corresponding highway (i.e., the time between the two cities corresponding to the vertices that the edge connects).
- If vertices represent warehouses and edges represent shipping routes, let the weight of an edge be the cost of shipping between the warehouses corresponding to the vertices connected by that edge.
A graph in which edges have weight is known as a weighted graph, and one without this information is known as an unweighted graph. Unweighted graphs can often be modelled as weighted graphs in which each edge has weight 1.
In a directed, weighted graph, when edges exist from to and from to , these two edges do not necessarily have the same weight.
Simple graphs, multigraphs, and hypergraphs
We have glossed over two subtleties in the above discussion.
First, some graphs may have loops. A loop is an edge that connects a vertex to itself. In many applications of graph theory, loops will not be allowed, but if they are, they are usually not too much of a pain to deal with. (Note that a loop in a directed graph will be drawn with a single arrowhead, not two.) In the mathematical description in the previous section, an edge in an undirected graph with loops will have to be considered a multiset instead of a plain set, as it contains two of the same vertex.
More troublesome than loops are multiple edges connecting a given pair of vertices. In a directed graph, it is normal to have two edges between a pair of vertices, one in each direction, but multiple edges in undirected graphs, or multiple edges in directed graphs in the same direction, can cause problems. First, they cannot be adequately represented with adjacency matrices, although adjacency lists will handle them, and second, the definition of the weight function above will not work, and instead the weight function must be thought of as a function from to 
. However, in many applications, multiple edges from one vertex to another can be treated as a single edge whose weight is either the sum, maximum, or minimum of the weights of the multiple edges.
An undirected graph with no loops and no multiple edges is known as a simple graph. A multigraph may have multiple edges, but whether it may contain loops depends on the context.
A hypergraph is a generalization of a graph in which the relationships may involve more than two nodes at a time. They are generally less useful than ordinary graphs.
Representation of graphs
Mathematically
Mathematically, an unweighted graph is considered to be an ordered pair 
, where is the set of vertices and is the set of edges. and need not be finite. Each element of is, of course, a pair of elements from . If the graph is directed, then it is an ordered pair, so that 
. If the graph is undirected, then it is really an unordered pair, or a set, so that 
. A weighted graph has an additional component, so that 
, where 
is the weight function, 
. Here 
represents the weight of the edge from to , if such an edge exists; otherwise, it is either zero, infinite, or undefined (whichever is most convenient). Note that in an undirected graph, 
.
Adjacency matrix
In programming, there are two main representations of graphs. A graph may be represented by a two-dimensional array, or adjacency matrix, with 
rows and columns, where the entry 
in row 
and column 
is 1 if an edge from to exists, 0 otherwise. In an adjacency matrix for an undirected graph, 
for all 
. If the graph is weighted, we often have 
. Thus the adjacency matrix contains enough information to completely reconstruct the graph, and takes up 
space. It takes only 
time to determine whether two vertices are connected, but it takes 
time to retrieve all neighbors of a given vertex, as we have to scan an entire row or column.
Adjacency list
The other major representation of the graph is the adjacency list. An adjacency list is actually a collection of lists of vertices, each of which corresponds to one vertex. The vertex will appear in the list of vertex if and only if there is an edge from to . (If the graph is undirected, this means that will also appear in 's list.) Additional information, such as the weight of the edge, may be stored along with that node in the list. This will now only use 
space, and all neighbors of a given node may be retrieved in linear time (i.e., constant time per neighbor). The drawback is that it will take time to determine whether two given nodes are adjacent, since this would require searching through one of their lists.
In practice, linked lists are not often used; arrays can often be used instead, provided that they only take up as much space as they need to, instead of all having size (which is the maximum size that one might have to be). This is easily accomplished using dynamic arrays, such as std::vector in C++. If edges are not added or deleted, this also makes it possible to determine whether two given nodes are neighbors in 
time, by sorting each list and performing binary search.
Graph-theoretic concepts
The degree of a vertex is the number of edges incident upon it. If the graph is directed, this can be split up into the in-degree, which is the number of edges entering the vertex, and the out-degree, the number of edges leaving it.
A path is a sequence of vertices 
such that for all 
, there is an edge from 
to 
. If such a sequence exists, we say it is a path from 
to 
or between and , or that and are connected by that path, or that is reachable from . Note that in a directed graph, saying there is a path from to is not the same as saying there is a path from to , and the same applies to reachability; if and are reachable from each other then they are said to be mutually reachable. We also say that the path visits each of the vertices . On a diagram of a graph, a path is obtained by "following" the edges (going only in the directions of arrowheads, if the graph is directed). The length of a path is the number of edges on that path (one less than the number of vertices), and the weight of the path, if the graph is weighted, is the sum of the weights of the edges along that path. (The definition must be slightly modified when multiple edges are allowed.) Note that in some cases length can actually mean weight in a weighted graph; mind the context. A path is said to be a simple path if it does not visit any vertex more than once.
A cycle is a path in which the first and last vertex are the same. By definition, a cycle can never be a simple path, but if it repeats no vertex other than the first and last, it is known as a simple cycle. An odd cycle is a cycle with odd length, whereas an even cycle is a cycle with even length. If a graph has no cycles, it is said to be acyclic.
Types of graphs
Given a graph, if we remove some (possibly zero) vertices and some (possibly zero) edges, we obtain a subgraph. (Note that when a vertex is removed, all edges incident upon it must be removed too.)
An undirected graph is said to be connected if and only if every vertex is reachable from every other vertex. A directed graph is said to be strongly connected if and only if each pair of distinct vertices is mutually reachable. If an undirected graph is not connected, it has two or more subgraphs called connected components. A connected component consists of a vertex and all the vertices reachable from it (and all the incident edges); if two vertices are reachable from each other than they will be in the same connected component, but if not, they will be in different connected components. Put another way, define an equivalence relation on the vertices of the graph so that two vertices are equivalent if and only if one is reachable from the other; then connected components are equivalence classes. If a directed graph is not strongly connected, it has two or more subgraphs called strongly connected components; these are analogous to connected components, and two vertices are in the same strongly connected component if and only if they are mutually reachable. Identifying the connected components of a graph can be easily accomplished in linear time via a graph search. Identifying strongly connected components is more challenging, but can still be accomplished in linear time via Kosaraju's algorithm, Tarjan's algorithm, or Gabow's algorithm.
A tree is an undirected graph that is both connected and acyclic. A forest is a graph that consists of one or more trees. If a graph is directed and acyclic, it is simply known as a directed acyclic graph or by the initialism DAG. A directed graph that is like a tree, but in which every edge points away from one of the tree's vertices, is called an arborescence.
A bridge or cut edge is an edge that, when removed, causes an increase in the number of connected components of a graph. If a connected graph has no bridges, then it remains connected when any edge is removed, and is said to be edge-connected. If a graph is not edge-connected, it has two or more edge-connected components, defined analogously to connected components; two vertices are in the same edge-connected component if they remain connected when any edge is removed. A cut vertex or articulation point is a vertex that, when removed, causes an increase in the number of connected components. If a connected graph has no articulation points, then it remains connected when any vertex is removed, and is said to be biconnected. If a graph is not biconnected, it has two or more biconnected components, defined analogously to edge-connected components. Cut vertices and edges may be identified in linear time using an algorithm due to Hopcroft and Tarjan.
Edges may also be spliced or subdivided, which refers to removing an edge and connecting its two vertices via a third vertex inserted "between" them (by adding two new edges). Splicing increases the number of vertices by one and the number of edges by one. If repeated splicing operations on a graph 
yield graph 
, then is said to be a subdivision of , and is said to be a minor of .
A flow graph or flow network is a directed graph in which two distinct vertices are specifically denoted the source, 
, and the sink, 
, no edges enter , and no edges leave . An 
cut is a set of edges which, when deleted from a flow graph, cause the sink to become unreachable from the source. As the name suggests, a flow graph is useful for modelling the flow of something (be it concrete or abstract) from the source to sink.
