Material and information models. Examples of information models in school Examples of graphic models in everyday life
Information model– a model of an object, presented in the form of information that describes the parameters and variable quantities of the object that are essential for this consideration, the connections between them, the inputs and outputs of the object, and which allows, by feeding the model information about changes in input quantities, to simulate possible states of the object.
Information models cannot be touched or seen; they have no material embodiment, because they are built only on information. An information model is a set of information that characterizes the essential properties and states of an object, process, phenomenon, as well as the relationship with the outside world.
An information model is a formal model of a limited set of facts, concepts, or instructions designed to satisfy a specific requirement.
To build an information model, it is necessary to go through a number of stages presented in Diagram 3. The process carried out from the “object of knowledge” to the “formal construction” is called “formalization”, and the reverse process - “interpretation” - is most often used in knowledge of the world and learning .
Information modeling is based on three postulates:
everything is made up of elements;
elements have properties;
elements are interconnected by relationships.
The object to which these postulates apply can be represented by an information model.
Stages of building an information model.
F Object of knowledge I
O Cognizing subjects N
P Personal presentation T
M Formed thought E
And the “Live” word R
L Written word P
I Scientific text R
Z Formal constructions E
Classifications of information models:
-according to the method of description:
Using formal languages (mathematical language, tables, programming languages, extension of human natural language, etc.);
Graphic (flowcharts, diagrams, graphs, etc.).
-according to the purpose of creation:
Classification (tree-like, family tree, computer directory tree);
Dynamic (as a rule, they are built on the basis of solving differential equations and are used to solve control and forecasting problems).
- by the nature of the modeled object:
Deterministic (definite), for which the laws by which the object changes or develops are known;
Probabilistic (processing of statistical uncertainty and some types of fuzzy information).
Historical origin and methodological significance of the concepts of model and analogy.
The word “model” comes from the Latin word “modulus”, meaning “measure”, “sample”. Its original meaning was associated with the art of building, and in almost all European languages it was used to denote an image or prototype, or a thing similar in some respect to another thing.
Modeling in scientific research began to be used in ancient times and gradually captured new areas of scientific knowledge: technical design, construction and architecture, astronomy, physics, chemistry, biology and, finally, social sciences. The 20th century brought great success and recognition in almost all branches of modern science to the modeling method. However, modeling methodology has long been developed by individual sciences independently of each other. There was no unified system of concepts, no unified terminology. Only gradually the role of modeling as a universal method of scientific knowledge began to be realized.
The term “model” is widely used in various fields of human activity and has many meanings. In this section we will consider only those models that are tools for obtaining knowledge.
Thus, model– a simplified idea of a real object, process or phenomenon. A model is a material or mentally imagined object that, in the process of research, replaces the original object so that its direct study provides new knowledge about the original object.
Under simulation understands the process of constructing, studying and applying models. It is closely related to such categories as abstraction, analogy, hypothesis, etc. The modeling process necessarily includes the construction of abstractions, inferences by analogy, and the construction of scientific hypotheses. Modeling– building models for research and study of objects, processes, phenomena.
Models of objects must reflect something that actually exists. Therefore, object models are often understood as an abstract generalization of real-life objects. For example, models of objects can be copies of architectural structures, the solar system, the structure of parliamentary power in the country, etc. The model can describe the phenomena of living and inanimate nature, and not just one, but a whole class of phenomena with common properties. Models of objects or phenomena reflect the properties of the original - its characteristics, parameters.
You can also create process models, e.g. simulate actions on material objects: progress, successive changes of states, stages of development of one object or their system. Examples of this are well known: these are models of economic or environmental processes, the development of the Universe or society, etc.
Methodological basis for modeling.
The modeling theory is based on a systems approach. The systems approach is that the researcher tries to study the behavior of the system as a whole, rather than focusing on its individual parts. This approach is based on the recognition that even if each element or subsystem has optimal design or functional characteristics, the resulting behavior of the system as a whole may be only suboptimal due to the interaction between its individual parts.
The increasing complexity of organizational systems and the need to overcome this complexity have led to the systems approach becoming an increasingly necessary research method.
A certain set of elements of the system under consideration can be represented as its subsystem. It is believed that subsystems include some independently functioning parts of the system. Therefore, to simplify the research procedure, it is initially necessary to correctly identify the subsystems of a complex system, that is, to determine its structure. The structure of a system is a time-stable set of relationships between its components (subsystems). And with a systems approach, an important step is to determine the structure of the system being studied and described.
A system is a whole made up of parts. A system is a set of elements that are in relationships and connections with each other and form a certain integrity and unity.
Computer model.
Computer model– a model implemented by means of a software environment.
When dealing with a computer as a tool, you need to remember that it works with information. Therefore, one should proceed from what information and in what form a computer can perceive and process. A modern computer is capable of working with sound, video, animation, text, diagrams, tables, etc. But to use the entire variety of information, you need both hardware (Hardware) and software (Software). Both are computer modeling tools. There is now a wide range of programs that allow you to create various types of computer iconic models: word processors, formula editors, spreadsheets, database management systems, professional design systems, as well as various programming environments.
Modern computers provide ample opportunities for modeling various phenomena and processes. In the educational process, a computer should not simply replace a blackboard, a poster, a film and slide projector, or a natural experiment. Such a replacement is advisable only when the use of a computer will provide a significant additional effect compared to the use of other teaching aids.
Computer modeling (CM) is a promising method for enhancing the educational process. It is gaining more and more importance in modern scientific knowledge, and, in addition, is currently becoming a popular didactic tool. Let's consider this direction in more detail.
The subject of CM is the study of processes and phenomena using a computer, which in this case acts as an experimental setup. When using CM to solve problems, the stages of problem formulation, model development, computer (computational) experiment, and analysis of modeling results are distinguished. If the simulation results do not meet the goal, then there is a need to return to previous stages.
Mathematical models.
Mathematical modeling allows using mathematical symbols and dependencies to create a description of the ongoing process.
Mathematical model is a set of mathematical objects and relationships between them that adequately reflects the properties and behavior of the object under study. The model is considered adequate if it reflects the properties under study with acceptable accuracy. The accuracy is assessed by the degree of agreement between the values of the output parameters predicted during a computational experiment on the model and their true values.
A mathematical model covers a class of undefined (abstract, symbolic) mathematical objects such as numbers or vectors, and the relationships between these objects.
A mathematical relation is a hypothetical rule connecting two or more symbolic objects. Many relationships can be described using mathematical operations that connect one or more objects with another object or set of objects (the result of the operation).
A mathematical model will reproduce suitably selected aspects of a physical situation if a correspondence rule can be established linking specific physical objects and relations with specific mathematical objects and relations. The construction of mathematical models for which there are no analogues in the physical world can also be instructive and/or interesting. The most commonly known mathematical models are systems of integers and real numbers and Euclidean geometry; the defining properties of these models are more or less direct abstractions of physical processes (counting, ordering, comparison, measurement).
The objects and operations of more general mathematical models are often associated with sets of real numbers that can be related to the results of physical measurements.
Numbers, variables, sets, vectors, matrices, etc. act as mathematical objects.
Classification of mathematical models based on the characteristics of the mathematical apparatus used.
Homework check Give various examples of graphical information models. Give various examples of graphical information models. Graphic model of your apartment. What is this: map, diagram, drawing? Graphic model of your apartment. What is this: map, diagram, drawing? What form of graphical model (map, diagram, drawing, graph) is applicable to display processes? Give examples. What form of graphical model (map, diagram, drawing, graph) is applicable to display processes? Give examples.
Dynamic Simulation
Meaningful formulation of the problem During the training of tennis players, machines are used to throw the ball at a certain place on the court. It is necessary to set the machine the required speed and angle of throwing the ball to hit an area of a certain size located at a known distance.
Qualitative descriptive model: the ball is small compared to the Earth, so it can be considered a material point; the ball is small compared to the Earth, so it can be considered a material point; the change in the height of the ball is small, therefore the acceleration of gravity can be considered a constant value g = 9.8 m/s 2 and the movement along the Y axis can be considered uniformly accelerated; the change in the height of the ball is small, therefore the acceleration of gravity can be considered a constant value g = 9.8 m/s 2 and the movement along the Y axis can be considered uniformly accelerated; the speed of throwing the body is low, therefore air resistance can be neglected and the movement along the X axis can be considered uniform. the speed of throwing the body is low, therefore air resistance can be neglected and the movement along the X axis can be considered uniform.
Mathematical model x = v0 cosα t y = v0 sinα t – g t 2 /2 v0 sinα t – g t 2 /2 = 0 t (v0 sinα – g t/2) = 0 v0 sinα – g t/2 = 0 t = (2 v0 sinα)/g x = (v0 cosα 2 v0 sinα)/g = (v0 2 sin2α)/g S x S+ L – “hit” If x is S+L, then this means “overfly”.
Computer model in Pascal language Computer model in Pascal language program s1; uses graph; (connecting a graphics module) uses graph; (graphics module connection) var g, V0, A, t: real; var g, V0, A, t: real; gr, gm, S, L, x, i, y: integer; gr, gm, S, L, x, i, y: integer;
Computer model in Turbo Pascal language Computer model in Turbo Pascal language begin g:=9.8; g:=9.8; readln(v0, a, S, L); gr:=detect; initgraph(gr,gm,""); (call the GRAPH procedure) line(0,200,600,200);(draw the x-axis) line(0,0,0,600);(draw the y-axis) setcolor(3);(set the blue color) line(S*10,200,(S+L) *10,200); (draw a platform)
Computer model in Turbo Pascal language Computer model in Turbo Pascal language x:=round(v0*v0*sin(2*a*3.14/180)/g); if x S+L then outtextxy(500,100,"perelet") else outtextxy(500,100,"popal"); (record the flight result) readln;closegraph;end.
Diversity graphic models big enough. Let's look at some of them.
Graphs
Graphs are a visual means of displaying the composition and structure of systems. Let's look at an example. There is a verbal description of some area.
The district consists of five villages: Dedkino, Repkino, Babkino, Koshkino and Myshkino. Highways are laid between: Dedkino and Babkino, Dedkino and Koshkino, Babkino and Myshkino, Babkino and Koshkino, Koshkino and Repkino.
From such a description it is quite difficult to imagine this area. The same information is much easier to perceive with the help of a diagram. This is not a map of the area. The cardinal directions are not maintained here and the scale is not maintained. This diagram reflects only the fact of the existence of five villages and the road connection between them. Such a diagram, displaying the elemental composition of the system and the structure of connections, is called a graph.
Components The graph consists of vertices and edges. In the figure, the vertices are shown as circles - these are elements of the system, and the edges are shown as lines - these are connections (relationships) between the elements. Looking at this graph, it is easy to understand the structure of the road system in a given area.
The constructed graph allows, for example, to answer the question: through which villages do you need to pass to get from Repkino to Myshkino? It can be seen that there are two possible ways: 1) R - K - B - M and 2) R - K - D - B - M. Can we conclude from this that the 1st path is shorter than the 2)th one? No you can not. This graph does not contain quantitative characteristics. This is not a map where the scale is respected and it is possible to measure distance.
The graph shown in the following figure contains quantitative characteristics. The numbers near the edges indicate the length of the roads in kilometers. This is an example of a weighted graph. A weighted graph can contain quantitative characteristics not only of connections, but also of vertices. For example, the vertices may indicate the population of each village. According to the data of the weighted graph, it turns out that the second path is longer than the first.
Such graphs are also called a network. The network is characterized by the possibility of many different paths of movement along the edges between some pairs of vertices. Networks are also characterized by the presence of closed paths called loops. In this case there is a cycle: K-D-B-K
In the diagrams discussed, each edge indicates the presence of a road connection between two points. But the road connection operates equally in both directions: if you can drive along the road from B to M, then you can also drive along it from M to B (we assume that there is two-way traffic). Such graphs are undirected, and their connections are called symmetric.
A qualitatively different example of a graph is shown in the following figure.
This example relates to medicine. It is known that different people have different blood types. There are four blood types. It turns out that when blood is transfused from one person to another, not all groups are compatible. The graph shows possible options blood transfusions. Blood groups are the vertices of the graph with corresponding numbers, and the arrows indicate the possibility of transfusion of one blood group to a person with a different blood group. For example, from this graph it is clear that blood of the first group can be transfused to any person, and a person with the first blood group accepts only blood of his own group. It can also be seen that a person with blood group IV can be transfused with any blood, but his own blood can only be transfused into the same group.
The connections between the vertices of this graph are asymmetrical and therefore are depicted by directed lines with arrows. Such lines are usually called arcs (in contrast to the edges of undirected graphs). A graph with such properties is called directed. A line leaving and entering the same vertex is called a loop. IN in this example There are four loops.
Tree – graph of hierarchical structure
A very common type of systems are systems with a hierarchical structure. A hierarchical structure naturally arises when objects or some of their properties are in a relationship of subordination (nesting, inheritance). As a rule, administrative management systems have a hierarchical structure, between the elements of which relationships of subordination are established (plant director - shop managers - section managers - foremen - workers). Systems also have a hierarchical structure, between the elements of which there are relationships of one entering another.
A graph of a hierarchical structure is called a tree. The main property of a tree is that there is only one path between any two of its vertices. Trees do not contain cycles or loops.
Tree of the administrative structure of the Russian Federation
Look at the graph reflecting the hierarchical administrative structure of our state: the Russian Federation is divided into seven administrative districts; Districts are divided into regions (regions and national republics), which include cities and other settlements. Such a graph is called a tree.
A tree has one main vertex, which is called the root of the tree. This peak is depicted at the top; tree branches come from it. The tree levels begin to count from the root. The vertices directly connected to the root form the first level. From them there are connections to the vertices of the second level, etc. Each tree vertex (except the root) has one source vertex at the previous level and can have many child vertices at the next level. This principle of communication is called “one to many”. Vertices that do not have any children are called leaves (in our graph these are the vertices that represent cities).
Graphical modeling results of scientific research.
The general goal of scientific graphics can be formulated as follows: to make the invisible and abstract “visible”. The last word is in quotation marks because... this appearance is often very conditional. You can see the temperature distribution inside a non-uniformly heated body of complex shape without introducing hundreds of microsensors into it, i.e. essentially its destruction? – Yes, it is possible if there is an appropriate mathematical model and, what is very important, an agreement on the perception of certain conventions in the drawing. Can see distribution of metal ores underground without excavation? WITH tripling of the surface of an alien planet based on radar results? Yes, you can, with help computer graphics and the mathematical processing preceding it.
Moreover, one can “see” something that, strictly speaking, generally does not correspond well to the word “see”. Thus, the science that emerged at the intersection of chemistry and physics—quantum chemistry—gives us the opportunity to “see” the structure of a molecule. These images are the height of abstraction and a system of conventions, since in the atomic world our usual concepts of particles (nuclei, electrons, etc.) are fundamentally inapplicable. However, a multicolored “image” of a molecule on a computer screen, for those who understand the full extent of its conventions, brings more benefits than thousands of numbers that are the results of calculations.
Isolines.
A standard technique for processing the results of a computational experiment is the construction of lines (surfaces), called isolines (isosurfaces), along which a certain function has a constant value. This is a very common technique for visualizing the characteristics of a certain scalar field in the approximation of a continuous medium: isotherms - lines of equal temperature; isobars – lines of equal pressure; isolines of the ecological population size in the area, etc.
Conditional colors, conditional contrast
This is a technique of modern scientific graphics - conditional coloring. It finds wide application in a wide variety of scientific applications and is a set of techniques for the most convenient visualization of the results of computer modeling.
In various studies of temperature fields, the problem arises of visually representing the results, for example, temperatures on meteorological maps. To do this, you can draw isotherms against the background of a map of the area. But you can achieve even greater clarity, given that most people tend to perceive red as “hot” and blue as “cold”. The transition along the spectrum from red to blue reflects intermediate temperature values. When searching for minerals using aerial photography from airplanes or space satellites, computers build conditional color images of density distributions under the Earth’s surface, etc.
Images in conditional colors and contrasts are a powerful technique in scientific graphics.
- Not to be confused study of graphical information modeling with the study of processing technologies graphic information
- The construction of simple graphical models in the form of graphs and hierarchical structures is appropriate in a basic computer science course.
- The implementation of scientific graphics models through programming is a material of increased difficulty, the practical development of which is appropriate in a specialized computer science course.
Exercise :
- Draw up a diagram of key concepts;
- Select practical tasks with solutions for basic and specialized computer science courses.
Homework check Give various examples of graphical information models. Give various examples of graphical information models. Graphic model of your apartment. What is this: map, diagram, drawing? Graphic model of your apartment. What is this: map, diagram, drawing? What form of graphical model (map, diagram, drawing, graph) is applicable to display processes? Give examples. What form of graphical model (map, diagram, drawing, graph) is applicable to display processes? Give examples.
Dynamic Simulation
Meaningful formulation of the problem During the training of tennis players, machines are used to throw the ball at a certain place on the court. It is necessary to set the machine the required speed and angle of throwing the ball to hit an area of a certain size located at a known distance.
Qualitative descriptive model: the ball is small compared to the Earth, so it can be considered a material point; the ball is small compared to the Earth, so it can be considered a material point; the change in the height of the ball is small, therefore the acceleration of gravity can be considered a constant value g = 9.8 m/s 2 and the movement along the Y axis can be considered uniformly accelerated; the change in the height of the ball is small, therefore the acceleration of gravity can be considered a constant value g = 9.8 m/s 2 and the movement along the Y axis can be considered uniformly accelerated; the speed of throwing the body is low, therefore air resistance can be neglected and the movement along the X axis can be considered uniform. the speed of throwing the body is low, therefore air resistance can be neglected and the movement along the X axis can be considered uniform.
Mathematical model x = v0 cosα t y = v0 sinα t – g t 2 /2 v0 sinα t – g t 2 /2 = 0 t (v0 sinα – g t/2) = 0 v0 sinα – g t/2 = 0 t = (2 v0 sinα)/g x = (v0 cosα 2 v0 sinα)/g = (v0 2 sin2α)/g S x S+ L – “hit” If x is S+L, then this means “overfly”.
Computer model in Pascal language Computer model in Pascal language program s1; uses graph; (connecting a graphics module) uses graph; (graphics module connection) var g, V0, A, t: real; var g, V0, A, t: real; gr, gm, S, L, x, i, y: integer; gr, gm, S, L, x, i, y: integer;
Computer model in Turbo Pascal language Computer model in Turbo Pascal language begin g:=9.8; g:=9.8; readln(v0, a, S, L); gr:=detect; initgraph(gr,gm,""); (call the GRAPH procedure) line(0,200,600,200);(draw the x-axis) line(0,0,0,600);(draw the y-axis) setcolor(3);(set the blue color) line(S*10,200,(S+L) *10,200); (draw a platform)
Computer model in Turbo Pascal language Computer model in Turbo Pascal language x:=round(v0*v0*sin(2*a*3.14/180)/g); if x S+L then outtextxy(500,100,"perelet") else outtextxy(500,100,"popal"); (record the flight result) readln;closegraph;end.
4.8 Graphic information models.
A graphical information model is a visual way of representing objects and processes in the form of graphic images. These include: drawings, graphs, diagrams, figurative models, diagrams (maps, graphs, flowcharts).
Graphic (geometric) information models convey the external characteristics of an object - size, shape, color, location. In graphic information models, conventional graphic images (figurative elements) are used to visually display objects. Often graphic models are supplemented with numbers, symbols and texts (sign elements). In this case, they are called mixed models.
Figurative models are visual images of objects recorded on some information medium (paper, photo and film, etc.). These include drawings and photographs.
Scheme- this is a representation of some object in general, main features using symbols. Scheme is a graphical representation of the composition and structure of a complex system. With the help of diagrams it is possible to represent appearance object and its structure. A diagram as an information model does not claim to be complete in providing information about an object. With the help of special techniques and graphic symbols, one or more features of the object in question are highlighted more clearly.
In computer science, a special place is occupied by the construction of flowcharts. Block diagrams clearly reflect the algorithm, i.e. sequence of actions when solving a problem. They are built during programming - creating new programs.
Map describes a specific area, which is the object of modeling for it. This is a reduced generalized image of the Earth’s surface on a plane in one or another symbol system .
The map is created with specific purposes to determine:
locations of settlements;
terrain;
highway locations;
measuring distances between real objects on the ground
etc.
Drawing– an exact geometric copy of a real object. Drawing- conditional graphic image an object with an exact ratio of its dimensions, obtained by projection. The drawing contains images, dimensional numbers, and text. Images give ideas about the geometric shape of the object, numbers - about the size of the object and its parts, inscriptions - about the name, the scale in which the images are made. Drawings are created by designers, designers, they must be very accurate, because... they indicate all the necessary dimensions of the real object. There are a lot of different computer environments for creating design drawings: AutoCAD, Adem, Compass, 3D MAX - for three-dimensional modeling, etc.
Graphs and diagrams are information models that present numerical and statistical data in a visual form.
Schedule- a line that gives a visual representation of the nature of the dependence of one quantity (for example, path) on another (for example, time). Schedule– display and visualization of various processes (natural, economic, social and technical). The graph allows you to track the dynamics of data changes. 
Diagram- a graphic image that gives a visual representation of the relationship between any quantities or several values of one quantity, and the change in their values. The types of charts and methods for constructing them will be discussed in more detail when studying spreadsheets.
Graphs occupy a special place among graphical models.
4.9 Graphs
Graphs are wonderful mathematical objects; with their help you can solve a lot of different, outwardly dissimilar problems. There is a whole section in mathematics - graph theory, which studies graphs, their properties and applications. In computer science, programs are built using graphs. This section discusses only the most basic concepts, properties of graphs and some methods for solving problems.
If the objects of a certain system are represented by points (circles, ovals, rectangles...), and the connections between them are represented by lines (arcs, arrows...), then we will obtain an information model of the system in question in the form of a graph. Graph is a set of vertices and edges connecting them. The vertices of the graph can be designated by letters, numbers, words...
If the edges of a graph are characterized by some additional information (expressed in numbers), it is called weighted, and the numbers are scales ribs The weight of the edges can correspond, for example, to the distance between objects (cities).
If the edges of a graph indicate direction (represented by arrows), then the graph is called oriented(digraph). Movement in a directed graph is only possible in one direction (along the arrows). In this case, connections between objects - vertices - are considered asymmetrical. In an undirected graph, the connections between objects - vertices - are symmetrical.
Identical but differently drawn graphs are called isomorphic. Isomorphic graphs have the same vertices connected.
Degree A vertex in a graph is called the number of edges leaving it. A vertex with an even degree is called even vertex,A vertex having an odd degree is called odd vertex. In the figure, vertices A, B, D are even. Their degree is 2. The vertices C and E are odd. Their degree is 3.
One of the main theorems of graph theory is connected with the concept of vertex degree - the theorem on the parity of the number of odd vertices.
Theorem : Any graph contains an even number of odd vertices.
To illustrate, consider a problem.
There are 5 telephones in the town of Malenky. Is it possible to connect them with wires so that each phone is connected to exactly 3 others?
Solution: Let's assume that such a connection between telephones is possible. Then imagine a graph in which the vertices represent telephones, and the edges represent the wires connecting them. Let's count how many wires there are in total. Each phone has exactly 3 wires connected, i.e. the degree of each vertex of our graph is 3. To find the number of wires, you need to sum up the degrees of all the vertices of the graph and divide the resulting result by 2 (since each wire has two ends and when summing the degrees, each wire is taken 2 times). (3*5)/2=15/2=7.5
But this number is not an integer, that is, the number of wires will be different. This means that our assumption that each phone can be connected to exactly five others turned out to be incorrect.
Answer. It is impossible to connect phones this way.
There is another important concept related to graphs - the concept of connectivity. The graph is called coherent,
if any two of its vertices can be connected by,
those. continuous sequence of edges. There are a number of problems whose solution is based on the concept of graph connectivity. The graph in the figure below has three connected components (consists of three separate parts).
A vertex that has no edges is called isolated the top and is separate component connectivity. A vertex with only one edge is called terminal or hanging.
A path along the vertices and edges of a graph, in which any edge of the graph occurs at most once, is called chain (1) . A chain whose starting and ending vertices coincide is called cycle (2). Tree (hierarchy) is a graph in which there are no cycles (3), that is, in it it is impossible to go from a certain vertex along several different edges and return to the same vertex. Distinctive feature of a tree is that between any two of its vertices there is only one path.
(1) 
(2) 
(3)
Any hierarchical system can be represented using a tree. A tree has one main vertex, called its root. Each vertex of the tree (except the root) has only one ancestor; the object designated by it is included in one class1 of the highest level. Any vertex of a tree can generate several descendants - vertices corresponding to lower-level classes. This communication principle is called “one-to-many”. Vertices that have no generated vertices are called leaves.
For example, it is convenient to depict relationships between family members using a graph called a family tree or family tree.
A graph with a cycle is called network. If we represent the characters of a certain literary work as vertices of a graph, and the connections existing between them are depicted as edges, then we get a graph called semantic network.
4.10
Using graphs to solve problems
Example 1. In order to write down all three-digit numbers consisting of digits 1 and 2, you can use a graph (tree)
You don’t have to build a tree if you don’t need to write down all possible options, but just need to indicate their number. In this case, you need to reason like this: in the hundreds place there can be any of the numbers 1 and 2, in the tens place there can be the same two options, in the units place there can be the same two options. Therefore, the number of different options: 2 2 2 = 8.
In general, if the number of possible choices at each step of constructing the graph is known, then all these numbers are needed to calculate the total number of options multiply.
Example 2. Let us consider a slightly modified classical crossing problem.
On the bank of the river stands a peasant (K) with a boat, and next to him there is a dog (S), a fox (L) and a goose (G). The peasant must cross himself and transport the dog, fox and goose to the other side. However, in addition to the peasant, either only a dog, or only a fox, or only a goose can be placed in the boat. You cannot leave a dog with a fox or a fox with a goose unattended - the dog is a danger to the fox, and the fox is a danger to the goose. How should a peasant organize a crossing?
D 
To solve this problem, let's create a graph whose vertices will be the initial placement of the characters on the river bank, as well as all sorts of intermediate states achieved from the previous ones in one crossing step. We denote each crossing state vertex by an oval and connect it with edges to the states formed from it. Invalid states according to the conditions of the problem are highlighted with a dotted line; they are excluded from further consideration. Initial and final state crossings are highlighted with a bold line.
The graph shows that there are two solutions to this problem. Here is a crossing plan corresponding to one of them:
a peasant transports a fox;
the peasant returns;
a peasant transports a dog;
the peasant returns with the fox;
a peasant transports a goose;
the peasant returns;
a peasant transports a fox.
Player I can remove one match (in this case there will be 4 of them) or 2 at once (in this case there will be 3 of them).
If the player I left 4 matches, player II can leave 3 or 2 matches on its own. If after the first player's turn there are 3 matches left, the second player can win by taking two matches and leaving one.
If after the player II 3 or 2 matches left, then the player I in each of these situations has a chance to win.
Thus, with the right game strategy, the first player will always win. To do this, he must take one match on his first move.
In Fig. 2.8 presents a graph called game tree; it reflects all possible options, including erroneous (losing) moves of players.
Control questions.
What information models are classified as graphic?
Give examples of graphical information models that you are dealing with:
What is a graph? What are the vertices and edges of the graph?Use your own example graph.
Which graph is called directed? Weighted?
What graphs are called isomorphic?
What is the degree of a vertex? Specify the degrees of the vertices in your graph.
Formulatetheorem on the parity of the number of odd vertices.
Which graph is called connected? Draw a graph with two connected components.
Which vertex is called isolated? Hanging? Use your own example – graph.
What is a path? Chain? Cycle?Give examples of circuits and cycles available in your graph.
What is a tree? What systems can trees serve as models? Give an example of such a system.
Create a semantic network based on the Russian folk tale “Kolobok”.