Just about the graphs. Attempt to popularize

"Any titles (nobleman, merchant, tradesman, peasant, etc., titles - princely, count, etc.) and the name of civil ranks (secret, state and other advisers) are destroyed ..."

On the destruction of estates and civil ranks
Decree of the All-Russian Central Executive Committee and SOVNARKOM of 10.11.1917, art. 2

---

Somehow I did without it before ...

Is there any use to the ordinary programmer or, say, the layman from graph theory, or is this a purely sacred thing from arrogant mathematical abstractions?

It is likely that the specifics of “ randomly distributed graphs ” will turn out to be of little demand in our everyday life, but some idea of ​​graph theory may turn out to be useful in a wide variety of situations, even for a person not particularly interested in mathematics — as for people working in the field of programming , then sophisticated ingenuity, as a rule, accompanies daily tasks falling to their lot, therefore, representatives of this profession, in search of new ideas and tools, happens to recklessly load ryut their mind with things that would seem unsuitable for useful use, however,ordering pizza for 10 thousand bitcoins , they give a good mood to other good people for many years, and yet they justify their passion.

Well, let’s say that we consider ourselves to be quite serious people and intend to seriously turn a small fraction of knowledge to our advantage, which we are hard to accumulate and, with the years with increasing work, keep in our heads. And the luxury of careless oblivion once we have learned the information we resolutely reject.

A graph can be a great visualization tool.ideas that have visited you. Every day we solve any problems that can be adequately written in the language of graphs, but often do not feel the need to manipulate visual images. Sometimes it is the visual image that has the necessary effect on our mental concentration, which leads us to a bright idea. - Often it is useful to look at things from different angles.

The graph may turn out to be the spokesman for the essence of some idea and shorten your path to the final goal (if you thought about sad things now, I didn’t mean that).
It often happens that we use, not consciously, intuitively, some methods of solving problems that arise before us, which are user patterns prompted by previous experience, and meanwhile, these methods, cast into an idea, put into a paradigm, turned into a concept, can become powerful a tool that shows us both the direction and the way to solve a whole class of problems united by a common symptom.

Graph theory currently contains quite a lot of effective tools for solving an equally wide range of problems. However, the tools and ideas that today relate to the field of discrete mathematics called graph theoryto this day remain in some eclectic unity, as it were, without violent compulsion. The range of issues solved by graph theory, and the variety of models used for this and the mechanisms for solving them are so vast that attempts to popularize graph theory as a whole should be based on considerable audacity. An academic and in-depth presentation of the specific nuances of graph theory will not be the purpose of this article. Our intention is to talk only about what we have found useful (or relatively useful) and not boring application.

And by the way, "where does it come from" graph theory?

We will pay tribute to great names and briefly turn to historical retrospectives.

... This is a decision in nature; apparently, it has little relation to mathematics, and it is not clear to me why one should expect this solution from a mathematician rather than from any other person, because this solution is supported by reasoning alone and there is no need to use any laws to find this solution peculiar to mathematics.

From a letter from Leonard Euler to his friend Karl Gottlieb Ehler, April 03 [14], 1736^{[ 1 ]} Fig. 1. Königsberg on an engraving of the 17th century. It is believed that graph theory began to take shape as an independent mathematical discipline after Euler's indicative solution to the “ seven-bridge problem”, a purely logistic problem, —application of graph theory to the solution of the “ four-colored cubes problem ”





", на мой взгляд, требовало значительно большей изобретательности и большой искушенности в предмете, достигаемыми лишь постоянными упражнениями в практическом применении теории графов, хотя, к моменту решения последней из упомянутых задач от цитируемой переписки минуло более двух веков, и предмет новой дисциплины, лишь туманно виденной Эйлером, успел приобрести очертания вполне конкретные и накопить некоторый опыт практического применения усилиями выдающихся ученых, развивавших идеи Эйлера.

