SCHOOL  ASSESSED  COURSEWORK  

PRACTICE  SAC  
2017  
Total  Writing  Time  95  minutes  with  5  minutes  Reading  time  

GENERAL  MATHEMATICS  UNIT  1  

Student  Name:  _____________________________________________________  

Equipment  Permitted:  1  bound  reference  (notes  or  text  book  NOT  BOTH),  TI-­‐nspire  CAS  Calculator,  scientific  
calculator,  Ruler,  Pencil  and  Pens.  
SAC  Rules  

FULL  SCHOOL  UNIFORM  MUST  BE  WORN  TO  ALL  SACS  

o   Students  must  bring  correct  equipment  to  each  SAC,  for  example:  pens,  pencils,  rulers,  calculators  and  other  materials  as  
informed  by  staff  
o   No  food  or  drink  is  to  be  consumed  in  the  SAC  room  (bottled  water  excepted)  
o   Students  are  not  to  communicate  with  each  other  in  any  way  during  a  SAC  
o   No  mobile  phones,  iPods,  mp3  players  etc  are  allowed  in  the  SAC  room  
o   Students  must  remain  for  the  duration  of  the  SAC.  
o   Students  are  to  behave  appropriately  at  all  times  –  disruptive  behaviour  will  be  considered  a  serious  breach  of  SAC  rules.  
 
Graphs  and  networks  
This  topic  includes:  
•   Introduction  to  the  notations,  conventions  and  representations  of  types  and  properties  of  graphs,  including  edge,  
loop,  vertex,  the  degree  of  a  vertex,  isomorphic  and  connected  graphs  and  the  adjacency  matrix  
•   Description  of  graphs  in  terms  of  faces  (regions),  vertices  and  edges  and  the  application  of  Euler’s  formula  for  
planar  graphs  
•   Connected  graphs:  walks,  trails,  paths,  cycles  and  circuits  with  practical  applications  
•   weighted  graphs  and  networks,  and  an  introduction  to  the  shortest  path  problem  (solution  by  inspection  only)  
and  its  practical  application  
•   Trees  and  minimum  spanning  trees,  Prim’s  algorithm,  and  their  use  to  solve  practical  problems.  
 
Key  knowledge  
•   the   language,   properties   and   types   of   graphs,   including   edge,   face,   loop,   vertex,   the   degree   of   a   vertex,  
isomorphic  and  connected  graphs,  and  the  adjacency  matrix,  Euler’s  formula  for  planar  graphs,  and  walks,  trails,  
paths,  circuits,  bridges  and  cycles  in  the  context  of  traversing  a  graph  
•   weighted  graphs  and  networks,  and  the  shortest  path  problem  
•   trees,  minimum  spanning  trees  and  Prim’s  algorithm.  
 
Key  skills  
•   describe   a   planar   graph   in   terms   of   the   number   of   faces   (regions),   vertices   and   edges   and   apply   Euler’s   formula  
to  solve  associated  problems  
•   apply  the  concepts  of  connected  graphs:  trails,  paths,  circuits,  bridges  and  cycles  to  model  and  solve  practical  
problems  related  to  traversing  a  graph  
•   find  the  shortest  path  in  a  weighted  graph  (solution  by  inspection  only)  
•   apply  the  concepts  of  trees  and  minimum  spanning  trees  to  solve  practical  problems  using  Prim’s  algorithm  when  
appropriate.  
 
   General  Maths  2017  
Networks  Quiz  
Name:____________________  
E              
1     The  minimum  number  of  edges  in  a  
 
connected  graph  with  nine  vertices  is:  
3     A  connected  graph  with  8  vertices  has  11  
A   5  
faces.  The  number  of  edges  in  the  graph  is:  
B   6  
C   7   A   15  
D   8   B   16  
E   9   C   17  
  D   18  
E   19  
2     Which  graph  is  a  spanning  tree  for  the  
 
following  graph?  
4     Which  of  the  following  graphs  will  not  have  
an  Euler  trail?  

A                

A            

B              

B            

C                

C            

D              

D            
 7     The  adjacency  matrix  that  represents  the  
following  graph  is:  

E            

5     The  length  of  the  minimum  spanning  tree  for  

this  graph  is:  

é 0 2 1 1 ù
  ê 2 0 2 0 úú
A   31   A   ê  
ê1 2 0 1 ú
ê ú
B   28   ë1 0 1 0 û
C   27    

D   26   é 0 2 2 2 ù
ê 2 0 2 0 úú
E   30  
B   ê  
ê 2 2 0 1 ú
  ê ú
ë 2 0 1 0 û
 
 
 
é0 1 1 0 ù
6     An  Euler  circuit  can  be  created  in  the   ê1 0 1 0 úú
following  graph  by  adding  an  edge  between   C   ê  
the  vertices:   ê1 1 0 1 ú
ê ú
ë1 0 1 0 û

