Types of graphs can be determined by the general principles of their construction (for example, a bipartite graph and an Euler graph), or they can depend on certain properties of vertices or edges (for example, a directed and undirected graph, an ordinary graph).
Directed and undirected graphs
links(the order of the two ends of an edge of a graph is not significant) are called unoriented .
Graphs in which all edges are arcs(the order of the two ends of an edge of a graph is significant) are called directed graphs or digraphs .
Undirected graph can be presented in the form directed graph , if each of its links is replaced by two arcs having opposite directions.
Looped graphs, mixed graphs, empty graphs, multigraphs, ordinary graphs, complete graphs
If the graph contains loops, then this circumstance is specifically stipulated by adding the words "with loops" to the main characteristic of the graph, for example, "digraph with loops". If the graph does not contain loops, then the words "without loops" are added.
mixed is called a graph in which there are edges of at least two of the three varieties mentioned (links, arcs, loops).
Graph consisting of only bare peaks, is called empty .
Multigraph is called a graph in which pairs of vertices can be connected by more than one edge, that is, containing multiple edges, but without loops.
A graph without arcs (that is, undirected), without loops and multiple edges is called ordinary . An ordinary graph is shown in the figure below.
A graph of a given type is called complete , if it contains all edges possible for this type (with the same set of vertices). So, in a complete ordinary graph, each pair of different vertices is connected by exactly one link (figure below).
bipartite graph
The graph is called bipartite , if the set of its vertices can be divided into two subsets so that no edge connects the vertices of the same subset.
Example 1 Build full bipartite graph.
A complete bipartite graph consists of two sets of vertices and of all possible links connecting the vertices of one set with the vertices of another set (figure below).
euler graph
We have already touched problems about Königsberg bridges. Euler's negative solution to this problem led to the first published work on graph theory. The bridge traversal problem can be generalized and the following graph theory problem can be obtained: is it possible to find a cycle in a given graph that contains all vertices and all edges? A graph in which this is possible is called an Euler graph.
So, Euler graph is called a graph in which it is possible to go around all the vertices and at the same time go through one edge only once. In it, each vertex must have only an even number of edges.
Example 2 Is the complete graph with the same number n edges to which each vertex is incident, an Euler graph? Explain the answer. Give examples.
Answer. If n- not even number, then each vertex is incident n-1 ribs. In this case, the given graph is an Euler graph. Examples of such graphs are shown below.
Regular graph
regular graph is a connected graph all of whose vertices have the same degree k. Thus, the figure for example 2 shows examples of regular graphs, called by the degree of its vertices 4-regular and 2-regular graphs or regular graphs of the 4th degree and 2nd degree.
Number of vertices in a regular graph k-th degree cannot be less k+1. A regular graph of odd degree can only have an even number of vertices.
Example 3 Construct a regular graph in which the shortest cycle has length 4.
Solution. We argue as follows: in order for the length of the cycle to satisfy the given condition, it is required that the number of vertices of the graph be a multiple of four. If the number of vertices is four, then the graph shown in the figure below will be obtained. It is regular, but its shortest cycle has length 3.
Increase the number of vertices to eight (the next number is a multiple of four). We connect the vertices with edges so that the degrees of the vertices are equal to three. We get the following graph that satisfies the conditions of the problem.
hamiltonian graph
Hamilton graph is called a graph containing a Hamiltonian cycle. Hamilton cycle is called a simple cycle passing through all the vertices of the graph under consideration. Thus, to put it simply, a Hamiltonian graph is a graph in which all vertices can be traversed and each vertex is repeated only once during the traversal. An example of a Hamiltonian graph is in the figure below.
Example 4 Given a bipartite graph in which n- number of vertices from the set A, but m- number of vertices from the set B. In which case is the graph an Eulerian graph, and in which case is it a Hamiltonian graph?
An edge is an ordered pair of vertices. A graph for which the direction of each of its edges is indicated is called oriented.
Obviously an application to tournaments. For example, the arrow goes from the losing team to the winning one, so the directed graph shows not only who played with whom, but who won.
It is also possible to define a sequence or preference relation by directed graphs.
For example, in algorithm graphs the vertices of the graph correspond operation being performed, and the arcs (oriented edges) correspond to data dependencies(i.e. what inputs are needed to perform the operation).
For example, in complex sample evaluation (in geology, for example), the direction of the edge indicates preference. A normal preference system should not have cycles.
Tanya Natasha
so that you can always make a choice, otherwise you need to reconsider the system of preferences.
One way.
A road map with direction of travel provides special examples of directed graphs. To deal with two-way roads, instead of one road (or instead of one undirected edge), we introduce two directed edges connecting the same vertices and having opposite directions.
The question is, under what condition can the streets of the city be oriented in such a way that from any point you can go to any other without violating the rules traffic through the streets.
In the language of graph theory, it is formulated as follows: under what condition can the edges of the graph G be oriented so that for any pair of its vertices there is an oriented path connecting them?
It is clear that each such graph must be connected, but this is not enough.
The edge E = (A, B) will be called connecting edge, or isthmus if it is the only path from A to B (or vice versa).
The connecting edge divides all the vertices of the graph into two sets: those that can be reached from A without passing along the edge E, and those that can be reached from B without passing along E. The graph in this case consists of two parts G 1 and G 2 connected only by the edge E (Fig. a and a+1).
On the map of the city, the connecting rib is the only highway connecting separate parts of the city. It is clear that if one-way traffic is established on such a highway, then there would be no passage from one part of the city to another.
If the edge E i = (A i , B i) is not connecting, then there is another path that connects A i and B i and does not pass through E i . Therefore, such an edge will be called a cyclic edge.
 |
