Editing Graph theory
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
− | A '''graph''' is a mathematical object with '''vertices''' (also known as '''nodes'''), discrete objects, and '''edges''' | + | 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''. |
==Structure of a graph== | ==Structure of a graph== | ||
Line 10: | Line 10: | ||
===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 | + | 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=== | ===Weighted graphs=== | ||
Line 48: | Line 48: | ||
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 '''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'''. | + | 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=== | ===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.) | 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 | + | 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 '''[[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. | + | 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>. | 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 | + | 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== | |
− | + |