Graphs in informatics: definition, types, applications, examples. Theory of graphs in computer science

Graphs in informatics are a way of defining relationships in a combination of elements. These are the main objects of the study of graph theory.

Basic Definitions

What is the graph in computer science? It includes a set of objects called vertices or nodes, some pairs of which are associated with so-called. Ribs. For example, the graph in Figure (a) consists of four nodes, designated A, B, C, and D, of which B is connected to each of the other three vertices by edges, and C and D are also connected. Two nodes are adjacent if they are connected by an edge. The figure shows a typical way of how to build graphs in informatics. Circles represent the vertices, and the lines connecting each pair of them are ribs.

What graph is called non-oriented in computer science? His relationship between the two ends of the rib is symmetrical. The rib simply connects them to each other. In many cases, however, it is necessary to express asymmetric relationships - for example, the fact that A points to B, but not vice versa. This goal is the definition of a graph in computer science, still consisting of a set of nodes, along with a set of oriented edges. Each oriented edge is a connection between vertices, the direction of which has a value. Directed graphs are represented as shown in figure (b), their edges are represented by arrows. When it is required to emphasize that the graph is non-directional, it is called undirected.

Models of networks

Graphs in computer science serve as a mathematical model of network structures. The following figure shows the structure of the Internet, then called ARPANET, in December 1970, when it had only 13 points. Nodes are computing centers, and the edges connect two vertices with a direct connection between them. If you do not pay attention to the superimposed map of the USA, the rest of the image is a 13-node graph similar to the previous ones. In this case, the actual arrangement of the vertices is insignificant. It is important which nodes are connected to each other.

The use of graphs in computer science allows you to imagine how things are either physically or logically related to each other in the network structure. The 13-node ARPANET is an example of a communication network in which computer vertices or other devices can transmit messages, and the edges are direct links over which information can be transmitted.

Routes

Although graphs are used in many different areas, they have common features. The theory of graphs (computer science) includes, perhaps, the most important one - the idea that things often move along the edges, consistently passing from node to node, whether it be a passenger of several flights or information transferred from person to person in a social network, or the user Computer, sequentially visiting a number of web pages, following the links.

This idea motivates the definition of a route as a sequence of vertices connected by edges. Sometimes it becomes necessary to consider a route that contains not only nodes, but also the sequence of edges connecting them. For example, the sequence of vertices MIT, BBN, RAND, UCLA is a route in the graph of the Internet ARPANET. The passage of nodes and edges can be repeated. For example, SRI, STAN, UCLA, SRI, UTAH, MIT is also a route. The path in which the edges do not repeat is called a chain. If nodes are not repeated, it is called a simple chain.

Cycles

Especially important types of graphs in computer science are cycles, which represent a ring structure, such as the sequence of nodes LINC, CASE, CARN, HARV, BBN, MIT, LINC. Routes with at least three edges, in which the first and last node are the same, and the others are different, are cyclic graphs in computer science.

Examples: the cycle SRI, STAN, UCLA, SRI is the shortest, and SRI, STAN, UCLA, RAND, BBN, UTAH, SRI is much larger.

In fact, every edge of an ARPANET graph belongs to a cycle. This was done intentionally: if any of them fails, there will be the possibility of moving from one node to another. Cycles in communication and transport systems are present to provide redundancy - they provide alternative routes along a different path path. In the social network, cycles are also often seen. When you find, for example, that a close school friend of your wife's cousin is actually working with your brother, this is a cycle that consists of you, your wife, her cousin, his school friend, his employee (ie your Brother) and, finally, again you.

Connected graph: definition (informatics)

It is natural to ask whether it is possible to get from each node to any other node. A graph is coherent if there is a route between each pair of vertices. For example, the ARPANET network is a connected graph. The same can be said about most communication and transport networks, since their goal is to direct traffic from one node to another.

On the other hand, there is no a priori reason to expect that these types of graphs in computer science are widespread. For example, in a social network it is not difficult to imagine two people who are not connected with each other.

Components

If the graphs in the computer science are not connected, then they naturally decompose into a set of related fragments, groups of nodes that are isolated and non-intersecting. For example, the figure shows three such parts: the first - A and B, the second - C, D and E, and the third consists of the remaining vertices.

The components of a graph connectivity are a subset of nodes in which:

• Each vertex of the subgroup has a route to any other;
• A subset is not part of a larger set in which each node has a route to any other.

When graphs in computer science are divided into their components, this is only the initial way of describing their structure. Within this component there can be a rich internal structure that is important for the interpretation of the network. For example, a formal method of determining the importance of a node is to determine how many parts the graph divides, if the node is removed.

Maximum component

There is a method of qualitative evaluation of connectivity components. For example, there is a worldwide social network with connections between two people, if they are friends.

Is she connected? Probably not. Connectedness is a fairly fragile property, and the behavior of one node (or a small set of them) can nullify it. For example, one person with no live friends will be a component consisting of a single vertex, and therefore the graph will not be coherent. Or a remote tropical island, consisting of people who have no contact with the outside world, will also be a small component of the network, which confirms its incoherence.

A global network of friends