é 0 2 1 1 ù
ê 2 1 2 0 úú
D   ê  
ê1 2 1 1 ú
ê ú
ë1 0 1 1 û

   

A   B  and  C   é1 2 1 1 ù
ê 2 0 2 0 úú
B   A  and  E   E   ê  
ê1 2 1 1 ú
C   A  and  D     ê ú
ë1 0 1 0 û
D   A  and  B    
 
E   A  and  C    

 
 8     The  number  of  faces  in  the  following  planar   11     The capacity of the cut shown in the  
graph  is:   digraph is:

A 4
B 11
 
C 14
A   10   D 21
B   9   E 29
 

C   6   12     The maximum flow from the source to the sink

D   8   in the network on the right is

E   7   A.   4
B.   10
 
C.   14
9     A  Hamiltonian  cycle  for  the  following  graph  
D.   21
is:  
E.   29  

   
A   ABDGFCEDEBCFA  
13     The capacity of the cut shown in the diagram  
B   ABDGFCECFA   on the right is 30. The value of b is
C   ABDGFA  
D   ABCEDGFA  

E   ABDGFCEA  

10     A  complete  graph  with  9  vertices  will  have  a  

total  number  of  edges  of:  

A   9  
A 0
B   8  
B 7
C   72   C 10
D   36   D 14
E   21   E   16  

 
   Short  Answer  
1     The  table  represents  the  distance  by  direct  roads  joining  several  towns  (distances  are  given  in  
kilometres).    

  Ap   Bi   Ca   Du   Ea   Fr      
Ap     20   23     17   21   Ap  =  Appin  
Bi   20     16         Bi  =  Bingo  
Ca   23   16     17   18     Ca  =  Carina  
Du       17     18     Du  =  Dutson  
Ea   17     18   18     19   Ea  =  Eastville  
Fr   21         19     Fr  =  Frog  Creek  
 
 (a)  Draw  a  weighted  graph  to  show  this  information.  
 
 
 
 
 
 
 
 
 
(b)   Find  the  shortest  circuit  that  travels  through  each  town  only  once.  
 
 
(c)   Draw  the  minimum  spanning  tree  for  the  graph  and  state  its  total  distance.  
 
 
 
 
 
 
 
(d)   If  the  roads  that  join  Carina  directly  to  Dutson  and  Eastville  are  blocked,  what  is  the  shortest  way  to  
travel  from  Carina  to  Dutson?  
 
 
 

   
 2    The   diagram   shows   a   system   of   interconnecting  
underground   tunnels   running   below   a   section   of   city  
streets.   The   weightings   indicate   distances   in   metres,  
and   the   vertices   indicate   the   location   of   access   points.  
The  tunnels  are  used  for  utilities  such  as  electricity,  gas,  
water  and  drainage.  

(a)   If  the  gas  company  wishes  to  run  a  pipeline  that  

minimises  its  total  length  but  reaches  each  vertex,  
what  will  be  the  total  length  required?  

(b)   Draw  a  graph  to  show  the  gas  lines.  

(c)   If  drainage  pipes  need  to  run  from  H  to  B,  what  is  the  shortest  path  to  follow?  How  long  will  it  be?  

(d)   A  single  line  of  cable  for  a  computerised  monitoring  system  needs  to  be  placed  so  that  it  commences  at  
H  and  reaches  every  vertex  once.  What  is  the  minimum  length  possible,  and  what  path  must  it  follow?  

   
 3     The  average  travel  times  in  minutes  are  shown  on  the  graph  for  the  system  of  travel  routes  possible  
between  home,  school  and  work  for  the  members  of  a  particular  family.  

 
(a)   What  is  the  shortest  average  time  from  home  to  work  without  going  to  the  school?  

(b)   What  is  the  shortest  average  time  from  home  to  work  if  you  have  to  go  to  the  school  first?  

(c)   What  is  the  shortest  average  time  of  traveling  from  home  to  work  and  returning  if  you  have  to  go  to  
the  school  each  way  and  you  don’t  travel  any  route  more  than  once?  

   
4     The  National  Broadband  Corporation  needs  to  install  network  cables  between  the  points  shown  on  the  
graph.  The  distances  between  the  points  are  indicated  in  metres.  

 
(a)   Draw  the  minimum  spanning  tree  for  the  graph.  

(b)   What  is  the  shortest  length  of  cable  required  for  a  circuit  joining  all  points?  

(c)   What  is  the  shortest  length  of  cable  required  for  a  spanning  tree  if  direct  connections  must  be  
included  from  B  to  F  and  from  E    
to  F?  

 
 5     Determine  the  maximum  flow  through  the  network  below  using  the  minimum  cut  method.