[Рис. 1 может дать некоторое представление о «задаче», упоминаемой в процитированной фразе.] Частью городской коммуникации и архитектурного ансамбля города Кёнигсберга в 1736 году являлись 7 мостов (эти старые мосты не сохранились) через реку Прегель. Трудно сказать, насколько широко была распространена загадка о том, is it possible to go through all seven bridges without having crossed two of them twice , and whether the city services seriously thought about approving such a route for city guests and citizens, but this mystery managed to attract the attention of Leonard Euler - however, it remained the only fairly long time a well-known example of the application of the method proposed by the great mathematician. For more than a hundred years, Euler’s work did not cause much interest in the scientific community. The term "count" was introduced by the Hungarian mathematician Denish König only in 1936.

I was once offered the task of an island located in the city of Königsberg and surrounded by a river through which seven bridges are thrown. The question is whether someone can continuously go around them, passing only once through each bridge. And then I was informed that no one has yet been able to do this, but no one has proved that this is impossible.

This question, although banal, seemed to me, however, worthy of attention in that neither geometry, nor algebra, nor combinatorial art were sufficient for its solution.

From a letter from Leonard Euler to Giovanni Jacobo Marinoni, March 13 [24], 1736^{[ 2 ]}



(Judging by the letters of Leonard Euler, the great scientist, not without pleasure, also solved other puzzling problems ..)

The seven bridges problem

Her decision is set out in detail in letters to Elera and Marinoni.

Finally, you, the most glorious husband, express a desire to become familiar with my way of building bridges; I willingly present this method to your court. For when you asked me for a solution to this problem, adapted to the special case of Koenigsberg, you probably thought that I proposed this kind of construction of bridges, but I didn’t do it, but only proved that such a construction cannot take place at all, and this should be taken instead of a decision. My method is universal, because with it, in any case of this kind proposed to me, I can immediately decide whether to build a transition using separate bridges or not, and in the first case [I can establish] how this transition should be implemented. Next, I will outline my method, and also describe the path by which I came to him.

Karl Gottlieb Ehler, 03 [14] April 1736

I examined an arbitrary figure of the branching of the river, as well as bridges a, b, c, d, e, f, as indicated in the figure, and found that a transition is possible, which I represent as follows. The areas separated from each other by water, I call the letters A, B, C, and when it is supposed to go through bridges from one area to another, [namely] the transition from A to B through a bridge or a or b, it is most convenient to call [ letters] AB, of which the first letter A will denote the area from which they cross. So, ABCASAV will determine the transition made through all bridges once; the number of these letters should be one more than the number of bridges; this should take place at any possible transition in the described way, which is easier for everyone to verify for themselves than to prove. Now I consider how many times in a series of letters A, B, C, A, C, A, The letters ABC should meet, which should be judged by the number of bridges leading to each of the areas. So, five bridges lead to area A: a, b, c, d, e, and how many times the letter A occurs in the middle of that row, so many times two of these bridges meet, because on the one hand you need to go to area A, on the other parties - get out of there. If A occurs either at the beginning or at the end of that row, then the only bridge crossing corresponds to A. It follows that if the number of bridges leading to area A is odd, then the transition across all bridges cannot be made otherwise than in this way so that it either starts in area A, or ends in area A. And if the number of bridges leading to A is even, then the transition can be completed without this condition, to start or end in A, but if it starts in A , it will have to end there too. It follows that in the ABCASAV series, any letter, with the exception of the first and last, denotes a transition leading through two bridges to the area designated by this letter.

Therefore, we must adhere to the following rule: if in any figure the number of bridges leading to a certain region is odd, then the desired transition through all bridges at the same time cannot be carried out otherwise than if the transition either begins or ends in this region. And if the number of bridges is even, there can be no difficulty, since neither the beginning nor the end of the transition is fixed. Hence follows this general rule: if there are more than two areas to which an odd number of bridges leads, then the desired transition cannot be made at all. For it seems completely impossible for the transition to begin and end in any one of these areas. And if there are only two areas of this kind (since one area of ​​this kind or an odd number of areas cannot be given), then a transition through all bridges can be completed, but with the condition that the beginning of the transition be in one and the end in the other of these areas. When in the proposed figure A and B there are areas to which an odd number of bridges leads, and the number of bridges leading to C is even, then I believe that the transition or the construction of bridges can take place if the transition starts either from A or from B, and if someone wants to start the transition from C, then he will never be able to achieve the goal. In the location of the Konigsberg bridges, I have four areas A, B, C, D, mutually separated from each other by water, each of which leads to an odd number of bridges. and the number of bridges leading to C is even, then I believe that a transition or building bridges can take place if the transition starts from either A or B, but if someone wants to start the transition from C, then he never will not be able to achieve the goal. In the location of the Konigsberg bridges, I have four areas A, B, C, D, mutually separated from each other by water, each of which leads to an odd number of bridges. and the number of bridges leading to C is even, then I believe that a transition or building bridges can take place if the transition starts from either A or B, but if someone wants to start the transition from C, then he never will not be able to achieve the goal. In the location of the Konigsberg bridges, I have four areas A, B, C, D, mutually separated from each other by water, each of which leads to an odd number of bridges.

