The following is a short preparation guide containing all the concepts covered in Secondary 5 in the CST pathway. To explain everything, each formula will be followed by an example and a link to a concept sheet in our virtual library.
Functional form
||y = ax + b|| where ||a = \dfrac{\Delta y}{\Delta x} = \dfrac{y_2 - y_1}{x_2 - x_1}||
General form
|0 = Ax + By + C| where |A, B, C \in \mathbb{Z}|
Using the information in the table below, determine the equation for the straight line in the general form.
-
Find the slope according to |\dfrac{\Delta y}{\Delta x}.|
||a = \dfrac{2 - 4{.}4}{-0{.}5 - 0{.}5} = 2{.}4|| -
Find the initial value |(b)| by substituting in one of the points on the graph.
||\begin{align} f(x) &= 2{.}4 x + b\\ 2 &= 2{.}4 (-0{.}5) + b \\ b &= 3{.}2 \end{align}|| -
Transform the value of parameters |a| and |b| to their simplified fractional form.
||\begin{align} y &= 2{.}4x + 3{.}2 \\ y &= \dfrac{24}{10}x + \dfrac{32}{10} \\ y &= \dfrac{12}{5}x + \dfrac{16}{5} \end{align}|| -
Find a common denominator for all the terms in the equation.
||\begin{align} y &= \dfrac{12}{5}x + \dfrac{16}{5} \\ \Rightarrow\ \frac{5y}{5} &= \dfrac{12x}{5} + \dfrac{16}{5} \end{align}|| -
Make the equation equal to |0.|
||\begin{align} \frac{5y}{\cancel{5}} &= \frac{12x}{\cancel{5}} + \frac{16}{\cancel{5}} \\ \Rightarrow 5y &= 12x + 16 \\ \Rightarrow\, \ 0 &= 12x - 5y + 16 \end{align}||
Answer: The equation of the straight line in general form is |0 = 12x - 5y + 16.|
See also
At the corner store, workers bought 4 coffees and 6 muffins for $15.06. The next day, the same group buys 3 coffees and 5 muffins for $11.97. If, the next day, these workers want to buy 6 coffees and 4 muffins, how much will they have to pay?
See also
Take the following steps to solve a system of equations by substitution:
1) Identify the variables as they relate to the unknowns
2) Create the equations according to the scenario
3) Isolate a variable in one of the two equations
4) Substitute the same variable in the other equation by the algebraic expression associated with it
5) Solve the new equation
6) Replace the value of the variable found in step 5 in one of the starting equations to find the value of the other variable
See also
Follow these steps to solve an equation system by elimination:
1) Identify the variables as they relate to the unknowns
2) Create the equations according to the scenario
3) Find equivalent equations to obtain the same coefficient of the same variable
4) Subtract the two equations
5) Isolate the remaining variable to find its value
6) Replace the value of the variable found in Step 5 into one of the starting equations to find the value of the other variable
See also
Generally, an optimization problem can be solved by following these steps:
- Identify variables
- Create the system of inequalities
- Determine the equation of the function to be optimized
- Draw the polygon of constraints
- Determine the coordinates of each of the polygon’s vertices
- Evaluate the function to be optimized for each vertex of the polygon of constraints
- Determine the coordinate(s) of the point(s) that optimize(s) the function
See also
TYPES OF EVENTS | DEFINITION | EXAMPLE |
Mutually exclusive | When they can't happen at the same time. | Rolling a six-sided die and getting a number that is a multiple of both 3 and 4. |
Not mutually exclusive | When they can occur at the same time. | Drawing a random card from a 52-card deck and getting an ace that is red. |
Dependent | When one result affects the other. | Drawing two cards successively without replacing it from a 52-card deck. |
Independant | When one result does not affect the other. | Drawing a card from a 52-card deck and rolling a six-sided die. |
However, we must not forget the types of events that have been seen in class in previous years (certain, probable, impossible, elementary, complementary, compatible, and incompatible).
See also
If |a = | the chances for and |b =| the odds against, then:
- the odds (ratio) against |\displaystyle = b : a \Rightarrow \frac {b}{b+a}|
Thus, we obtain the net winnings according to the following proportion:
In the days of the Quebec horse races, people could bet on the victories of racehorses. Each horse had odds that quantified its chances of winning. For the last race, an amateur bet |$20| for victory whose odds were |1:14.| So, what was the potential gain from his bet?
-
Apply the proportion ||\begin{align} \dfrac{20}{\text{Gain net}} &= \dfrac{\color{blue}{1}}{\color{blue}{1}+\color{red}{14}}\\\\ \dfrac{20}{\text{Gain net}} &= \dfrac{\color{blue}{1}}{15}\end{align}||
-
Solve with the cross product ||\begin{align} \dfrac{20}{\text{Gain net}} &= \dfrac{\color{blue}{1}}{15}\\\\ \Rightarrow\ \text{Gain net} &= \frac{20 \times 15}{\color{blue}{1}} \\ \text{Gain net} &= 300\end{align}||
Answer: If his horse finished first in the race, the amateur would walk away with the sum of |$300.|
In some boxing matches, you can bet on a boxer's defeat. Each boxer has odds that quantify his chances of winning. For the next fight, the champion has odds of |44 : 1| for his victory. So what would be the net profit of an amateur who bets |$10| against a victory for the champion?
-
Identifying the odds against ||\begin{align} \text{Odds ratio} &= \color{blue}{44} : \color{red}{1} \\ \Rightarrow\ \text{Odds ratio} &= \color{red}{1} : \color{blue}{44}\end{align}||
-
Apply the proportion ||\begin{align} \dfrac{10}{\text{Net gain}} &= \dfrac{\color{red}{1}}{\color{red}{1}+\color{blue}{44}} \\\\ \dfrac{10}{\text{Net gain}} &= \dfrac{\color{red}{1}}{45}\end{align}||
-
Solve with the cross product ||\begin{align} \dfrac{10}{\text{Net gain}} &= \dfrac{\color{red}{1}}{45} \\\\ \Rightarrow \text{Net gain} &= \frac{10 \times 45}{\color{red}{1}} \\ \text{Net gain} &= 450\end{align}||
Answer: If the champion fails to keep his belt, the boxing fan wins |$450.|
See also
where |p_i =| probability of occurrence of the event |i|, |x_i =| amount associated with the event |i|, |M =| initial bet amount
To help fund the school's freestyle ski team, the organisers are organising a fundraising event with the following prizes up for grabs.
-
one weekend family ski package ($800 value);
-
two alpine ski season tickets (value of $500 each);
-
four pairs of skis (value of $300 each);
-
eight lift tickets valid for one day (value $45 each).
Given that they have a total of 336 tickets to sell, what should be the selling price of a raffle ticket?
-
Apply the mathematical expectation formula
|\begin{align}\mathbb{E} &= (\color{blue}{p_1 x_1} + \color{red}{p_2 x_2} + \color{green}{p_3 x_3} + \color{black}{p_4 x_4}) - M \\\\ \displaystyle \mathbb{E} &= \left(\color{blue}{\frac{1}{336}\times 800 } + \color{red}{\frac{2}{336} \times 500} + \color{green}{\frac{4}{336} \times 300} + \color{black}{ \frac{8}{336} \times 45}\right) - M\end{align}|
-
Replace the value of |\mathbb{E}| by |0| because the game is fair
|\begin{align}\displaystyle \mathbb{E} &= \left(\color{blue}{\frac{1}{336}\times 800 } + \color{red}{\frac{2}{336} \times 500} + \color{green}{\frac{4}{336} \times 300} + \color{black}{ \frac{8}{336} \times 45}\right) - M \\\\ \displaystyle 0 &= \left(\color{blue}{\frac{1}{336}\times 800 } + \color{red}{\frac{2}{336} \times 500} + \color{green}{\frac{4}{336} \times 300} + \color{black}{ \frac{8}{336} \times 45}\right) - M\end{align}|
-
Isolate |M| to find the value of the initial stake
|\begin{align}\displaystyle 0 &= \left(\color{blue}{\frac{1}{336}\times 800 } + \color{red}{\frac{2}{336} \times 500} + \color{green}{\frac{4}{336} \times 300} + \color{black}{ \frac{8}{336} \times 45}\right) - M\\\\ \displaystyle 0 &= \left(\color{blue}{\frac{800}{336}} + \color{red}{\frac{1000}{336}} + \color{green}{\frac{1200}{336}} + \color{black}{ \frac{360}{336}}\right) - M\\\\ \displaystyle 0 &= \frac{3360}{336} - M\\\\ \displaystyle M &= \frac{3360}{336} \\\\ M &= 10\ $\end{align}|
Answer: For the game to be fair, tickets must be sold at a price of |$10.|
If |\mathbb{E} = 0|, the game is fair.
If |\mathbb{E} < 0|, the game is unfavourable to the player.
If |\mathbb{E} >0|, the game is favourable to the player.
See also
|P(A \mid B) = \dfrac{P (A \cap B)}{P (B)}| with |P(A) >0|
During the previous month, listeners to a Quebec radio station had the chance to win a trip to Walt Disney's fairytale estate. Before randomly selecting the winner, the broadcaster drew up an overall profile of the participants.
English image coming soon!
What is the probability that the winner is the father of a family with three children and that the raffle ticket was given to him as a gift?
-
Identify the boxes referring to the participants who received the ticket as a gift
||P(\color{red}{B}) = \dfrac{\color{red}{15 + 30 + 2}}{23 + 12 + ... + 67 + 27 } = \dfrac{\color{red}{47}}{240}||
-
Among the people identified above, identify those with a family of three children
||P(\color{blue}{A \cap B}) = \dfrac{\color{blue}{30}}{240}||
-
Apply the formula
||P(\color{blue}{A} \mid \color{red}{B}) = \frac {P( \color{blue}{A \cap B})}{P(\color{red}{B})}= \dfrac{\frac{\color{blue}{30}}{240}}{\frac{\color{red}{47}}{240}}= \dfrac{\color{blue}{30}}{\color{red}{47}}||
Answer: The probability that the winner is the father of a family with three children and that he was given the ticket as a gift is |\dfrac{30}{47}.|
See also
Two figures are equivalent when they have the same area.
See also
Two solids are equivalent when they have the same volume.
See also
Solve the following equation. ||6 \ 300 (1{.}2)^{3x} = 175 (7{.}2)^2||
Calculs | Explanations |
---|---|
|\begin{align} |
Factorisation to find equivalent bases |
|\begin{align} |
Power of a product |
|\begin{align} |
Power calculation and multiplication |
|\begin{align} |
Reciprocal operation to isolate exponential notation |
|\begin{align}\phantom{(6 \ 300)}1{.}2^{\color{blue}{3x}} &= 1{.}2^\color{blue}{2} \\ \dfrac{\color{blue}{3x}}{\color{red}{3}} &= \dfrac{\color{blue}{2}}{\color{red}{3}} \\ x &= \dfrac{2}{3} \end{align}| |
Comparison of exponents with identical bases |
Answer : |x=\dfrac{2}{3}.|
See also
Solving an exponential equation
What is the value of |x| in the equation:
|| 4500 = 1500 (1.08)^{\frac{x}{2}}||
||\begin{align}
\frac{4500}{\color{red}{1500}} &= \frac{1500}{\color{red}{1500}} (1.08)^{\frac{x}{2}} && \small\text{inverse operation} \\\\
3 &= 1.08^{\frac{x}{2}} \\\\
log_{1.08} \ 3 &= \frac{x}{2} && \small \text{definition of log} \\\\
\frac{log_{10} \ 3}{log_{10} \ 1.08} &= \frac{x}{2} && \small\text{change of base} \\\\
14.275 \cdot \color{red}{2} &\approx \frac{x}{2} \cdot \color{red}{2} && \small\text{inverse operation} \\\\
28.55 &\approx x \end{align}||
Solving a logarithmic equation
What is the value of |x| in the equation:
||log_5 \ x^3 + log_5 \ \left(\frac{x}{32}\right) = log_5 \ 732 - 1||
||\begin{align}
log_5 \ x^3 + log_5 \ \left(\frac{x}{32}\right) &= log_5 \ 732 - 1 \\\\
3 \ log_5 \ x + log_5 \ \left(\frac{x}{32}\right) &= log_5 \ 732 - 1 && \small\text{power of a log}\\\\
3 \ log_5 \ + (log_5 \ x - log_5 \ 32) &= log_5 \ 732 - 1 && \small\text{log of a quotient} \\\\
3 \ log_5 \ x + log _5 \ x - 2,153 &\approx 4.098 - 1 && \small\text{change of base law} \\\\
4 \ log_ 5 \ x - 2.153 &\approx 4.098 - 1 && \small\text{like terms} \\\\
4 \ log_5 \ x - 2.153 \color{red}{+2.153} &\approx 4,098 - 1 \color{red}{+ 2.153} && \small\text{inverse operation} \\\\
\frac{4 \ log_5 \ x}{\color{red}{4}} &\approx \frac{5.251}{\color{red}{4}} && \small\text{inverse operation} \\\\
log_5 \ x \approx 1.313 &\Rightarrow 5^{1.313} = x && \small\text{definition of log} \\\\
8.275 &\approx x \end{align}||
See also
Finding Current Value
||\begin{align}
C_0&=C_n\left(1+\dfrac{i}{k}\right)^{-x}\\\\
C_0&=\dfrac{C_n}{\left(1+\dfrac{i}{k}\right)^x}\\\\
\end{align}||
where
||\begin{align}
C_0&:\text{present value}\\
C_n&:\text{future value}\\
i&:\text{annual interest rate in decimal notation}\\
k&:\text{factor related to the interest period}\\
x&:\text{number of interest periods}
\end{align}||
To ensure the best possible retirement, Christian needs to obtain a future value of |$200\ 000| on an investment he is making today. So what should be the present value of his investment if he knows that it will be subject to an annual interest rate of |2{.}59\ \%| compounded monthly over a period of |35| years?
-
Identify the differents types of data ||\begin{align} \color{#ec0000}{C_n}&=\color{#ec0000}{200\ 000}\\ \color{#333fb1}{i}&=\color{#333fb1}{2{,}59\ \%}\\ \color{#fa7921}{k}&=\color{#fa7921}{12}\\ \color{#ff55cc}{x}&=\color{#ff55cc}{35\times12}=\color{#ff55cc}{420} \end{align}||
-
Apply the formula ||\begin{align} C_0&=\dfrac{\color{#ec0000}{C_n}}{\left(1+\dfrac{\color{#333fb1}{i}}{\color{#fa7921}{k}}\right)^{\color{#ff55c3}{x}}}\\\\ C_0&=\dfrac{\color{#ec0000}{200\ 000}}{\left(1+\dfrac{\color{#333fb1}{0{.}0259}}{\color{#fa7921}{12}}\right)^{\color{#ff55c3}{420}}}\\\\ C_0&\approx80\ 866{.}06 \end{align}||
-
Give the answer in a sentence
The present value of Christian's investment should be approximately |$80\ 866{.}06.|
See also
This procedure confers victory on the individual or group that obtains the majority of votes, i.e. |50\ \%+1| of the total number of votes representing an absolute majority.
In the last Canadian Federal Election, the aim of the various parties was to elect as many deputies as possible from the country's 338 ridings. Once the results have been compiled, here's how power is distributed.
Political Party |
Number of Elected Deputies |
---|---|
Conservative Party |
|125| |
Green Party |
|4| |
Liberal Party |
|171| |
New Democratic Party |
|16| |
Bloc Québécois Party |
|22| |
-
Determine the percentage of each party using the following proportion ||\dfrac{\text{Number of elected deputies}}{\text{Number of elected deputies}}=\dfrac{\text{% of Party}}{\text{100 %}}||
Political Party
Percentage of Elected Deputies (%) Conservative Party
|37{.}0|
Green Party
|1{.}2|
Liberal Party
|50{.}6|
New Democratic Party
|4{.}7|
Bloc Québécois Party
|6{.}5|
-
Identify the group or individual who received more than 50% of the vote
Political Party
Percentage of Elected Deputies (%) Conservative Party
|37{.}0|
Green Party
|1{.}2|
Liberal Party
|50{.}6|
New Democratic Party
|4{.}7|
Bloc Québécois Party
|6{.}5|
Under majority rule, the Liberal Party of Canada won the election.
See also
This procedure confers victory on the individual or group that obtains the greatest number of votes, i.e. an absolute majority.
To elect the new captain of the Montreal Canadiens hockey team, the general manager asked the opinion of all the players who have a contract with the team. Each player was asked to write down the name of the player they wanted to lead the team. Here are the results compiled by management.
Player |
Number of Votes |
---|---|
Brendan Gallagher |
2 |
P.K. Subban |
1 |
Max Pacioretty |
16 |
David Desharnais |
5 |
Tomas Plekanec |
1 |
Andrei Markov |
11 |
Using the plurality method, who will be named captain of this team?
-
Place results in descending order
Player |
Number of Votes |
---|---|
Max Pacioretty |
16 |
Andrei Markov |
11 |
David Desharnais |
5 |
Brendan Gallagher |
2 |
P.K. Subban |
1 |
Tomas Plekanec |
1 |
The team captain will be Max Pacioretty, who received the most votes.
See also
This procedure confers victory on the individual or group who obtains the most points by awarding| n-1| points for each voter's 1st choice, |n-2| points for the 2nd choice and so on for the next choices |n| of candidates.
To be inducted into the Hockey Hall of Fame, the players nominated are ranked in order of preference by the members of the Hall committee. To simplify the presentation of the results, votes with identical preferences have been grouped together. Here is the list of four players and their preference ranking in 2014.
Choice |
7 Members |
6 Members |
4 Members |
---|---|---|---|
1st choice |
Dominik |
Mike |
Peter |
2nd choice |
Peter |
Peter |
Rob |
3rd choice |
Mike |
Dominik |
Mike |
4th choice |
Rob |
Rob |
Dominik |
Using Borda's method, who would be the next player to be inducted into the Hockey Hall of Fame?
-
Determine the number of points awarded for each choice
We use the following rule. ||\text{Nombre de points}=n-p||
where
|n :| number of possible choices
|p :| position on the preference list1st : |n-p=4-1=3| points
2nd : |n-p=4-2=2| points
3rd : |n-p=4-3=1| point
4th : |n-p=4-4=0| point -
Calculate the number of points obtained by each
Dominik :|\color{#333fb1}{7}\times(4-1)+\color{#ec0000}{6}\times(4-3)+\color{#3a9a38}{4}\times(4-4)=27\text{ points}|
Peter : |\color{#333fb1}{7}\times(4-2)+\color{#ec0000}{6}\times(4-2)+\color{#3a9a38}{4}\times(4-1)=38\text{ points}|
Mike : |\color{#333fb1}{7}\times(4-3)+\color{#ec0000}{6}\times(4-1)+\color{#3a9a38}{4}\times(4-3)=29\text{ points}|
Rob : |\color{#333fb1}{7}\times(4-4)+\color{#ec0000}{6}\times(4-4)+\color{#3a9a38}{4}\times(4-2)=8\text{ points}|
Since Peter scored the most points, he is the only player who will be eligible for the Hockey Hall of Fame in 2014.
See also
This procedure confers victory on the individual or group that wins all its head-to-head duels according to voters' preferences.
If no individual or group wins all their duels, it is preferable to use another procedure.
To be inducted into the Hockey Hall of Fame, the players nominated are ranked in order of preference by the members of the Hall committee. To simplify the presentation of the results, votes with identical preferences have been grouped together. Here is the list of four players and their preference ranking in 2014.
Choice |
7 Members |
6 Members |
4 Members |
---|---|---|---|
1st choice |
Dominik |
Mike |
Peter |
2nd choice |
Peter |
Peter |
Rob |
3rd choice |
Mike |
Dominik |
Mike |
4th choice |
Rob |
Rob |
Dominik |
Using Condorcet's principle, who would be the next player to be inducted into the Hockey Hall of Fame?
-
Compile Dominik's duels with each of the players
Dominik |(\color{#333fb1}{7})| is beaten by Peter |(\color{#ec0000}{6}+\color{#3a9a38}{4}).|
Since he loses his first duel, we can move on to another candidate.
-
Compile Peter's duels with each player
Peter |(\color{#ec0000}{6}+\color{#3a9a38}{4})| wins against Dominik |(\color{#333fb1}{7}).|
Peter |(\color{#333fb1}{7}+\color{#3a9a38}{4})| wins against Mike |(\color{#ec0000}{6}).|
Peter |(\color{#333fb1}{7}+\color{#ec0000}{6}+\color{#3a9a38}{4})| wins against Rob |(0).|
Since Peter won all his duels, he will be inducted into the Hockey Hall of Fame.
See also
This procedure confers victory on the individual or group that obtains the highest number of votes while voters can cast their ballot only once for as many candidates as they wish.
In order to avoid the popular vote, the assent vote is used to elect the next class president. Once the results have been counted, the following table is obtained.
Number of Voters who Voted for these Candidates |
5 |
8 |
10 |
7 |
3 |
---|---|---|---|---|---|
|
Marie-Claude |
Simon |
Vincent |
Judith |
Simon |
|
Gitane |
Vincent |
Gitane |
Marie-Claude |
Judith |
|
|
Gitane |
Simon |
Vincent |
If we compiled the results properly, who would be the winner of this election if we followed the principle of assent-based voting?
-
Compiling Gitane's votes ||\color{#ec0000}{5}+\color{#3a9a38}{8}+\color{#ff55c3}{10}=23\text{ votes}||
-
Compiling Marie-Claude's votes ||\color{#ec0000}{5}+\color{#333fb1}{7}=12\text{ votes}||
-
Compiling Simon's votes ||\color{#3a9a38}{8}+\color{#efc807}{3}+\color{#ff55c3}{10}=21\text{ votes}||
-
Compiling Vincent's votes ||\color{#3a9a38}{8}+\color{#333fb1}{7}+\color{#ff55c3}{10}=25\text{ votes}||
-
Compiling Judith's votes ||\color{#333fb1}{7}+\color{#efc807}{3}=10\text{ votes}||
Since Vincent received the most votes (|25| votes), he will be appointed class president.
See also
This procedure confers victory on the individual or group that obtains the majority of votes, i.e. |50\ \%+1| of the total number of votes, while voters rank them in order of preference. If there is no absolute majority on the first count, we eliminate the least popular to transfer votes to the next candidate.
To be inducted into the Hockey Hall of Fame, the players nominated are ranked in order of preference by the members of the Hall committee. To simplify the presentation of the results, votes with identical preferences have been grouped together. Here is the list of four players and their preference ranking in 2014.
Choice |
7 Members |
6 Members |
4 Members |
---|---|---|---|
1st choice |
Dominik |
Mike |
Peter |
2nd choice |
Peter |
Peter |
Dominik |
3rd choice |
Mike |
Dominik |
Mike |
Using the elimination voting method, who would be the next player to be inducted into the Hockey Hall of Fame?
-
Determine whether one of the candidates has the majority of 1st choices
Dominik ||\dfrac{\color{#333fb1}{7}}{\color{#333fb1}{7}+\color{#ec0000}{6}+\color{#3a9a38}{4}}=\dfrac{\color{#333fb1}{7}}{17}\approx41{.}2\ \%||
Mike ||\dfrac{\color{#ec0000}{6}}{\color{#333fb1}{7}+\color{#ec0000}{6}+\color{#3a9a38}{4}}=\dfrac{\color{#ec0000}{6}}{17}\approx35{.}3\ \%||
Peter ||\dfrac{\color{#3a9a38}{4}}{\color{#333fb1}{7}+\color{#ec0000}{6}+\color{#3a9a38}{4}}=\dfrac{\color{#3a9a38}{4}}{17}\approx23{.}5\ \%||
-
Since no one has a majority of votes, the votes of the least popular are transferred to the next most popular member of the group
Choice
7 Members
6 Members
4 Members
1st choice
Dominik
Mike
Peter2nd choice
PeterPeterDominik
3rd choice
Mike
Dominik
Mike
-
Redo the calculations to determine whether one of the remaining candidates has a majority of votes
Dominik ||\dfrac{\color{#333fb1}{7}+\color{#3a9a38}{4}}{\color{#333fb1}{7}+\color{#ec0000}{6}+\color{#3a9a38}{4}}=\dfrac{11}{17}\approx64{.}7\ \%||
Mike ||\dfrac{\color{#ec0000}{6}}{\color{#333fb1}{7}+\color{#ec0000}{6}+\color{#3a9a38}{4}}=\dfrac{\color{#ec0000}{6}}{17}\approx35{.}3\ \%||
Since Dominik has now obtained more than |50\ \%| of votes, he will be inducted into the Hockey Hall of Fame.
See also
To fully understand the concepts in this section, it is important to master the following vocabulary.
-
Vertices : the different elements which are linked (people, steps to be taken, etc.) and which are generally represented by dots.
-
Edges : the links that connect the elements, generally represented by lines or arcs.
-
Parallel edges : when two edges have the same start and end vertices.
-
Loop : edge which begins and ends with the same vertex.
-
Degree : the number of times a vertex is touched by the different edges.
-
Chain : a sequence of edges that we loan to ‘walk’ around the graph.
-
Length : corresponds to the number of edges loaned in a chain.
-
Distance : minimum number of stops to go from the starting vertex to the destination vertex.
-
Simple chain : a chain in which each edge is loaned only once.
-
Cycle : a chain that starts and ends at the same vertex.
-
Simple cycle : a cycle in which each edge is used only once.
|\color{#ec0000}{B}| is a vertex.
|\color{#333fb1}{A — E}| is an edge.
|\color{#3a9a38}{F — F}| is a loop.
|E — D| and |D — E| are parallel edges.
The degree of |\color{#ec0000}{B}| is |3.|
|\color{#ec0000}{B-F-E-C-F-B}| is a cycle.
|\color{#3a9a38}{D-B-C-B-A}| is a chain.
|\color{#3a9a38}{A-B-C-F}| is a simple string of length |3,| but the distance |\color{#333fb1}{d(A,F)=2}.|
Finally, |\color{#3a9a38}{A-B-C-F}\color{#333fb1}{-E-A}| is a simple cycle of length |5.|
See also
The Eulerian characteristic of a graph requires that all edges are involved only once in the chain or cycle.
As a police officer, you want to know every nook and cranny of the area you serve. To do this, you decide to patrol every street in your district during your shift. To help you, you use a road map to identify the area you have to supervise.
Bearing in mind that you can decide where your route starts and finishes, what sequence of routes should you take to patrol each street as efficiently as possible?
-
Choose a starting point that seems appropriate.
-
Make sure that all the edges are loaned only once. However, it is possible to pass through the same vertex several times.
One possible route could be the following Eulerian chain. ||\color{#ec0000}{A}-B-F-\color{#ec0000}{A}-E-C-B-D-E||
See also
The Hamiltonian characteristic of a graph requires that all the vertices are involved only once in the chain or cycle.
To complete a car rally, competitors must pass through each of the milestones identified by letters on the following map.
Bearing in mind that they must return to the starting point identified by the vertex |A| to finish the race, what could be one of the routes taken by the competitors?
We need to ensure that the start and end vertex are the same, while passing through each vertex only once.
So one possible route could be the following Hamiltonian cycle. ||A-E-D-C-F-B-A||
See also
Depending on the information provided on the graph, it can be given a specific name.
-
Related : when all the vertices are accessible from any vertex.
-
Tree : it's a graph that has no simple cycles.
-
Oriented : when the edges suggest an accurate orientation by means of an arrow.
-
Weighted (Valued) : when each of the edges has a quantity associated with it.
-
Coloured : when each of the edges has a quantity associated with it.
See also
In practical terms, the critical path is often used to establish a deadline for completing a project.
Before you buy a home, it's important to analyse a number of factors that will help you make a wise purchase. To make sure you don't forget anything in the process, here are a few tips.
Tasks |
Time (Days) |
Prerequisites |
---|---|---|
A : Establishing your needs |
1 |
None |
B : Drawing up a budget |
5 |
A |
C : Shopping for a mortgage |
7 |
B |
D : Hiring a notary |
3 |
B |
E : Hiring a real estate agent |
3 |
B |
F : Visiting homes |
182 |
C - D - E |
G : Negotiating an interest rate |
7 |
F |
H : Obtain a pre-authorised loan |
30 |
F |
I : Making an offer |
7 |
G - H |
J : Have the home inspected |
14 |
I |
K : Signing the deed of sale |
2 |
J |
L : Taking out home insurance |
10 |
J |
M : Moving |
1 |
K - L |
What is the total duration of such a project?
-
Construct a weighted (valuated) graph of the situation
-
Identify the path with the highest weight
-
Calculate the weight for this path
||\begin{align}
\text{Weight}&=1+5+7+182+30+7+14+10+1\\
\text{Weight}&=257
\end{align}||
Answer : It will take a total of |257| days to complete this project.
See also
In practical terms, the chromatic number is often used to colour a world map, design electronic chips or plan a telecommunications network.
Keen to get to know her colleagues as well as possible, Ms Dreau wants to take part in as many of the activities offered by her school as possible. However, certain constraints in her timetable prevent her from taking part in everything she would like to.
-
journalism clashes with a few improvisation and success support sessions;
-
it's impossible for her to enrol in basketball, theatre and dance at the same time;
-
success support and theatre are both on the Monday evening timetable.
What is the maximum number of activities she can take part in?
-
Draw a graph whose edges link incompatible elements.
-
Assign different colours to adjacent vertices using a minimum number of colours.
Answer: Taking all these constraints into account, Ms Dreau will be able to take part in 3 activities: dance, success support and improvisation.
See also
In practical terms, the value tree is often used to minimise or maximise costs or distances.
Before building homes in a new neighbourhood, a city must install a water and sewer system that connects each residence. Despite a few geographical constraints, most homes can be connected by this future system.
Taking the quantities in the graph as the distance, in metres, between each of the houses, what would be the minimum length of the network in this neighbourhood?
-
Put the edges in ascending order according to their respective values
|DF=199,| |DE=213,| |CE=256,| |AB=298,| |BD=332,| |BC=375,| |EF=395,| |AF=405,| |AC=657| -
Trace the graph again, placing the edges one by one, following the order established above, until all the vertices in the graph are connected.
Answer: The minimum length for this network will be |298+332+199+213+256=1\ 298| metres.