|||||
 |
|||||
fig.2 Connecting fig. 2+1 Final (connecting) Fig. 2+2 Cyclic
rib rib
Theorem 1 If G- connected graph, then it is always possible to orient the cyclic edges from G , leaving the connecting edges undirected so that any pair of vertices in this graph can be connected by a directed path.
For a city plan, this statement can be formulated as follows: if two-way traffic is left only on bridges (provided that this bridge is the only bridge across the river) and on dead ends, then on all other streets one-way traffic can be established in such a way that transport provides communication all parts of the city.
We can prove this theorem by showing a way to properly orient the graph. Let's choose in G arbitrary edge E \u003d (A, B) . If E - connecting edge, it will remain two-sided, and then it will be possible to go from BUT to IN and back (Fig. 2+3).
 |
fig.2+3 fig. 2+4
If E is a cyclic edge, then it is included in some cycle FROM, on which you can set the cyclic orientation (fig.2+4).
Suppose we have already oriented some part H count G, so that from any vertex of the graph H you can go to any other of its vertices in compliance with the rules of one-way traffic. Since the graph G is connected, then either H matches the whole graph g, or there is an edge E \u003d (A, B), which does not belong H , but one of its vertices, say BUT , belongs H .
If E - connecting rib AB , then it will remain two-sided. Then for any vertex X count H one can find an oriented chain R connecting X with A , which means (through the edge E ) , and with IN . Back from the top IN over the edge E you can go to BUT , and then - along the orienting chain Z - from BUT to X (Figure a+5). Attaching E to H , we will get most of the graph G with the required properties. If the edge E \u003d (A, B) is cyclic, it belongs to some cycle FROM . We set the direction for FROM from BUT before IN and further along FROM to the first peak D from FROM owned by H (Fig. a+6).
rice. a+5 fig. a+6
Let's add all these edges to H . Let be X - arbitrary vertex from H , but At - any vertex FROM ; one can find an oriented chain R , owned H and connecting X from BUT and then along FROM go to the top At from FROM . Back from At you can walk along FROM to the top D , and from it - belonging H oriented chain Z - from D to X . Therefore, the directed graph obtained by adding to H specified cycle edges FROM , also satisfies the required conditions. Continuing this process, we eventually orient the original graph in the required way G .
Vertex degrees.
For directed graphs, we have at each vertex the number p(A) of outgoing and the number p*(A) of incoming edges. Total number ribs is equal to:
N \u003d p (A 1) + p (A 2) + ... + p (A n) \u003d p * (A 1) + p * (A 2) + ... + p * (A n)
Available different types graphs for which degrees of vertices have some special properties. The count is called homogeneous, if the degrees of all its vertices are equal to the same number r: for each vertex A:
p(A) = p * (A) = r
The exercise
Construct homogeneous directed graphs of degree r = 2 with n = 2,6,7,8 vertices.
RELATIONS.
Relationships and Graphs.
Any mathematical system deals with a set of some objects or elements. (Signs: algebra, geometry)
In order to build mathematical theory, we need not only these elements themselves, but also relations between them. (Examples: for numbers a > b; in geometry - equality of triangles, // lines; in set theory - equality and inclusions of sets.)
All these relations concern two objects, so they are called binary relations, or simply relations, there are other types of relations, for example ternary relations relating to three objects. (For example, point A lies between points B and C).
Let's introduce general definition binary relation R: aRv - in is in relation to R to a.
For example, the relation a > b means that b belongs to the set of all numbers less than a
In fact, each directed graph G defines some relation in the set of its vertices. This ratio can be written as: аGв. It means that the graph has a directed edge going from a to b.
Special conditions.
Let some relation R be given. If an element a is in relation R with itself, then it corresponds to a loop in the graph
Relation R for which the condition аRв is satisfied for any a, is called reflective.
If the condition aRv is not satisfied for any element, then R is called anti-reflexive attitude.In this case, none of the vertices of the graph has a loop.
For each relation R, one can define inverse ratio R*, assuming that аR * в if and only if аRв.
It can be seen from the definition of the inverse relation that if the graph G corresponding to R has an edge (a, b), then the graph G * corresponding to R * must have an edge (c, a). In other words, the graph G * is inverse to G, i.e. a graph with the same edges as G, but oppositely oriented.
The relation is called symmetrical, if from аRв follows вРа.
A symmetric relation corresponds to a graph with undirected edges; conversely, a graph with undirected edges defines some symmetric relation.
The relation is called antisymmetric, if it follows from аRв that it certainly does not hold in Rа. Antisymmetric relation graphs do not have undirected or oppositely oriented edges connecting the same pair of vertices; moreover, there are no loops on them, i.e. these relations are anti-reflexive.
Ratio transitively, if it follows from the two conditions aRb and bRc that aRc.
The graph of a transitive relation has the following characteristic property: for each pair of edges (a, b), (b, c) there is closing edge. Applying this property repeatedly, we conclude that if this graph has a directed path from vertex X to vertex Y, then there is also a directed edge (x, y).
Assume that there is a graph G with directed edges that is not transitive. In all cases, a directed graph G can be made transitive by adding directed edges to it until a closure is attached for every pair of its consecutive edges. The new graph G m thus obtained is called transitive closure Count G.
Equivalence relations.
An equivalence relation, usually denoted by ~ , has the following three properties:
one). Reflexivity: a ~ a;
2). Symmetry: from a ~ to z to ~ a;
3). Transitivity: from a ~ to and to ~ c Þ a ~ c.
In fact, the equivalence relation is a generalization of the property of equality.
The equivalence relation introduces a partition into the set of vertices disjoint equivalence classes.
Let B i be the set of vertices of the equivalence graph G that are equivalent to vertex i. Then all vertices belonging to B i are connected by edges, i.e. In i - complete graph G i . At each vertex of such a graph there is a loop. The graph G splits into a set of connected components G i .
Partial order.
Attitude partial order is (on the example of sets):
one). Reflexivity: A Ê A
2). Transitivity: if A Ê B and B Ê C Þ A Ê C
3). Identity: if A Ê B and B Ê Az A = B
Strict Inclusion Relations -
one). Anti-reflexivity: A ÉA never takes place;
2). Transitivity: if A É B and B É C, then A É C
Ordering relation(in the strict sense) is called a strict ordering, a > b, for which, in addition to the previous conditions, the following also holds:
completeness condition. For any two non-coincident elements in and a, one of the two relations a>b or b>a is always satisfied.
Usually, a partially ordered graph is depicted in an ordered form. Since for any edges (a, b) and (b, c) there is a closing edge (a, c), it can be omitted.
FLAT GRAPHS.
Conditions for planar graphs.
Count Kuratovsky K 3.3
Graph problem about three houses and three wells
Count Kuratovsky K 5
These two graphs are NOT FLAT!
Graph extension- new vertices were placed on some edges, so these edges
became elementary chains consisting of several edges.
 |