Thus, since there are more than two areas to which an odd number of bridges leads, I argue that I have proved the complete impossibility of such a bridge connection. So, with the help of a very easy rule, you can almost instantly determine for any figure, is it possible to build bridges of this kind in which the transition will occur only through all bridges at the same time, or not? For it will be possible to build, if there is no area, or only two, to which an odd number of bridges will lead; in such cases, the beginning of the transition is chosen arbitrarily, but there must also be the end of the transition. In the latter case, the beginning of the transition should take place in one of those areas, and the end in the other. Building is impossible if there are more than two areas to which an odd number of bridges will lead.

 

Fig. 2. Count of Konigsberg bridges.
Fig. 3. The puzzle "Envelope".

Therefore, you can make sure, my dear husband, that this decision by its nature, apparently, has little to do with mathematics, and I don’t understand why one should expect this solution from a mathematician rather than from any other person, because this solution It is supported only by reasoning and there is no need to use any laws typical of mathematics to find this solution. So, I do not know how it turns out that questions that have very little relation to mathematics are more likely to be solved by mathematicians than by other [scientists]. Meanwhile, you, the most illustrious husband, determine the place of this question in the geometry of the situation, and as for this new science, I confess I do not know what kind of tasks related here were desirable to Leibniz and Wolf. So I ask you if you think that I am able to create something in this new science, so that you would deign to send me some specific tasks related to it, so that I can better understand for myself what exactly seems desirable. Meanwhile, since I know that you can also make a judgment about the mathematical sciences on the basis of only one task that should be proposed and solved, the beginning of which, at Your request, the glorious Kühn proposed, I would like him to present us with such problems that he considers it more difficult [to do so] both for the progress of science and for the exercise of our forces.

The above reasoning of Leonard Euler hardly caused you awe, which, for example, is completely excusable for a person who is somewhat involved in mathematics, admiringly examines the consequences of Euler’s spectacular formula for complex numbers.


However, one can be impressed by a simple enumeration of the merits of this great man before science ...

However, already very three hundred years ago, the “problem of the Königsberg bridges” ( Fig. 2 ) reminds you of the “envelope” that you successfully painted in “one pass” in elementary grades ( Fig. 3 ), with each new way you open, draw this “envelope” multiplying your triumph over classmates competing with you in this lesson.

How many routes will you find today? I believe that Euler’s letters carefully read above will not be mistaken in choosing starting points for constructing their routes (did you have such a hint in the first class?), And it’s not difficult to predict where their routes will end. At the same time, finish the eighth bridge in the "city of thinkers" and fill the desired walks with its residents.

And there could be more bridges ...

In Henry E. Dudeney's booklet “520 Puzzles” (I have a 1975 edition, Mir Publishing House, Moscow^{[ 3 ]} ) there are many problems that can be solved directly according to Euler’s instructions. Let us take a look at one of such problems, which is assigned the number 408 in the indicated edition.

Euler armed us with a reliable technique, and we will solve the Dudeny problem No. 408 without difficulty. However, frankly, when this book started up with me, I had no idea about Euler's recommendations.

• 408. Twenty-two bridges. You see here a diagram of the district with a developed system of irrigation facilities, on which numerous canals and bridges are indicated. A person leaves one of the sections marked with letters to visit a friend living in another section. Desiring to make a exercise at the same time, he goes through each bridge once and only once.

