کارت شما خالی است
Tree graphs (extra-curricular topic)
Example 1
We planted a tree in the spring, which consisted of one branch. This branch had been growing for two years, and then by the end of the second year in the spring it sent forth a new branch, and after that it sent forth a new branch every spring. The new shoots only grow in the first year, and they start sending forth a new branch at the end of the second year, and then they send forth a new branch in the spring every year. How many branches will there be at the end of the sixth year (when the new shoots have not pushed out yet), if none of the branches break off in the meantime?
Solution
Let us represent the growth of the tree by denoting the years and the number of the branches at the end of the year. It can be seen in the figure that there will be \latex{8} branches at the end of the sixth year. (Figure 51)
\latex{6}
\latex{5}
\latex{4}
\latex{3}
\latex{2}
\latex{1}
\latex{0}
Years
Figure 51
The terms of the
Fibonacci sequence:
Fibonacci sequence:
\latex{1;\, 1;\, 2;\, 3;\, 5;\, 8;\, 13;\, 21;\, 34;\, ...}
\latex{f_1=1; f_2=1; f_n=f_{n-1}+f_{n-2}}
It can be observed that the branches, which were there at the end of the \latex{5}th year, remained by the end of the \latex{6}th year. Those branches should be added to these, which were sent forth at the end of the \latex{5}th year by the branches existing at the end of the \latex{4}th year. Thus the number of the branches at the end of the \latex{6}th year is the sum of the number of the branches existing at the end of the \latex{4}th and the \latex{5}th year. So the first two terms are \latex{1} and after that every term is the sum of the previous two terms in the sequence of the number of branches. Based on this rule the sequence can be continued. This sequence is the Fibonacci sequence.
By representing the growth of the tree by a graph the example can be rephrased as follows: how many points of degree one does the graph have apart from the starting point?
DEFINITION: A graph is growing by sending forth branches, if it can be built by starting from a point so that to an existing point we attach a new edge the other end-point of which will be a new point.
A connected graph, which is growing by sending forth branches, is called a tree graph. The points of degree one of the tree graph are called leaves.
Example 2
Mrs. Smith bought a hen in the market. Once the hen laid two eggs, it was eaten for dinner. Hens or cocks hatched from the eggs. They ate every cock, but they ate the hens only once they had laid two eggs. It went on for years like this, until only cocks remained, and these were also eaten. It turned out that they ate a total of \latex{2004} cocks. Can we tell how many hens they ate?
Solution
By trying a few simpler cases (Figure 52) we assume that the number of the cocks is \latex{1} more than the number of the hens. Let \latex{C} be the number of the cocks, and let \latex{H} be the number of the hens. Let us verify the conjecture \latex{C = H + 1}.
\latex{C}
\latex{C}
\latex{C}
\latex{C}
\latex{C}
\latex{H}
\latex{H}
\latex{H}
\latex{H}
Figure 52
The number of the eggs in the story is: \latex{2H}.
On one hand the number of the chickens is \latex{2H + 1}, because it started with one hen, then a chicken was hatched from every egg. On the other hand it is \latex{H + C}, because a chicken is either a hen or a cock. Hence \latex{2H +1= H + C}, which implies \latex{C = H + 1}, so the number of the cocks is \latex{1} greater than the number of the hens. Mrs. Smith and her family ate \latex{2003} hens.
\latex{C}
\latex{C}
\latex{C}
\latex{C}
\latex{C}
\latex{H}
\latex{H}
\latex{H}
\latex{H}
Figure 53
\latex{C}
\latex{C}
\latex{C}
\latex{H}
\latex{H}
\latex{H}
\latex{H}
\latex{H}
\latex{C}
\latex{C}
Let us draw a graph in which the points correspond to the chickens, and two edges start from every point corresponding to a hen, because it lays two eggs from which two chickens hatch. It is a tree graph, in which the number of the points is equal to the sum of the number of the hens and the cocks (\latex{H+C}), and the number of the edges is equal to the number of the eggs. Since except for the first hen every chicken hatches from an egg corresponding to an edge, the number of the chickens is one greater than the number of the eggs, that is the number of the points in the tree graph is one greater than the number of the edges. (Figure 53)
THEOREM: In a tree graph the number of the points is one greater than the number of the edges.
Proof
According to the definition a tree graph is growing by sending forth branches starting from a point, thus we add an edge and a point to the graph each time. By adding the starting point finally the number of the points is one greater than the number of the edges.
Example 3
The roads were built between six villages so that there is a direct road from every village to every village. In the winter after a heavy snow all the roads became impassable. At least how many stages (direct roads connecting two villages) should be cleared so that one can get from any village to any village on road?
Solution
If the snow plough clears for example the roads corresponding to the red edges of the graph shown in Figure 54, then by clearing \latex{5} stages it can be reached that one can get from any village to any village.
Clearing \latex{5} stages is also necessary, because the snow plough starts from a village, then it needs to clear a stage to get to another village. So to free the remaining \latex{5} villages at least \latex{5} stages are needed to be cleared. The roads cleared by the snow plough are attached to each other like a tree graph grows its branches.
Figure 54
Based on the example it can be assumed that a tree graph is a minimal connected graph, i.e. by leaving away any of its edges it will not be connected anymore. Let us realise that if the snow plough carries on clearing the roads, after clearing the sixth stage there will surely be a cycle in the graph of the cleared roads. Based on this it can be assumed that a tree graph is a maximal acyclic graph, i.e. by adding any of the edges there will be a cycle in the graph.
THEOREM: A connected graph is a tree graph if and only if there is no cycle in it, but by drawing an edge between any two of its points there will be a cycle in it.
THEOREM: A connected graph is a tree graph if and only if by leaving away any of its edges it will not be connected anymore. (We do not leave away the end-points with the edge.)
Proof
Tree graph \latex{\Rightarrow} maximal acyclic
A tree graph is growing by sending forth branches, so no edge can be drawn between two existing points, thus there cannot be a cycle in it.
Let us choose two arbitrary points without an edge between them; let us denote them by \latex{A} and \latex{B}. Because of the connectedness there is a path from \latex{A} to \latex{B}. By adding the edge \latex{AB} to this path a cycle is obtained.
In the meantime we also showed the following:
If we connect two points of a connected graph by an edge, then there will surely be a cycle in the graph.
Tree graph \latex{\Rightarrow} maximal acyclic
If there is no cycle in the graph, therefore there is a point of degree one in it. This point and the edge starting from it is the branch of the tree graph grown as last. When leaving it away the remaining graph is also acyclic, thus we can continue with leaving away the edges with the previous method; finally one point will be left. By adding the edges in the opposite order as left away the growth of the graph by shoots is obtained, so it is a tree graph.
(As by drawing any of the edges the graph will not be acyclic anymore, the graph is connected, because otherwise we could draw an edge between the parts not connected so that there would be no cycle in it.)
Maximal acyclic \latex{\Rightarrow} minimal connected
A maximal acyclic graph is surely connected; it could be seen previously.
If the graph was not minimal connected, then by leaving away one of its edges the graph would stay connected. By adding the edge just left away to this connected graph there would be a cycle in it, i.e. the graph would not be acyclic.
Minimal connected \latex{\Rightarrow} maximal acyclic
There cannot be a cycle in the graph, because then it would have an edge by leaving away which the graph would stay connected, so it could not be minimal connected.
If the graph was not maximal acyclic, then there would be an edge by adding which it would still stay acyclic. But it is not possible, because by drawing any edge in a connected graph there will surely be a cycle.
Example 4
Peter thinks of a natural number not greater than \latex{31}. Paul asks questions to find the number Peter thought of; Peter answers with yes or no to these questions. With at least how many questions can Paul find the number Peter thought of?
Solution
Paul's strategy is to half the set of the possible numbers with every question. (Figure 55)
\latex{0-31}
Is it greater than \latex{15}?
\latex{0-15}
Is it greater than \latex{8}?
\latex{16-31}
Is it greater than \latex{23}?
n
y
\latex{0-7}
Is it greater than \latex{3}?
\latex{8-15}
Is it greater than \latex{11}?
\latex{16-23}
Is it greater than \latex{19}?
\latex{24-31}
Is it greater than \latex{27}?
\latex{0} - \latex{3}
\latex{4} - \latex{7}
\latex{8} - \latex{11}
\latex{12} - \latex{15}
\latex{16} - \latex{19}
\latex{20} - \latex{23}
\latex{24} - \latex{27}
\latex{28} - \latex{31}
\latex{0} - \latex{1}
\latex{2} - \latex{3}
\latex{4} - \latex{5}
\latex{6} - \latex{7}
\latex{8} - \latex{9}
\latex{10} - \latex{11}
\latex{12} - \latex{13}
\latex{14} - \latex{15}
\latex{16} - \latex{17}
\latex{18} - \latex{19}
\latex{20} - \latex{21}
\latex{22} - \latex{23}
\latex{24} - \latex{25}
\latex{26} - \latex{27}
\latex{28} - \latex{29}
\latex{30} - \latex{31}
\latex{31}
\latex{30}
\latex{29}
\latex{28}
\latex{27}
\latex{26}
\latex{25}
\latex{24}
\latex{23}
\latex{22}
\latex{21}
\latex{20}
\latex{19}
\latex{18}
\latex{17}
\latex{16}
\latex{15}
\latex{14}
\latex{13}
\latex{12}
\latex{11}
\latex{10}
\latex{9}
\latex{8}
\latex{7}
\latex{6}
\latex{5}
\latex{4}
\latex{3}
\latex{2}
\latex{1}
\latex{0}
n
y
n
y
Figure 55
With this strategy Paul can find the number Peter thought of with \latex{5} questions.
Less questions than these cannot be enough, because we can divide the set of the possible numbers into at most two parts with one polar (yes/no) question.
Example 5
Let us give the prime factorisation of \latex{2,520}.
Solution
Let us transform \latex{2,520} to a product with two factors, and let us represent it with a tree graph. Let edges lead from the point representing \latex{2,520} to the two factors. We are going to do it with every composite number, thus the prime factors of \latex{2,520} will be obtained on the leaves (Figure 56). The factorisation can be done in several ways; however we always get the same prime factors. So:
\latex{2,520 = 2^3 \times 3^2 \times 5 \times 7}.
Figure 56
\latex{2,520}
\latex{20}
\latex{126}
\latex{2}
\latex{10}
\latex{2}
\latex{63}
\latex{2}
\latex{5}
\latex{3}
\latex{21}
\latex{3}
\latex{7}
Exercises
{{exercise_number}}. New roads are being built between six villages. At least how many roads should be built, if we want to get from every village to every village on a new road?
{{exercise_number}}. Draw the graph of the tree, which starts with one branch, and all its branches send forth a new branch every year. How many branches will this tree have by the end of the sixth year? How can you give the sequence of the number of branches?
{{exercise_number}}. Hydrocarbons consist only of carbon and hydrogen. The hydrogen atom has one as its atomic number, the carbon atom has four as its atomic number, and it can be attached to a hydrogen atom or also to another carbon atom. Two carbon atoms can be attached to each other even with two or three valences. The hydrocarbons are classified based on their structure, and also their denomination is based on this.
These can be seen in the figure below with a simple example in each case:
Saturated hydrocarbons (paraffins)
(there are no double bonds between the carbon atoms)
(there are no double bonds between the carbon atoms)
Unsaturated hydrocarbons
(there are double or triple bonds between the carbon atoms)
(there are double or triple bonds between the carbon atoms)
alkanes
(open-chain)
(open-chain)
cycloalkanes
(ring)
(ring)
alkenes
(one double bond)
(one double bond)
alkynes
(one triple bond)
(one triple bond)
arenes
ethane
cyclobutane
ethylene
acetylene
benzene
C
C
H
H
H
H
H
H
C
C
C
C
H
H
H
H
H
H
H
H
C
C
H
H
H
H
C
C
H
H
C
C
C
C
C
C
H
H
H
H
H
H
- Characterise the hydrocarbons with graph theory concepts (tree graph, cycle, multiple edge, degree).
- Can the following combine to form a chemical combination, and if so, which group can it belong to:
- \latex{33} carbon atoms and \latex{93} hydrogen atoms?
- \latex{10} carbon atoms and \latex{22} hydrogen atoms?
- \latex{5} carbon atoms and \latex{10} hydrogen atoms?
- \latex{10} carbon atoms and \latex{8} hydrogen atoms?
- How many hydrogen atoms are needed for six carbon atoms to form an open-chain saturated hydrocarbon? Draw.
{{exercise_number}}. Give the prime factorisation of the following numbers with the help of graphs: \latex{10,586}; \latex{56,235}.
{{exercise_number}}. Draw it with a graph: how many matches are played by \latex{n} teams in a single-elimination system by the time it turns out which team the winner is, if the teams are paired, the winner is qualified for the next round, the loser fails to progress. If a team does not have a pair, then it is qualified for the next round without a match played. How many matches are needed if they also want to find out which team is the second best?
- \latex{n=32};
- \latex{n=48};
- Without drawing the graph solve the problem also for the cases \latex{n = 1,024} and \latex{n = 2,765,289.}
{{exercise_number}}. Which of the following statements are true and which are false?
- Every tree graph has at least two points of degree one.
- Every tree graph has at least three points of degree one.
- There is a tree graph in which there is a closed Eulerian trail.
- There is a tree graph, which has two points with two different paths between them.
{{exercise_number}}. Five villages are given – let us denote them by \latex{A}, \latex{B}, \latex{C}, \latex{D}, \latex{E} – and no three or more of them are collinear. Four roads consisting of straight stages are planned to be built between the villages so that one can get from every village to every village (not necessarily directly, possibly by touring several stages). The roads can cross each other, but in this case an overpass will be built, thus one cannot get from one road to the other one on the way. How many different road networks can be built?
{{exercise_number}}. By starting with an arbitrary two-digit number let one step be calculating the sum of the squares of the digits of the number. For example: \latex{23 \rarr 13 \rarr 10 \rarr 1}. Let us call a number a happy number, if \latex{1} is obtained at the end of the process; let the other numbers be called sad numbers. Find happy and sad numbers.
Puzzle
- Are the grandfathers of my great-grandfathers the same people as the great-grandfathers of my grandfathers?
- There are two short turnouts on the stage \latex{BC} of the main line, as it can be seen in the figure: \latex{BA} and \latex{AC}. There is a carriage on both short stages: \latex{P} and \latex{Q}, and there is an engine on the line \latex{BC}. The two carriages should be swapped with the help of the engine so that the engine gets back to the main line. The two short stages are enough for one carriage each, but these are too short for the engine, that is if the engine goes in on the line \latex{CA}, it cannot come out on the line \latex{AB}. The carriages can be attached to each other and also to either end of the engine.
\latex{A}
\latex{B}
\latex{C}
\latex{P}
\latex{Q}
\latex{E}