cadaVR anatomy by Mozaik Education

Graphs

In Figure 35 you can see a part of the House of Windsor family tree.

George V

(\latex{ 1865–1936 })

Mary of Teck

(\latex{ 1867–1953 })

Elizabeth Bowes-Lyon

(\latex{ 1900–2002 })

George VI

(\latex{ 1895–1952})

Mary

(\latex{ 1897–1965})

Henry

(\latex{ 1900–1974})

Wallis Simpson

(\latex{ 1895–1986})

Edward VIII

(\latex{ 1894–1972})

Elizabeth II

(\latex{ 1926–2022})

Philip

(\latex{ 1921–2021})

Margaret

(\latex{ 1930–2002})

Camilla

(\latex{ 1947–})

Charles

(\latex{ 1948–})

Diana

(\latex{ 1961–1997})

Anne

(\latex{ 1950–})

Andrew

(\latex{ 1960–})

Edward

(\latex{ 1964–})

William

(\latex{ 1982–})

Catherine

(\latex{ 1982–})

George

(\latex{ 2013–})

Charlotte

(\latex{ 2015–})

Louis

(\latex{ 2018–})

Henry

(\latex{1984–})

Archie

(\latex{2019–})

Lilibet

(\latex{2021–})

Meghan

(\latex{1981–})

Figure 35

Draw your own family tree. Represent at least \latex{ 3 } generations.

Example 1

We know the following about the overland routes connecting \latex{ 5 } villages of an island. \latex{ A } and \latex{ B } are connected by two roads, one road was built between \latex{ A } and \latex{ C } and between \latex{ B } and \latex{ C } each. Out of village \latex{ D } there is a direct road to both \latex{ C } and \latex{ E }. These roads do not intersect each other. Because of the dense vegetation and the cliffs one can travel only on the roads on the island.

Is it possible to get from \latex{ A } to \latex{ E? }
Is it possible to get from \latex{ A } to \latex{ E }, if it is not possible to travel on the road between \latex{ A } and \latex{ C } because of the snow?
Is it possible to get from \latex{ E } to \latex{ B }, if the road between \latex{ C } and \latex{ D } is closed?

Let us sketch. The villages correspond to points and the roads connecting them correspond to the lines. The answers can be read from the figure. (Figure 36)

Solution (a)

From \latex{ A } one can get to \latex{ E } through \latex{ C } and \latex{ D }.

Solution (b)

If we cannot go from \latex{ A } directly to \latex{ C }, then by a roundabout way towards \latex{ B } we can reach \latex{ C } then both \latex{ D } and \latex{ E }.

Solution (c)

As all the possible routes from \latex{ E } to \latex{ B } go through the road connecting \latex{ C } and\latex{ D }, if this one is closed, then it is not possible to get from \latex{ E } to \latex{ B }.

It helped during the solution of the example that we drew a figure where the villages corresponded to points and two points were connected if there was a road between the corresponding villages. The connecting line could be a straight or a curved line, the only important thing was which two points were connected. This type of “figure” can be useful when solving other exercises too.

DEFINITION: A figure consisting of points and lines – connecting some (possibly all but it can also happen that none) of the point pairs that can be made of the points – is called a graph. The points are the points (vertices) of the graph, the lines are the edges of the graph. (Figure 37)

Notations:
The set of the points (vertices) of graph \latex{ G } is denoted by \latex{ V }(\latex{ G }).
The set of the edges of graph \latex{ G } is denoted by \latex{ E }(\latex{ G }).

DEFINITION: The edge both end-points of which are the same point is called a loop. If we draw more than one edge between two points then we get a multiple edge. A graph is called a simple graph if the set of its points and edges is finite and there is neither a loop nor a multiple edge in the graph. (Figure 37)

Henceforth we generally deal with simple graphs.

If for example a simple graph has five points, then it can have at most as many edges as many ways we can pick two out of five, i.e. \latex{\frac{5\times 4}{2}}.

Example 2

A tennis tournament for the local old boys is organised in the single-elimination system, i.e. the players are paired and this way they play against each other, the winner qualifies for the next round, the loser fails to progress in the tournament. The players were ranked as \latex{ 1–8 } and were placed on the table so that the better a player is the weaker opponents he would have. The result of the tournament is represented on the graph shown in Figure 38. If two players play a match against each other, then we write the number of the winner to the common end-point of the edges incident with the representing points.

Who played the final?
How many matches were played during the tournament?
Who can be the second best player, and how many more matches are necessary to find out who is the second best?