• The puzzle is to find out what areas are located at home buddies. It will seem extremely simple to you if you think about it for a few minutes. Of course, you should not go beyond the boundaries of the scheme.

Right here is "extremely simple"? ..
...
What if I want to take into account the schedule of city attractions in my route? - For example, part of the bridges along my route are movable, and every time I go over them, I’m annoyed that I can’t admire their mechanics in action, or, on the contrary, it is this feature of them that drives my step in order to pass these bridges before the command hours.

Knowing the path indicated to us by the great mathematician, we are, perhaps, capable of some independent steps. As often happens, if part of the problem is decided for us, the rest of the solution already seems easier. Knowing where to take the first step, I can probably write a short instruction for counting or even dispatching possible routes.


Total routes, there are 67344 options. A bit too much, but true friendship should be able to endure so many visits, it remains to find "real" shoes, because this is a test for her.

Paths and trees

Graphic schemes, of course, are not exhausted by closed routes, and our path leads us to trees ...

Since 1978, in a world that lies beyond your computers, here and there, and never here, there are quiet or even almost secret meetings of strangers with me (I guess) people called International Puzzle Party . You can receive an invitation to this event only from a member of this private club. Where and when the next meeting will take place is never known outside the club. If you believe the laconic announcement of the official IPP website, then nothing more dangerous than the handshakes of puzzle collectors on the "party" themselves. However, after the fact of the secret meeting, other mortals happen to see the catalogoutlandish puzzles carefully inspected by the committee of this elite forum, sophisticated in puzzle tasks. One of these puzzles, presented at IPP 37 in Paris in August 2017 (did you also feel attracted to collecting puzzles?), Was proposed by a participant in the “non-joint puzzles forum” (I am ignorant of its international movements) as a warm-up for the brain before such leisure to colleagues.

This puzzle seemed to me somewhat reminiscent of the Dudeney task, burdened, however, by several nuances.

The developer (creator, creator, creator, demiurge) of this sample of extraordinary thought, a masterpiece of sophisticated human ingenuity was noted Donghoon Pee - the creator, apparently a modest and undeservedly little-known here on Habré - we will correct the last injustice, although, of course, we will destroy the intrigue ... Me and myself it’s a pity to deprive Habr’s readers of the opportunity to independently think over the 2 & 1 puzzle by Donghoon Pee - I can only advise those who are eager to solve the puzzle on their own, close their palms with drawings and partly puzzle text below.

