Knowledge Representation and Reasoning
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP4418: Knowledge Representation and Reasoning Assignment 1, 23T3
Requirements
• Due date: October 6, 2023 at 11:55PM. This is an individual assignment. This assign-
ment is weighted 15% of the course grade.
• Each student submits three files: assignment1.pdf, spiders.lp, and spidershortlegs.lp.
The file assignment1.pdf should contain the answers to questions 1.1, 1.2, 1.3, 2.1, 2.2,
and 3.1, including any snippets of code necessary.
Spanning Spiders
Let G = (V,E) be a graph. A spanning tree T is a subgraph of G with the following
properties:
• T is a tree (i.e. it contains no cycles and is connected).
• T contains all of the vertices of G.
A spider S is a tree with at most one vertex in S whose degree is 3 or more. Such a vertex
is called the centre of the spider. If S consists of no vertices with degree 3 or more, then any
vertex can act as the centre of the spider. Finally, a leg of a spider is a path from the centre
to a vertex of degree 1.
To get a better understanding of the terminology, consider the following example graph.
a
b
c
d
e
x
y
z
Figure 1: An example graph.
A possible spider is highlighted. In fact, the highlighted spider is a spanning spider because
it is a spider and a spanning tree.
a
b
c
d
e
x
y
z
Figure 2: A spider that is also a spanning tree.
1 of 3
COMP4418: Knowledge Representation and Reasoning Assignment 1, 23T3
Given an input graph, our goal is to write an Answer Set Program to return a list of distinct
spanning spiders (i.e. each stable model of our program corresponds to a distinct spanning
spider). Not every graph has a spanning spider; if an input graph does not admit any
spanning spiders, the corresponding program should return unsatisfiable.
Input format. An input file contains predicate instances of vertex/1, indicating the
vertices of the graph and predicate instances of edge/2, indicating the edges of the graph.
The example graph above is modelled with the following predicates.
vertex(a).
vertex(b).
vertex(c).
vertex(d).
vertex(e).
vertex(x).
vertex(y).
vertex(z).
edge(a, d).
edge(a, x).
edge(b, d).
edge(b, y).
edge(c, d).
edge(c, z).
edge(d, e).
edge(e, x).
edge(x, z).
edge(y, z).
Output format. Your program should compute a model containing a predicate leg/2,
indicating which edges are included in the spanning spider. Each model should also contain
a predicate centre/1, indicating which vertex is the centre of the spider.
2 of 3
COMP4418: Knowledge Representation and Reasoning Assignment 1, 23T3
Part I: Understanding the Problem
[1.1] Consider the spanning spider from Figure 2. Indicate the centre vertex and the list of
edges that is included in the spanning spider.
[1.2] Provide ASP rules to define the centre/1 predicate and ensure that in any model,
exactly one vertex is selected as the centre.
[1.3] Provide a generator for the leg/2 predicate.