Solution (a)

The final was played by Player 1 and 3, and finally Player 3 won the tournament.

Solution (b)

In Figure 38 we can count that all together \latex{ 7 } matches were played in the tournament.

It can also be explained in the way that except for the champion everyone lost exactly one match. As after each match there is one loser, the number of matches equals to the number of losers, i.e. it is \latex{ 1 } less than the number of all players: \latex{ 8 – 1 = 7 }.

Solution (c)

The second best player can be any of the players who lost against the champion, as the others lost against someone who also lost against someone else.

The champion is Player 3 and he won against Player 1, 2 and 6. We need two matches to decide who the best is among three players, for example following the arrangement represented by the graph shown in Figure 39.

⯁ ⯁ ⯁

With the help of graphs we can represent the atomic formula of the molecules of the organic compounds. For example:

methane (CH₄)

acetic acid (CH₃COOH)

ethyl-alcohol (C₂H₅OH)

Let us observe how many chemical bonds the atoms form. In organic compounds the carbon atom always forms \latex{ 4 }, the oxygen atom forms \latex{ 2 } bonds and the hydrogen atom forms \latex{ 1 } bond. If we consider the atomic formula as a graph, then each atom forms as many bonds as the number of edges incident with their corresponding point.

DEFINITION: The degree (deg) of a point (vertex) of a graph is the number of edges incident with it.

Example 3

In Figure 40 the nutritional relationships of a few animals living in the meadow are represented.

Which animals are the top predators?
Let us create a food chain from the members of the represented community.

Solution (a)

As the animal at the starting point of the arrow is food for the animal at the end-point of the arrow, the top predators correspond to those points which are not starting points of any arrows, thus the rook and the white stork are the top predators.

Solution (b)

An example of food chain along the arrows: gramineae → locust → green tree fog → white stork.

DEFINITION: The figure consisting of points and directed lines connecting point pairs is called a directed graph. Its edges are called directed edges.

Exercises

{{exercise_number}}. The prime factorisation of which natural number is represented by the graph? Give the prime factorisation as a product.

a)

b)

\latex{ 8 }

\latex{ 2 }

\latex{ 3 }

\latex{ 2 }

\latex{ 5 }

\latex{ 9 }

\latex{ 2 }

{{exercise_number}}. Draw graphs for the prime factorisation of the following numbers.

\latex{ 54 }

\latex{ 96 }

\latex{ 144 }

{{exercise_number}}. How can we plan the arrangement of a tennis tournament of \latex{ 32 } players so that the \latex{ 8 } seeded players meet as late as possible, and so that the better a player is the weaker opponents the player would have?

{{exercise_number}}. There are \latex{ 16 } bags which seem to be alike but have different weights. In case we use a balancing scale what is the minimum number of necessary measurements to select

the heaviest bag;

the second heaviest bag?

{{exercise_number}}. Represent the phylums and classes of the animal kingdom on a graph.

{{exercise_number}}. Let us come up with a combinatorial exercise the solution of which is given by the following graphs:

a)

b)

{{exercise_number}}. Four towns are given among which there are no three or more which are on one straight line. It is planned to connect the towns with a road system consisting of four straight line segments, without any stops in between. Intersections are allowed but at these places an underpass or an overpass should be built. How many such systems are possible?

{{exercise_number}}. From the community of the African savannah give the name of at least eight living beings and draw a graph which shows their nutritional relationships.

{{exercise_number}}. Interpret the logistic system shown in the figure.

delivery

delivery
warehouse

production

distribution
warehouse

distribution

sales

processing
of orders

orders

procurement

information flow

material flow

{{exercise_number}}. Draw the graph the points of which are the natural numbers \latex{ 0–20 }, and an arrow points from number \latex{ a } to number \latex{ b } if number \latex{ a } is a divisor of number \latex{ b }. From which number do arrows start to all other numbers? To which number do arrows point from all other numbers?

{{exercise_number}}. Three married couples arrived to Mr Smith and his wife for a party. At the greetings some of them shook hands with each other, but none of them shook hands with their own spouse. When everyone was there Mr Smith asked them how many people being present they had shaken hands with. With how many people did the wife of Mr Smith shake hands if we know that Mr Smith got seven different answers to his question?

Puzzle

\latex{ 7 } agents of the secret agency are observing each other too.
Agent 001 is observing the agent observing Agent 002.
Agent 002 is observing the agent observing Agent 003.

…
And so on, Agent 007 is observing the agent observing Agent 001.

Who is observing who?

Mathematics 9.

-