Similar documents
Restoring graphs from given vertex adjacency matrices. Construction for each graph of a matrix of edge adjacency, incidence, reachability, counter-reachability. Finding the composition of graphs. Determination of local degrees of graph vertices. Searching for a graph database.
laboratory work, added 01/09/2009
Description of a given graph by sets of vertices V and arcs X, adjacency lists, incidence and adjacency matrix. The weight matrix of the corresponding undirected graph. Determination of the shortest path tree using Dijkstra's algorithm. Finding trees on a graph.
course work, added 09/30/2014
The concept of "graph" and its matrix representation. Properties of adjacency and incidence matrices. Properties of routes, chains and loops. The problem of finding the central vertices of a graph, its metric characteristics. Application of graph theory in the fields of science and technology.
course work, added 05/09/2015
Algorithm for transition to graphical representation for an undirected graph. The number of vertices in an undirected graph. Reading from the adjacency matrix. Connections between vertices in the matrix. Setting the coordinates of the vertices depending on the number of sectors.
laboratory work, added 04/29/2011
Mathematical description of an automatic control system using graphs. Drawing up a graph and transforming it, getting rid of differentials. Optimization of directed and undirected graphs, compilation of adjacency and incidence matrices.
laboratory work, added 03/11/2012
Directed and undirected graphs: general characteristics, special vertices and edges, half-degrees of vertices, adjacency, incidence, reachability, connectivity matrices. Numerical characteristics of each graph, depth-first and breadth-first traversal, cycle basis.
course work, added 05/14/2012
Checking the validity of identities or inclusions using set algebra and Euler-Venn diagrams. Image of a graph and matrix of a relation that has the properties of reflexivity, transitivity and antisymmetricity. Learning an undirected graph.
test, added 05/05/2013
A set is a collection of elements united according to some characteristic. Operations that are in many ways similar to arithmetic are defined on sets. Set operations are interpreted geometrically using Euler-Venn diagrams.
abstract, added 02/03/2009
Construction of a pseudograph diagram, incidence matrix and vertex adjacency matrix. Restoring a tree from a vector using the Prüfer algorithm. Construction of a truth table for a function and perfect conjunctive and disjunctive normal forms.
test, added 09.25.2013
Methods for solving discrete mathematics problems. Calculating the shortest path between pairs of all vertices in directed and undirected graphs using Floyd's algorithm. Analysis of the problem and methods for solving it. Development and characteristics of the program.
Some problems can be conveniently and clearly solved using Euler-Venn diagrams. For example, problems involving sets. If you don’t know what Euler-Venn diagrams are and how to build them, then read first.
Now let's look at typical problems about sets.
Task 1.
A survey was conducted among 100 students at a school with in-depth study of foreign languages. The students were asked the question: “What foreign languages are you studying?” It turned out that 48 students are studying English, 26 - French, 28 - German. 8 schoolchildren study English and German, 8 - English and French, 13 - French and German. 24 schoolchildren do not study English, French or German. How many schoolchildren who completed the survey study three languages at the same time: English, French and German?
Answer: 3.
Solution:
- many schoolchildren learning English ("A");
- many schoolchildren studying French (“F”);
- many schoolchildren studying German ("N").
Let us depict using the Euler-Venn diagram what is given to us according to the condition.
Let us denote the desired area A=1, Ф=1, Н=1 as “x” (in the table below, area No. 7). Let's express the remaining areas in terms of x.
0) Region A=0, Ф=0, Н=0: 24 schoolchildren - given according to the conditions of the problem.
1) Area A=0, F=0, H=1: 28-(8-x+x+13-x)=7+x schoolchildren.
2) Area A=0, F=1, H=0: 26-(8-x+x+13-x)=5+x schoolchildren.
3) Area A=0, F=1, N=1: 13 schoolchildren.
4) Area A=1, F=0, H=0: 48-(8-x+x+8-x)=32+x schoolchildren.
5) Area A=1, F=0, H=1: 8 schoolchildren.
6) Area A=1, F=1, H=0: 8 schoolchildren.
| № region | A |
F |
N |
Quantity schoolchildren |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
24 |
| 1 | 0 |
0 |
1 |
7+x |
| 2 | 0 |
1 |
0 |
5+x |
| 3 | 0 |
1 |
1 |
13th |
| 4 | 1 |
0 |
0 |
32+x |
| 5 | 1 |
0 |
1 |
8 |
| 6 | 1 |
1 |
0 |
8 |
| 7 | 1 |
1 |
1 |
X |
Let's define x:
24+7+(x+5)+x+(13-x)+(32+x)+(8-x)+(8-x)+x=100.
x=100-(24+7+5+13+32+8+8)=100-97=3.
We found that 3 schoolchildren were studying three languages at the same time: English, French and German.
This is what the Euler-Venn diagram will look like for known x:
Task 2.
At the Mathematics Olympiad, schoolchildren were asked to solve three problems: one in algebra, one in geometry, one in trigonometry. 1000 schoolchildren took part in the Olympiad. The results of the Olympiad were as follows: 800 participants solved the problem in algebra, 700 in geometry, 600 in trigonometry. 600 schoolchildren solved problems in algebra and geometry, 500 in algebra and trigonometry, 400 in geometry and trigonometry. 300 people solved problems in algebra, geometry and trigonometry. How many schoolchildren did not solve a single problem?
Answer: 100.
Solution:
First, we define sets and introduce notation. There are three of them:
- many problems in algebra ("A");
- many problems in geometry ("G");
- many problems in trigonometry ("T").
Let's depict what we need to find:
Let us determine the number of schoolchildren for all possible areas.
Let us denote the desired area A=0, G=0, T=0 as “x” (in the table below, area No. 0).
Let's find the remaining areas:
1) Area A=0, G=0, T=1: no schoolchildren.
2) Area A=0, G=1, T=0: no schoolchildren.
3) Area A=0, G=1, T=1: 100 schoolchildren.
4) Area A=1, G=0, T=0: no schoolchildren.
5) Region A=1, G=0, T=1: 200 schoolchildren.
6) Area A=1, D=1, T=0: 300 schoolchildren.
7) Region A=1, G=1, T=1: 300 schoolchildren.
Let's write the values of the areas into the table:
| № region | A |
G |
T |
Quantity schoolchildren |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
X |
| 1 | 0 |
0 |
1 |
0 |
| 2 | 0 |
1 |
0 |
0 |
| 3 | 0 |
1 |
1 |
100 |
| 4 | 1 |
0 |
0 |
0 |
| 5 | 1 |
0 |
1 |
200 |
| 6 | 1 |
1 |
0 |
300 |
| 7 | 1 |
1 |
1 |
300 |
Let's display the values for all areas using a diagram:
Let's define x:
x=U-(A V Г V Т), where U is the universe.
A V G V T=0+0+0+300+300+200+100=900.
We found that 100 schoolchildren did not solve a single problem.
Task 3.
At the Physics Olympiad, schoolchildren were asked to solve three problems: one in kinematics, one in thermodynamics, and one in optics. The results of the Olympiad were as follows: 400 participants solved the problem in kinematics, 350 in thermodynamics, and 300 in optics. 300 schoolchildren solved problems in kinematics and thermodynamics, 200 in kinematics and optics, 150 in thermodynamics and optics. 100 people solved problems in kinematics, thermodynamics and optics. How many schoolchildren solved two problems?
Answer: 350.
Solution:
First, we define sets and introduce notation. There are three of them:
- many problems in kinematics (“K”);
- many problems in thermodynamics ("T");
- many problems in optics ("O").
Let us depict using the Euler-Venn diagram what is given to us according to the condition:
Let's depict what we need to find:
Let us determine the number of schoolchildren for all possible areas:
0) Region K=0, T=0, O=0: not defined.
1) Region K=0, T=0, O=1: 50 schoolchildren.
2) Region K=0, T=1, O=0: no schoolchildren.
3) Region K=0, T=1, O=1: 50 schoolchildren.
4) Area K=1, T=0, O=0: no schoolchildren.
5) Region K=1, T=0, O=1: 100 schoolchildren.
6) Region K=1, T=1, O=0: 200 schoolchildren.
7) Region K=1, T=1, O=1: 100 schoolchildren.
Let's write the values of the areas into the table:
| № region | TO |
T |
ABOUT |
Quantity schoolchildren |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
- |
| 1 | 0 |
0 |
1 |
50 |
| 2 | 0 |
1 |
0 |
0 |
| 3 | 0 |
1 |
1 |
50 |
| 4 | 1 |
0 |
0 |
0 |
| 5 | 1 |
0 |
1 |
100 |
| 6 | 1 |
1 |
0 |
200 |
| 7 | 1 |
1 |
1 |
100 |
Let's display the values for all areas using a diagram:
Let's define x.
x=200+100+50=350.
We got it, 350 schoolchildren solved two problems.
Task 4.
A survey was conducted among passers-by. The question was asked: “What pet do you have?” According to the survey results, it turned out that 150 people have a cat, 130 have a dog, and 50 have a bird. 60 people have a cat and a dog, 20 have a cat and a bird, 30 have a dog and a bird. 70 people do not have a pet at all. 10 people have a cat, a dog, and a bird. How many passers-by took part in the survey?
Answer: 300.
Solution:
First, we define sets and introduce notation. There are three of them:
- many people who have a cat (“K”);
- many people who have a dog (“C”);
- a lot of people who have a bird ("P").
Let us depict using the Euler-Venn diagram what is given to us according to the condition:
Let's depict what we need to find:
Let's determine the number of people for all possible areas:
0) Region K=0, S=0, P=0: 70 people.
1) Area K=0, S=0, P=1: 10 people.
2) Region K=0, S=1, P=0: 50 people.
3) Area K=0, S=1, P=1: 20 people.
4) Region K=1, S=0, P=0: 80 people.
5) Area K=1, T=0, O=1: 10 people.
6) Area K=1, T=1, O=0: 50 people.
7) Area K=1, T=1, O=1: 10 people.
Let's write the values of the areas into the table:
| № region | TO |
C |
P |
Quantity Human |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
70 |
| 1 | 0 |
0 |
1 |
10 |
| 2 | 0 |
1 |
0 |
50 |
| 3 | 0 |
1 |
1 |
20 |
| 4 | 1 |
0 |
0 |
80 |
| 5 | 1 |
0 |
1 |
10 |
| 6 | 1 |
1 |
0 |
50 |
| 7 | 1 |
1 |
1 |
10 |
Let's display the values for all areas using a diagram:
Let's define x:
x=U (universe)
U=70+10+50+20+80+10+50+10=300.
We found that 300 people took part in the survey.
Task 5.
120 people entered one specialty at one of the universities. Applicants took three exams: in mathematics, computer science and the Russian language. 60 people passed mathematics, 40 - computer science. 30 applicants passed mathematics and computer science, 30 - mathematics and Russian language, 25 - computer science and Russian language. 20 people passed all three exams, and 50 people failed. How many applicants passed the Russian language test?
To visually represent sets, Euler–Venn diagrams (named after the mathematicians Leonhard Euler (1707–1783) and John Venn (1834–1923)) are used. Sets are denoted by regions on a plane, and the elements of the set are conventionally located within these regions. Often all the sets in a diagram are placed inside a rectangle, which represents a universal set. If an element belongs to more than one set, then the regions corresponding to such sets must overlap so that a common element can simultaneously be in the corresponding regions. The choice of the shape of the areas representing sets in diagrams can be arbitrary (circles, polygons, etc.).
For example, using Euler–Venn diagrams it is possible to show that a set is a subset of a set (Fig. 3).
Let us illustrate the above operations on sets using Euler–Venn diagrams: a) union of sets and; b) intersection of a set; c) set difference (without); d) addition of a set to a universal set (Fig. 4, A, b, V, G).
Example 1. Prove the identity using Euler–Venn diagrams.
Solution
Let us construct the complement of the set to the universal set (Fig. 5, A). The set corresponds to the shaded area (Fig. 5, b). Thus, it is clear that in Euler–Venn diagrams the sets and are depicted in the same way, therefore.
Example 2. Show that.
Solution
Let us construct a set corresponding to the left side of the given identity. The set is represented by the shaded area in Fig. 6, A. The set corresponds to the shaded area in Fig. 6, b.
The set represents the area shaded in both previous diagrams, which is why it is presented in Fig. 6, V darker area.
Let us construct a set corresponding to the right side of the given identity.
The sets and are represented by the shaded area in Fig. 7, A and 7, b respectively.
The set is depicted by the shaded area in Fig. 7, V.
Comparing Fig. 6, V and rice 7, V, we see that the Euler–Venn diagrams are depicted in the same way, therefore .
Questions and tasks for independent solution
1. Draw sets using Euler–Venn diagrams:
2. Describe the sets corresponding to the shaded parts in Fig. 8, A, b, V, G, using Euler–Venn diagrams:
3. Using Euler–Venn diagrams, show that:
1.4. Properties of set operations
The set operations introduced above have the following properties.
1. – commutativity.
2.
– associativity.
3.
– distributivity.
4. – idempotency.
5.
– laws of identity.
6. – laws of complement.
7. – de Morgan’s laws.
8. – laws of absorption.
9.
– laws of gluing.
10.
- Poretsky's laws.
Example 1. Based on the properties of set operations, simplify the expression.
Solution
= /de Morgan's law/ =
= = /law of distributivity/ =
= = /law of commutativity/ =
= = /law of distributivity/ =
/law of commutativity/ =
/laws of addition/ =
= /laws of commutativity and identity/ =
= = /definition of symmetric difference/ =.
As already mentioned, the cardinality of a finite set is the number of its elements. The following theorem gives a simple rule for calculating the power of the union of two sets.
Theorem of inclusions and exclusions. The cardinality of the union of two sets is equal to the difference between the sum of the cardinalities of these sets and the cardinality of their intersection, i.e.
Proof
The proof of the statement is most conveniently illustrated graphically. As shown in Fig. 9, the set consists of subsets:,and, which do not have common elements. Therefore, and.
Let us introduce the following notation:
Q.E.D.
Example 2. Each of the 63 first-year students studying computer science at the university can attend additional lectures. If 16 of them are also taking an accounting course, 37 are taking a business course, and 5 are studying both of these disciplines, then how many students do not take these additional classes at all?
Solution
Let us introduce the following notation:
Therefore, is the number of students who do not attend additional courses.
Note 1. The inclusion and exclusion theorem can be formulated for the case of three sets:
Example 3. There are 42 students studying on the course. Of these, 16 are involved in the athletics section, 24 in the football section, 15 in the chess section, 11 in both the athletics and football sections; 8 – in both track and field and chess; 12 – in both football and chess; and 6 – in all three sections. The rest of the students are interested in tourism. How many students are tourists?
Solution
Let us introduce the following notation:
From the problem conditions: ,,,,,,and.
Where from, i.e. – the number of students involved in tourism.
Note 2. When solving the above problems, it is convenient to use Euler–Venn diagrams.
Problems to solve independently
Prove the identities using the properties of set operations:
2. 33 people came to the dining room for lunch. 10 people ordered soup, 16 - pilaf, 30 - compote, 7 people ordered all three dishes, 8 people ordered soup and pilaf, 14 people ordered soup and compote. How many people ordered pilaf and compote?
3. In the student group, 12 people study English, 13 - German, 16 - French, 4 - only English and German, 3 - only English and French, 5 - all three languages. There are no English-only students in the group. Two people study only German, six people study only French. One student in the group does not study any of the listed languages. How many students are in the group?
Human thinking is structured in such a way that the world appears to consist of individual “objects”. Philosophers have long known that the world is a single inextricable whole, and the selection of objects in it is nothing more than an arbitrary act of our thinking, allowing us to form a picture accessible to rational analysis. But be that as it may, the identification of objects and their collections is a natural way of organizing our thinking, so it is not surprising that it underlies the main tool for describing exact knowledge - mathematics.
The concept of set is one of the fundamental undefined concepts of mathematics. At a minimum, what is known about a set is that it consists of elements. For definiteness, we accept the following formulations.
Definition. Under the multitude S we will understand any collection of defined and distinguishable objects, conceived as a single whole. These objects are called elements of the set S.
Definition. A set is understood as the unification into a single whole of certain completely distinguishable objects (objects), which are then called elements of the set they form.
Sets are usually denoted in capital letters of the Latin alphabet: A, B, C, ...; and the elements of sets are in lowercase letters: a, b, c, … .
If the object X is an element of the set M, then they say that X belongs M: Hm. Otherwise it is said that X do not belong M: Hm.
In this intuitive definition, which belongs to the German mathematician G. Cantor, the essential fact is that the collection of objects is itself considered as one object, thought of as a single whole. As for the objects themselves, which can be included in the set, there is considerable freedom regarding them.
Example 1
This could be a set of students studying at a university, a set of prime numbers, etc.
Definition. A bunch of A called a subset of the set IN, if every element from A is an element IN(denote). If A is a subset IN And IN is not a subset A, then they say that A is a strict (proper) subset IN(denote).
Definition. A set that does not contain elements is called empty (denoted by Æ); it is a subset of any set. A bunch of U is called universal, that is, all the sets under consideration are its subset.
Let's consider two definitions of equality of sets.
Definition. Sets A And IN are considered equal if they consist of the same elements, write A=B, otherwise A¹ IN.
Definition. Sets A And IN are considered equal if 
There are the following ways to define sets :
1) listing the elements: M = (a 1 , a 2 , …, a k} , i.e. a list of its elements;
2) characteristic predicate: M = (x | P(x)} (description of the characteristic properties that its elements must have);
generating procedure: M = { x | x= f} , which describes a method for obtaining elements of a set from already obtained elements or other objects. In this case, the elements of the set are all objects that can be
1) are constructed using this procedure. For example, the set of all integers that are powers of two.
Comment. When defining sets by enumeration, element designations are usually enclosed in curly braces and separated by commas. Only finite sets can be specified by enumeration (the number of elements of a set is finite, otherwise the set is called infinite). A characteristic predicate is some condition expressed in the form of a logical statement or procedure that returns a logical value. If the condition is met for a given element, then it belongs to the defined set, otherwise it does not belong. A generating procedure is a procedure that, when run, generates some objects that are elements of the set being defined. Infinite sets are defined by a characteristic predicate or a generating procedure.
Example 2
1) M = (1, 2, 3, 4)– listing the elements of a set.
2) is a characteristic predicate.
Definition. Cardinality of a finite set A is the number of its elements.
The cardinality of a set is denoted by: | A|.
Example 3
|| = 0; |{}| = 1.
Definition. Sets are said to be of equal cardinality if their cardinalities coincide.
Definition. The set of all subsets of a set A is called the Boolean P(A).
It is known that if a set A contains n elements, then the set P(A) contains 2 n elements. In this regard, the notation for set-degree of set is also used A as 2 A.
Example 4
A = (0, 1, 2),P(A) = { , {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}} .
Sets can be represented geometrically using Euler-Venn diagrams. The construction of the diagram consists of drawing a large rectangle representing the universal set U, and inside it - circles (or some other closed figures) representing sets. The shapes must intersect in the most general way required by the problem and must be labeled accordingly. Points lying inside different areas of the diagram can be considered as elements of the corresponding sets. With the diagram constructed, you can shade certain areas to indicate newly formed sets.
Set operations are considered to obtain new sets from existing ones.
Definition. Union of sets A And IN is a set consisting of all those elements that belong to at least one of the sets A,IN(Fig. 1.1):
Rice. 1.1. Euler-Venn diagram for unification
Definition. Intersection of sets A And IN is a set consisting of all those and only those elements that simultaneously belong to the set A, and many IN(Fig. 1.2):
Rice. 1.2. Euler-Venn diagram for intersection
Definition. Set difference A And IN is called the set of all those and only those elements A, which are not contained in IN(Fig. 1.3):
Rice. 1.3. Euler-Venn diagram for difference
Definition. Symmetric set difference A And IN is the set of elements of these sets that belong either only to the set A, or only to the set IN(Fig. 1.4):
Rice. 1.4. Euler-Venn diagram for symmetric difference
Definition. An absolute complement to the set A is the set of all those elements that do not belong to the set A(Fig. 1.5):
Rice. 1.5. Euler-Venn diagram for absolute complement
Example 5
Using Euler-Venn diagrams we prove the identity:
Let's look at the left side of the relation and perform the steps in order:
1) find the intersection of sets IN And WITH() (Fig. 1.6, a);
2) find the union of the resulting set with the set A() (Fig. 1.6, b).
Let us consider the right side of the relation 
:
1) find the union of sets A And IN(Fig. 1.6, c);
2) find the union of sets A And WITH(rice.
1.6, d);
3) find the intersection of the last two sets and ( ) (Fig. 6, d):
In both cases (Fig. 1.6, b) and (Fig. 1.6, e) we obtain equal sets. Therefore, the original relation is valid.
Rice. 1.6. Proof of identity using Euler-Venn diagrams
Let us consider the basic identities of set algebra. For arbitrary sets A,IN, And WITH the following relations are valid (Table 1.11):
Table 1.11 Basic identities of set algebra
|
An association |
Intersection |
|
1. Commutativity of the union |
1'. Commutativity of intersection |
|
2. Association associativity |
2′. Intersection associativity |
|
3. Distributivity of a union with respect to intersection |
3′. Distributivity of intersection relative to union |
|
4. Laws of action with empty and universal sets |
4'. Laws of action with empty and universal sets |
|
5. Law of union idempotency |
5'. Law of Idempotency of Intersection |
|
6. De Morgan's Law |
6′. De Morgan's Law |
|
7. Law of absorption
|
7′. Law of Absorption
|
|
8. Law of gluing
|
8'. Law of Bonding
|
|
9. Poretsky's Law
|
9'. Poretsky's Law
|
|
10. Double complement law |
|