||||||
 |
||||||
Reverse operation, at which separating vertices are removed from elementary chains, is called compression graph.
Kuratovsky's theorem
In order for a graph to be flat, it is necessary and sufficient that it does not contain any graph within itself that can be compressed to a K 3.3 graph or a K 5 graph.
Euler's formula
We will consider planar graphs that form on the plane polygonal networks. this means that the edges of the plane graph G form a set of polygons adjacent to each other, dividing the plane into polygonal regions.
| |
|||||||
| | |
||||||
 |
It follows from the definition of polygonal graphs that they are connected. We also require that no polygon lies inside another. The boundary edges of each such polygon form a cycle, sometimes called minimum cycle. The part of the plane enclosed within the polygon is called graph face. The graph also has maximum cycle C 1, surrounding the entire graph with all its faces. We will consider the part of the plane lying outside C 1, also as a face of a graph with boundary C 1 - endless face F ¥ .
Denote by
number of vertices, edges and faces space polygon..
Euler's theorem
c - p + r = 2
Proof: The formula is obvious for a polygon with n edges. Indeed, n vertices and n edges, as well as two faces F 1 F ¥
We add a new face to a graph with r faces by drawing along the face F ¥ some elementary chain connecting two vertices of the maximal graph G. If this arc has r edges, then we have to add r - 1 new vertices and one new face. But then
c' - p' + r' = (c + r - 1) - (p + r) + (r + 1) = c - p + r (= 2!)
by the induction hypothesis.
Matrix representations.
1. Incident matrix A.
but). For an undirected graph incidence matrix is a matrix whose rows correspond to vertices and whose columns correspond to edges. The matrix element is equal to 1 if the vertex is incident to an edge. Otherwise, the matrix element takes the value 0.
b). For a directed graph, the element of the incidence matrix is +1 when the vertex incident to the arc is the initial vertex of the arc (i.e., the arc originates from this vertex). The element is -1 when the arc enters a vertex. If the vertex is not incident to the arc, then the matrix element is 0.
2. Matrix of cycles C.
but). For an undirected graph, the rows of the cycle matrix correspond to the simple cycles of the graph, and the columns correspond to its edges. Matrix element a ij =1 if cycle С i contains edge e j . Otherwise a ij =0.
b). For a directed graph a ij =1, -1 or 0, depending on whether the orientation of the cycle C i and the arc e j is the same or opposite, or this cycle does not contain the arc e j at all.
3. The vertex adjacency matrix (or simply the adjacency matrix) V is a matrix whose rows and columns correspond to vertices, and the matrix element a ij in the case of an undirected graph is equal to the number of edges connecting vertices i and j. For a directed graph, the element a ij is equal to the number of edges directed from vertex i to vertex j.
Onovye theorems related to matrix representations of graphs.
1). The rank (maximum number of linearly independent columns) of the incidence matrix A of a connected graph (directed and undirected) with n vertices is equal to (n-1).
2). The rank of the cycle matrix C of a connected graph with m edges and n vertices is (m-n+1).
An example of using an adjacency matrix.
The following mapping shows that the graphs G 1 and G 2 are isomorphic
In adjacency matrices, rows and columns are simultaneously permuted, which can be performed using a similarity transformation and a permutation matrix.
A 2 \u003d PA 1 P", where
P = 
, or p ij =d p(i),j (Kronecker symbol)
and R" is the transposed matrix.
Finding the P matrix can be tricky.
The isomorphism of G 1 and G 2 means that A 1 and A 2 have the same eigenvalues. However, this condition is not sufficient (example below).
Before you start studying algorithms directly, you need to have basic knowledge about the graphs themselves, to understand how they are represented in a computer. Here, all aspects of graph theory will not be described in detail (this is not required), but only those, ignorance of which will significantly complicate the assimilation of this area of programming.
A few examples will give a bit of a superficial idea of the graph. So a typical graph is a subway map or some other route. In particular, a programmer is familiar with a computer network, which is also a graph. The common thing here is the presence of dots connected by lines. So in a computer network, points are separate servers, and lines are different types of electrical signals. In the subway, the first is the stations, the second is the tunnels laid between them. In graph theory, points are called peaks (knots), and the lines ribs (arcs). In this way, graph is a collection of vertices connected by edges.
Mathematics operates not with the content of things, but with their structure, abstracting it from everything that is given as a whole. Using just this technique, we can conclude about some objects as about graphs. And since graph theory is a part of mathematics, it does not matter to it at all what, in principle, an object is; the only important thing is whether it is a graph, i.e., whether it has the properties required for graphs. Therefore, before giving examples, we single out in the object under consideration only what, in our opinion, will allow us to show an analogy, we look for something in common.
Let's go back to the computer network. It has a certain topology, and can be conventionally depicted as a number of computers and paths connecting them. The figure below shows a fully meshed topology as an example.
It's basically a graph. The five computers are vertices, and the connections (signaling paths) between them are edges. Replacing computers with vertices, we get a mathematical object - a graph that has 10 edges and 5 vertices. You can number the vertices arbitrarily, and not necessarily the way it is done in the figure. It is worth noting that in this example no loops are used, that is, such an edge that leaves the vertex and immediately enters it, but loops can occur in problems.
Here are some important notations used in graph theory:
- G=(V, E), here G is a graph, V are its vertices, and E are edges;
- |V| – order (number of vertices);
- |E| – graph size (number of edges).
In our case (Fig. 1) |V|=5, |E|=10;
When any other vertex is accessible from any vertex, then such a graph is called unoriented connected graph (Fig. 1). If the graph is connected, but this condition is not satisfied, then such a graph is called oriented or a digraph (Fig. 2).
Directed and undirected graphs have the notion of the degree of a vertex. Vertex Degree is the number of edges connecting it to other vertices. The sum of all the degrees of a graph is equal to twice the number of all its edges. For Figure 2, the sum of all powers is 20.
In a digraph, unlike an undirected graph, it is possible to move from vertex h to vertex s without intermediate vertices, only when an edge leaves h and enters s, but not vice versa.
Directed graphs have the following notation:
G=(V, A), where V are vertices, A are directed edges.
The third type of graphs - mixed graphs (Fig. 3). They have both directed edges and non-directional ones. Formally, a mixed graph is written as follows: G=(V, E, A), where each of the letters in brackets also denotes what was previously attributed to it.
In the graph in Figure 3, some arcs are directed [(e, a), (e, c), (a, b), (c, a), (d, b)], others are non-directed [(e, d), (e, b), (d, c)…].
Two or more graphs at first glance may seem different in their structure, which arises due to their different representation. But it is not always the case. Let's take two graphs (Fig. 4).
They are equivalent to each other, because without changing the structure of one graph, you can build another. Such graphs are called isomorphic, i.e., having the property that any vertex with a certain number of edges in one graph has an identical vertex in another. Figure 4 shows two isomorphic graphs.
When each edge of a graph is assigned some value, called the weight of the edge, then such a graph suspended. In different tasks, various types of measurements can act as weights, for example, lengths, route prices, etc. In a graphical representation of a graph, weight values are usually indicated next to the edges.
In any of the graphs we have considered, it is possible to select a path and, moreover, more than one. Way is a sequence of vertices, each of which is connected to the next one by means of an edge. If the first and last vertices coincide, then such a path is called a cycle. The length of a path is determined by the number of edges that make it up. For example, in Figure 4.a, the path is the sequence [(e), (a), (b), (c)]. This path is a subgraph, since the definition of the latter applies to it, namely: the graph G'=(V', E') is a subgraph of the graph G=(V, E) only if V' and E' belong to V, E .
Let be V, D are arbitrary sets, and V??. Denote by V 2 Cartesian square set V.
Directed graph or, in short, digraph G called a triple V, D, c) : where c- some mapping of the set D into the set V 2. Set elements V And D are called, respectively, the vertices and arcs of the digraph G. Sets of vertices and arcs of a digraph G conveniently denoted by VG And DG respectively. If f- arc, then c(f) is an ordered pair ( and, v), where And : v J V. Arc f coming out of the top And and goes to the top v; in its turn And And v called end vertices of the arc f; in the future we will write f= (and sometimes even - f = UV if there is no danger of confusion).
When writing an arbitrary digraph, it will usually be represented as G = (V, D).
Digraphs are usually depicted using diagrams similar to diagrams for graphs. The only difference is that the line depicting the arc has a direction.
With every digraph G = (V, D) naturally connect the graph G o = (V, E), called the base of the given digraph. To obtain the basis, it is necessary in the digraph G replace every arc f= edge e = uv
On fig. 8 shows the digraph and its base
Figure 8
digraph G is called connected if its base is connected. An oriented route, or, in short, a route in a digraph G is called an alternating sequence of vertices and arcs
Wherein
This route is called (v about , v t) - standard route; peaks v o And v t are called, respectively, the initial and final vertices of such a route. If v o = v t, then the or-route is called closed. The number of arcs that make up the pattern is the length of the pattern.
A path without repeating arcs is called an orchain. A simple orchain is an orchain with no repeating vertices (except perhaps the same start and end vertices). A closed simple orchain is called an orcycle or contour.
It is easy to check that the existence (and, v;) - orroute guarantees the existence of a simple ( and, v) - orcepi.
They say that the top v reachable from top And, if exists ( and, v) route. digraph G is strongly connected or op-connected if any of its vertices is reachable from any other vertex. Obviously, a strongly connected digraph is connected; the converse is, of course, not true.
Graph G is called orientable if it is the base of some strongly connected digraph.
Theorem 1.3. Connected graph G is orientable if and only if each of its edges is not a bridge.
Proof. Let the count G is the base of the digraph H And G contains a bridge e. Then in H there is an arc f=, where and, v- rib ends e. Obviously in H No ( u, v) - routes. Therefore, graph G is not orientable.
Back, let the count G has no bridges, i.e. each edge of the graph G contained in a cycle. Since any cycle is an orientable graph, in the graph G there is a maximal orientable subgraph H. Let's make sure that H = G. Assume that this equality is not satisfied. Due to the connectedness of the graph G there is an edge e incident to the vertex v from H and not lying in H. By assumption, the edge e lies in some cycle FROM. Denote by Q the set of cycle edges that do not belong to the subgraph H. It is easy to see that, adding to H all edges from the set Q, we again obtain an orientable subgraph, in contradiction to the choice H.
Let be G is an arbitrary digraph. Degree of outcome degv peaks v is the number of all arcs having v as a start. Similarly, the degree of entry degv is the number of all arcs for which the vertex v is the end. Digraph containing P peaks and T arcs will be called ( n, t) is a digraph.
The out-degrees and in-degrees are related in the following obvious way.
Lemma 1. Let be G- arbitrary ( n, t) is a digraph. Then
This assertion is similar to Lemma 1 from Sec. 1.1; it is often referred to as the handshake orlemma.
In the previous chapters, we presented some of the main results of the theory of undirected graphs. However, undirected graphs are not enough to describe some situations. For example, when representing a traffic map with a graph whose edges correspond to streets, an orientation must be assigned to the edges to indicate the permissible direction of movement. Another example is a computer program modeled by a graph whose edges represent the flow of control from one set of instructions to another. In this representation of the program, the edges must also be given an orientation to indicate the direction of control flow. Another example of a physical system that requires a directed graph to represent is an electrical circuit. Applications of directed graphs and related algorithms are discussed in Chap. 11-15.
This chapter presents the main results of the theory of directed graphs. Questions related to the existence of oriented Euler chains and Hamiltonian cycles are discussed. Oriented trees and their connection with oriented Euler chains are also considered.
5.1. Basic definitions and concepts
Let's start by introducing some basic definitions and concepts related to directed graphs.
A directed graph consists of two sets: a finite set V, whose elements are called vertices, and a finite set E, whose elements are called edges or arcs. Each arc is associated with an ordered pair of vertices.
Symbols are used to designate vertices, and symbols are used to designate arcs. If , then are called end vertices, where - initial vertex, - end vertex . All arcs that have the same pair of start and end vertices are called parallel. An arc is called a loop if the incident vertex is both its start and end vertex.
In a graphical representation of a directed graph, vertices are represented by dots or circles, and edges (arcs) are represented by segments.
lines connecting dots or circles representing their endpoints. In addition, the arcs are assigned an orientation, indicated by an arrow pointing from the start vertex to the end vertex.
For example, if such that Theirs), a directed graph can be represented by fig. 5.1. In this graph - parallel arcs, and - loop.
Rice. 5.1. Oriented Graph.
An arc is said to be incident to its end vertices. Vertices are called adjacent if they are terminal for one arc. If the arcs have a common terminal vertex, then they are called adjacent.
An arc is called outgoing from its initial vertex and entering its final vertex. A vertex is said to be isolated if it has no incident arcs.
The degree of a vertex is the number of arcs incident to it. The in-degree of a vertex is the number of arcs entering V] and the out-degree is the number of outgoing arcs. The symbols and b" denote the minimum out-degree and in-degree of the directed graph. Similarly, the symbols denote the maximum out-degree and in-degree, respectively.
The sets of any vertex are defined as follows: . For example, in the graph in Fig. 5.1.
Note that the loop increases the half-degrees of both entry and exit of this vertex. The following assertion is a consequence of the fact that each arc increases by 1 the sum of the semidegrees of both the input and output of a directed graph.
Theorem 5.1. In a directed graph with arcs
Sum of in-degrees = Sum of out-degrees = m.
Subgraphs and generated subgraphs of a directed graph are defined in the same way as in the case of undirected graphs (Sec. 1.2).
An undirected graph resulting from the removal of orientation from the arcs of a directed graph G is called the underlying undirected graph G and is denoted by .
A directed path of a directed graph is a finite sequence of vertices
What is an arc of the graph G. Such a route is usually called a directed -route, and the initial vertex is the final vertex of the route, and all other vertices are internal. The start and end vertices of a directed path are called its end vertices. Note that arcs, and hence vertices, may appear more than once in a directed path.
An oriented route is said to be open if its end vertices are different, otherwise it is called closed.
An oriented path is called an oriented path if all of its arcs are distinct. An oriented path is open if its endpoints are distinct, otherwise it is closed.
An open oriented path is called an oriented path if all its vertices are distinct.
A closed oriented chain is called an oriented cycle or contour if its vertices, with the exception of the terminal ones, are different.
A directed graph is said to be acyclic or contourless if it has no contours. For example, the directed graph in Fig. 1 is acyclic. 5.2.
Rice. 5.2. Acyclic directed graph.
Rice. 5.3. A strongly connected directed graph.
A sequence of vertices in a directed graph G is called a path in G if it is a path in the underlying undirected graph. For example, the sequence in the graph in Fig. 5.2 is a route, but not oriented.
The chain, path, and cycle of a directed graph are defined similarly.
A directed graph is said to be connected if the underlying undirected graph is connected.
A subgraph of a directed graph G is called a component of the graph G if it is a component of the graph
Vertices of a directed graph G are said to be strongly connected if there are directed paths from and back to G. If is strongly connected to then, obviously, is strongly connected to . Every vertex is strongly connected to itself.
If a vertex is strongly connected to a vertex, then, as is easy to see, the vertex is strongly connected to the vertex. Therefore, in this case, one simply says that the vertices are strongly connected.
A directed graph is said to be strongly connected if all its vertices are strongly connected. For example, the graph in Fig. 5.3.
The maximal strongly connected subgraph of a directed graph G is called a strongly connected component of G. If a directed graph is strongly connected, then it has a single strongly connected component, namely itself.
Consider a directed graph. It is easy to see that each of its vertices belongs to exactly one strongly connected component of the graph G. Therefore, the sets of vertices of strongly connected components form a partition of the vertex set Y of the graph
Rice. 5.4. Graph and its condensation.
For example, the directed graph in Fig. 5.4, a has three strongly connected components with vertex sets and forming a partition of the vertex set of a directed graph.
Interestingly, a directed graph may contain arcs that are not included in any strongly connected components of the graph. For example, no strongly connected components include arcs in the graph in Fig. 5.4, a.
Thus, although the "strongly connected" property entails splitting the vertex set of the graph, it may not generate splitting the set of arcs.
Union, intersection, mod 2 sum, and other operations on directed graphs are defined in exactly the same way as in the case of undirected graphs (Sec. 1.5).
The graph resulting from the contraction of all arcs of strongly connected components of a directed graph G is called the condensed graph of G. The condensation of the graph shown in fig. 5.4, a, is shown in fig. 5.4b.
The vertices of the graph correspond to strongly connected components of the graph G and are called condensed images of the components.
The rank and cyclomatic number of a directed graph are the same as those of the corresponding undirected graph. This means that if a directed graph G has arcs, vertices, and components, then the rank and cyclomatic number of the graph G are given by
We now define minimally connected directed graphs and study some of their properties.
A directed graph G is said to be minimally connected if it is strongly connected, and removing any arc deprives it of its strongly connected property.
Rice. 5.5. Minimally connected directed graph.
Minimally connected is, for example, the graph shown in Fig. 5.5.
Obviously, minimally connected graphs cannot have parallel arcs and loops.
We know that an undirected graph is minimally connected if and only if it is a tree (Ex. 2.13). By Theorem 2.5, a tree has at least two vertices of degree 1. Therefore, minimally connected undirected graphs have at least two vertices of degree 1.
Let us establish a similar result for directed graphs. The degree of any vertex of a strongly connected directed graph must be at least 2, since each vertex must have outgoing and incoming arcs. In the following theorem, we prove that a minimally connected directed graph has at least two vertices of degree 2.