But there's something else. For example, the reader of a popular book has friends who grew up in other countries and makes up one component with them. If you take into account the parents of these friends and their friends, then all these people are also in the same component, although they have never heard of the reader, speak a different language and have never been with him. Thus, while the global friendship network is not coherent, the reader will enter into a very large component that penetrates into all parts of the world, including people from very different backgrounds and, in fact, containing a large part of the world's population.

The same is true for network data sets-large, complex networks often have a maximum component that includes a significant portion of all nodes. Moreover, when the network contains the maximum component, it is almost always only one. To understand why, we should return to the example with a global network of friendship and try to imagine the presence of two maximal components, each of which includes millions of people. It will require the presence of a single edge from one of the first component to the second, so that the two maximal components merge into one. Since the edge is unique, in most cases it is unbelievable that it does not form, and therefore the two maximal components in real networks are never observed.

In some rare cases, when the two maximal components coexisted for a long time in a real network, their unification was unexpected, dramatic, and, ultimately, had catastrophic consequences.

Component Fusion Crash

For example, after the arrival of European researchers in the civilization of the Western Hemisphere, about half a millennium ago, a global cataclysm occurred. From the network point of view, it looked like this: for five thousand years the global social network probably consisted of two giant components - one in North and South America, and the other in Eurasia. For this reason, technology developed independently in two components, and, even worse, human diseases, etc., also developed. When the two components finally came into contact, the technologies and diseases of one quickly and catastrophically filled the second one.

American High School

The concept of maximal components is useful for reasoning about networks and in much smaller sizes. An interesting example is a graph illustrating the romantic relationship in American high school for an 18-month period. The fact that it contains the maximum component is important when it comes to the spread of sexually transmitted diseases, which was the purpose of the study. Pupils may have had only one partner for this period of time, but nonetheless, without realizing this, they were part of the maximum component and therefore part of many potential transmission routes. These structures reflect relationships that may have long since ended, but they link individuals in chains for too long to become the subject of close attention and gossip. Nevertheless, they are real: as social facts are invisible, but logically flowing macrostructures that arose as a product of individual mediation.

Distance and width search

In addition to the information about whether two nodes are connected by a route, the graph theory in computer science makes it possible to learn about its length - in transport, communication or in the dissemination of news and diseases, as well as whether it passes through several peaks or a multitude.

To do this, determine the length of the route, equal to the number of steps it contains from beginning to end, that is, the number of edges in the sequence that makes it. For example, the route MIT, BBN, RAND, UCLA has a length of 3, and MIT, UTAH is 1. Using the length of the path, one can say whether two nodes are located in a graph close to each other or far: the distance between two vertices is defined as the length The shortest path between them. For example, the distance between LINC and SRI is 3, although to make sure of this, you should make sure there is no length equal to 1 or 2 between them.

The search algorithm is wide

For small graphs, the distance between two nodes can be easily calculated. But for complex ones, there is a need for a systematic method of determining distances.

The most natural way to do this and, therefore, the most effective, is the following (on the example of a global network of friends):

• All friends are declared to be at a distance of 1.
• All friends of friends (not including those already marked) are declared to be located at a distance of 2.
• All of their friends (again, not counting tagged people) are declared remote by a distance of 3.

Continuing this way, the search is carried out in subsequent layers, each of which is one unit beyond the previous one. Each new layer is made up of nodes that have not yet participated in the previous ones, and which enter the edge with the top of the previous layer.

This technique is called a width search, since it searches the graph outwards from the starting node, first of all covering the nearest ones. In addition to providing a way to determine the distance, it can serve as a useful conceptual basis for organizing the structure of the graph, as well as how to build a graph in informatics, placing the vertices based on their distance from a fixed starting point.

Search in width can be applied not only to the network of friends, but also to any graph.

The world is small

If you go back to the global network of friends, you can see that the argument explaining the ownership of the maximum component, in fact, says something more: not only the reader has routes to friends that connect him with a large proportion of the world's population, but these routes are surprisingly short .

This idea was called "the phenomenon of a close world": the world seems small, if you think about what a short route connects any two people.

The theory of "six handshakes" was first experimentally investigated by Stanley Milgram and his colleagues in the 1960s. Not having any set of social networking data and with a budget of 680 dollars, he decided to test the popular idea. To this end, he asked 296 randomly selected initiators to send a letter to a stockbroker who lived in a suburb of Boston. The initiators were given some personal information about the purpose (including address and profession) and they had to forward the letter to a person they knew by name, with the same instructions that it reached the goal as quickly as possible. Each letter passed through the hands of a number of friends and formed a chain that closed on an exchange broker outside of Boston.

Among the 64 chains that reached the goal, the average length was six, which was confirmed by the number named two decades earlier in the title of the play by John Gare.

Despite all the shortcomings of this research, the experiment demonstrated one of the most important aspects of our understanding of social networks. In subsequent years, he made a broader conclusion: social networks, as a rule, have very short routes between arbitrary pairs of people. And even if such indirect links with business leaders and political leaders do not pay off on a daily basis, the existence of such short routes plays a big role in the speed of the dissemination of information, diseases and other types of infection in society, as well as in the access opportunities that the social network provides to people with Completely opposite qualities.