Donghoon Pee (Dongong Pi is the most probable reading, but in order to not risk it, I will use the Latin spelling) has his own channel on youtube.com, a Facebook page, he lives in the city of Seoul and is a professional creator (the language does not turn to say “designer ", Although he himself so calls his occupation) of puzzles. And his work has repeatedly received the attention of the IPP club. Hopefully, the income of this absolutely worthy person will not be affected by this publication.

• Five tiles of various shapes must be placed on a green field of a strictly defined size, each of which consists of two colors. The central cell in the field is three-colored - only the corresponding tile color can contact any of the colors of this cell, i.e. if the side strip of the central cell is colored red, the tile should not touch this side surface of the cell other than red. The goal of the puzzle: to lay all five tiles on the playing field so that each of the three colors of the tile elements forms an inextricable color field.

If we continue the analogy with islands and bridges, then, dividing the field into cells, we can consider these cells “islands” between which we transfer “bridges” -tiles. Not to say that our “bridges” will serve anyone as an example of architecture, but, for our narrow task, such a convention is quite appropriate. By restricting the conditions for “building bridges” to the requirement of matching matching colors in different tiles, and introducing the criterion of “color continuity” (well, it would be logical, of course, to start “building” from the central cell), we can start the recursive construction of the tree graph , which will not be particularly long, due to the insignificance of the "building material". The root of our tree is the central cell, and in any node of such a treemultiple branching is permissible .



A small modification of the problem can turn it into a tight packing problem, etc., but within recognizable limits, we can adhere to the model allowed by graph theory. Of course, with the increasing severity of the task, it may be necessary to take into account the algorithmic complexity and limitations of the recursive mechanism.

Four color dice challenge

Let's try to give our review the appearance of a little more academic, for which we again turn to the "puzzle with four colored cubes . "

Solving this puzzle by the usual brute force method, we resort to a method that promises us 41,472 iterations. The most elegant solution in the graphs will require enumeration of combinations of four cubes described by three pairs of colors. - The difference is palpable. Let me remind you of an easily algorithmizable procedure: the

cube graph in this puzzle is a graphical model with 4 colors in 4 nodes, and each edge indicates / connects a pair of opposite faces: a witty thought that occurred to F. De Carteblanche (Cedric AB Smith) consisted of two sets of four colors in eachcan be described in the form of a graph with nodes of degree 2 , where the nodes themselves mean colors, and the edges of the graph indicate that the pair consists of different, but not one , sets - correlating the pair with the parent cube ( by numbering the edges ), we get Unambiguous directions for placement in the pyramid of this set of faces.

Having instructions for the second set - i.e. for the second pair of faces of the pyramid, we can finally assemble the combination that is the solution to the puzzle. Thus, selecting two subgraphs from the multigraph (the totality of the graphs of cubes)pointing to different sets of colors - and for this it is enough that the same edge (since it is the edge that indicates the connection) is not used simultaneously in each of the graphs - we will get an easily readable solution to the puzzle: for us, for example, according to the first instruction arrange the cubes in accordance with the "top-bottom" and bring them in accordance with the second instruction, turning left and right. [Let me remind you that the “loop” is also a node of the 2nd degree]. Of all the subgraphs shown in the figure, only two form a pair with mismatched edges. This is the so-called “only solution” to the “right” puzzle.


It is not superfluous, probably, to consider in detail the example of a multi-graph scan for a beautiful assembly that has 24 positions on each of its sides with all 4 colors (the “wrong” puzzle, it was presented in Fig. 6 at the previous publication of the previous publication ): three subgraphs (in the left figure, these are the three leftmost subgraphs ) can add up in three pairs with diverging edges - an assembly with “three solutions” in the terminology common in the English language environment.

If I need to “catch symmetrical assemblies” in some, relatively speaking, “stream of cubic entities”, I will try to avoid trivial enumeration. For example, from cubes whose sweeps are shown onFig. 2 of the same publication, you can quickly add 16 sets with “three solutions”.

The graph points us to an internal connection, to the unique nature of some of the things we are studying. It is quite natural to take advantage of the noted feature, especially if the model promises us some advantage in comparison with other ways of solving the problem.

 

Reverse modeling

Is it possible to move from the desired graphical model to a concrete implementation of anything? - There is hardly an unambiguous answer, but in most cases I would advise you not to try to make such transitions, unless the model you are looking for is limited to the features fully described within the framework of the graphic prototype. Describing an object from the real world, you neglect a part of its properties in front of one essential feature, for the sake of the model you have chosen.

For example, in 1073 unique sets of cubes, four each have a smaller number of unique graphs corresponding to these sets: if we take into account only the combination of its edges and nodes in the graph topology, omitting the numbering of edges, we can select only 204 unique graphs for four possible puzzles colored cubes.

Decision graphs — those two paths of the nodes traversal that need to be distinguished from the multigraph — will be similar, although the original multigraph itself can be divided in different ways, because the numbering of faces nevertheless introduces features into the general topology of the graph. The graphical model that we use to find a puzzle solution, similar to Instant Insanity, characterizes sets of cubes only in terms of optimizing the search for solutions to this puzzle. This model is based on the analysis of the topological structure of a set of cubes for solving only one narrow problem - the problem of the relative arrangement of cubes. Separate multigraph, like the graph of a separate cube, does not indicate the uniqueness of the object, and it should not - we ourselves were looking for something in common in the phenomenon, and not in the object . The portrait image does not appear from the laconic characteristic "character - solid, Nordic."


Fig. 4. 204 columns "puzzles with four colored cubes."

Isomorphism

I have only a slight hope that someone peered carefully at the graphs given by me - mind you - for everyone! puzzles of four colored cubes, and, in addition, bothered to carefully examine the solution graphs for Instant Insanity and its clones from the website of Robert Stegmann. Meanwhile, this inquisitive hypothetical reader would undoubtedly have a question: “And where, where is this very one, instantly replicated by millions of copies, Count Instant Insanity? “Nothing at all like any of these graphs?” “But he is, nevertheless, there is ... However, it is not surprising that it is not possible to recognize this graph the first time — here, however, I got excited: there is no chance of knowing this graph either from the second or third — this problem is called isomorphism of graphs .

 

Count Instant Insanity and the countless number of its clones, shyly endowed by their "creators" with different names, can be seen in the left figure. Usually it is this pattern that accompanies the sold puzzle piece to maintain the spirit of those who are completely desperate ... (I have already done the subgraphing, I hope, will remove all their difficulties at all) It is impossible to find out this puzzle in the figure below, and this is only one of 1073 possible puzzles from four cubes !, just repainted (and probably somewhere existing with a different name).


There are various ways to identify isomorphism of graphs, but the description of any of them, in my opinion, is redundant for an already protracted article. However, without an illustration of the “miracle of transformation”, some readers may find themselves disappointed, and I prefer that she find other reasons for this.

Take a scan of the Instant Insanity puzzle on Robert Stegmann’s website (R. Stegmann - he’s probably the “handshake” of the entire IPP club!) - I will follow the following order of circumvention of the cube faces: bottom → front → top → back → left → right.

The most common of the scans from the marked site (the author has collected several clones, but we focus on the “classic” version of the puzzle) will be written in the selected order of traversal as follows: RWGGWB, RBBWGG, RGWWRB, GWRBRR.
I hope that no one has forgotten that when writing the graph we take into account only pairs of colors of opposite faces, and therefore the line recording of the graphic configuration of the selected cubes looks no different than: RG | WG | WB, RB | BW | GG, RW | GW | RB, GR | WB | RR. As you can see, the multigraph in the first figure fully corresponds to this set (well, except for the fact that I have yellow instead of classic white).

Perhaps it’s more than one that I’m more comfortable working with numbers, so we’ll designate the numbers as colors (and thereby exclude some disagreement in the colors noted above), and at the same time we’ll write down this combination of cubes immediately in the solution position (fortunately, we have two subgraphs that show us the way before your eyes):

• R = 0, W = 1, B = 2, G = 3
• After that, replace the colors (“repaint the cubes”) as follows:
  0 → 1, 1 → 2, 2 → 3, 3 → 0
• and in the end, each of them will rotate 90 degrees twice around the “long” axis of the pyramid (in the terms adopted in the previous publication, this is equivalent to a permutation of the faces in the order 230145, which, of course, is no longer colors, but indices )

[0, 1, 3, 3, 1, 2] → [1, 2, 0, 0, 2, 3] → [0, 0, 1, 2, 2, 3] : RW|RB|BG
[2, 2, 0, 1, 3, 3] → [3, 3, 1, 2, 0, 0] → [1, 2, 3, 3, 0, 0] : WG|BG|RR
[3, 0, 1, 2, 0, 1] → [0, 1, 2, 3, 1, 2] → [2, 3, 0, 1, 1, 2] : BR|GW|WB
[1, 3, 2, 0, 0, 0] → [2, 0, 3, 1, 1, 1] → [3, 1, 2, 0, 1, 1] : GB|WR|WW

You can compare the resulting graph with that placed below the Instant Insanity graph, and make sure that it is the same graph.

Instead of a conclusion

I really hope that reading was not boring. Perhaps someone was partly helpful. And I’m almost sure that the number of envelopes drawn by tomorrow will increase slightly, and someone will finally find the strength and motivation to distract the heir from his gadget with some interesting and smart task. Euler didn’t neglect ...

---

1. ↑Leonard Euler. Letters to Scientists, Publishing House of the USSR Academy of Sciences, 1963, p
. 339 2. ↑Leonard Euler. Letters to Scientists, Publishing House of the Academy of Sciences of the USSR, 1963, p
. 153 3. ↑Henry E. Dudeney. 520 puzzles. Compiled and edited by the American publication M. Gardner, MIR Publishing House, Moscow, 1975

---