COM00026H
math代做 | 作业assignment – 这个题目属于一个math的代写任务, 包括了math等方面, 该题目是值得借鉴的assignment代写的题目
Module Code
COM00026H
BEng, BSc, MEng and M math Degree Examinations 2019-
Size Limits: Some questions have size limits for answers which include text and any drawings.
Allocation of Marks:
Q1:14 marks;Q2:12 marks;Q3:14 marks Q4:10 marks;Q5:12 marks;Q6:38 marks
Instructions:
- Answer all questions.
- Submit your answers to the Departments Teaching Portal as a single PDF file.
- If a question is unclear, answer the question as best you can,and note the assump- tions you have made to allow you to proceed.
- Do not use colour: use black-on-white only.
- Start each top-level question on a new page.
- communicate with departmental staff on the topic of the assessment
- communicate with other students on the topic of this assessment
- seek assistance with the assignment from the academic and/or disability support services, such as the Writing and Language Skills Centre, Maths Skills Centre and/or Disability Services. (The only exception to this will be forthose students who have been recommended an exam support worker in a Student SupportPlan. If this applies to you, you are advised to contact Disability Services as soon as possible to discuss the necessary arrangements.)
- seek advice or contribution from any third party, includingproofreaders, online fora, friends, or family members.
We expect, and trust, that all our students will seek to maintain the integrity of the assessment, and of their award, through ensuring that theseinstructions are strictly fol- lowed. Failure to adhere to these requirements will be considered a breach of the Academic Misconduct regulations, where the offences of plagiarism, breach/cheating, collusion and commissioning are relevant: see AM1.2.1. (Note this supersedes Section 7.3 of the Guide to Assessment).
(1) [14 marks]
Consider the following unlabelled graphsLandG:
L
VL={ 1 , 2 , 3 }
EL={a, b, c}
a b c
sL 1 2 3
tL 2 3 1
G
VG={ 4 , 5 , 6 }
EG={d, e, f, g, h, k, n, p, q}
d e f g h k n p q
sG 4 4 4 5 5 5 6 6 6
tG 4 5 5 5 6 6 6 4 4
(i) [4 marks] DrawLandG.
(ii) [5 marks] How many injective graph morphismsLGare there?
(iii) [5 marks] How many isomorphismsGGare there?
(2) [12 marks]
Consider the following ruler=LKRand graphG:
L K R
1 2
1 2
1 2
3 4 5
6
7
8
9 10 11
G
(i) [4 marks]
List the injective graph morphismsLGthat satisfy the dangling condition.
(Denote a morphism by 1 7m, 2 7nwithm, n{ 3 ,... , 11 }.)
(ii) [8 marks]
Draw the graph that results from applyingrtoGas long as possible.
(3) [14 marks] [size limit: 2 pages]
Given a nodevin a graphG,indegG(v)is the number of edges with targetvand
outdegG(v)is the number of edges with sourcev. A graphGisdegree-balancedif
for each nodevinG,indegG(v) = outdegG(v).
The graph grammarDEGBAL =L,N,R,Startis given byLV=LE={},
NV=NE=,Start =and the following rules inR:
r 1 :
r 2 : 1 1 1
r 3 : 1 2 1 2 1 2
r 4 : 1 2 3 1 2 3 1 2 3
Show that every unlabelled degree-balanced graph is contained inL(DEGBAL), by
induction on the size of graphs.
(4) [10 marks] [size limit: 1 page]
A graphGis afull binary tree(fbt for short) if
- Gis acyclic,
- there is exactly one node (the root) without incoming edges and all other nodes have exactly one incoming edge, and
- each node has either two outgoing edges or no outgoing edges.
Construct a graph grammarFBT =L,N,R,Startsuch thatL(FBT)consists
of all unlabelled full binary trees. Do not use nonterminals, that is, make sure that
LV=LE={}andNV=NE=.
Hint: Exploit the dangling condition by using rules that temporarily delete nodes.
(5) [12 marks]
Consider the following graph morphismsABandAC:
1 2
3
A
1 2
3 4
B
1 2
3 5
C
?
Di
(i) [2 marks]
Which of the following graphsDi, together with suitable morphismsBDi
andCDi, is a pushout ofABandAC?
1=2=3=4=
1 2
3 4=
1 2
3
5
4
D 1 D 2 D 3
(ii) [10 marks] [size limit: 1 page]
For each of the two graphsDithat are not pushouts, explain why the pushout
definition is violated.
(6) [38 marks]
LetLbe the label alphabet for unlabelled graphs (LV=LE={}). Consider the
following rule setR={r 1 ,r 2 }:
r 1 : 1 2 1 2 1 2
r 2 : 1 2 3 1 2 3 1 2 3
(i) [32 marks]
List all critical pairs constructed fromr 2 only, that is, all critical pairs of the
formT 1 r 2 S r 2 T 2. You should find eight of them. For each pair, say
whether the pair is (a)strongly joinable, (b)joinable but not strongly joinable,
or (c)not joinable. Show the joining derivations unless they are of length zero.
(ii) [6 marks] [size limit: 1 page]
Show thatL,Risnotlocally confluent, by giving a counterexample.
End of examination paper