We now focus on the use of Datalog for defining properties and queries m graphs.

(a) Suppose that P is some property of graphs definable in Datalog. Show drat P is preserved under extensions and homomorphisms. That is, if G is a graph satisfying P, then every supergraph of G (i.e., graph extending G) satisfies P, and if h is a graph homomorphism, then h (G) satisfies P.

Which of the following properties and queries on graphs are definable in Datalog?

b) The number of vertices is even.

(c) There is a simple path (i.e., a path without repeated vertices) of even length between two specified vertices.

(d) The binary relation T containing all pairs of vertices (a, D) for which there is a path of even length from o to b. Provide either a Datalog program defining the property or query or an argument why the property or query is not definable in Datalog.

 

Posted Date: 3/1/2013 12:41:37 AM | Location : United States

Ask an Expert

Related Discussions:- Determine the properties and query are definable in datalog, Assignment Help, Ask Question on Determine the properties and query are definable in datalog, Get Answer, Expert's Help, Determine the properties and query are definable in datalog Discussions

Write discussion on Determine the properties and query are definable in datalog
Your posts are moderated

Write your message here..

Related Questions

Velocity and acceleration - three dimensional space, Velocity and Accelerat... Velocity and Acceleration - Three Dimensional Space In this part we need to take a look at the velocity and acceleration of a moving object.    From Calculus I we are famili

Change of base of logarithms, Change of base: The final topic that we have... Change of base: The final topic that we have to look at in this section is the change of base formula for logarithms. The change of base formula is,

Precalculus, describe the end behavior of the following function using Limi... describe the end behavior of the following function using Limit notation f(x)= 2x-1/x-1

Relate perimeter and area, Need help figuring perimeter and area. Need help figuring perimeter and area.

Ratios, the ratio of boys to girls in the sixth grade is 2:3 if there are ... the ratio of boys to girls in the sixth grade is 2:3 if there are 24 boys, how many are girls?

Find x if circle passes through -3, The centre of a circle is (2x - 1, 3x +... The centre of a circle is (2x - 1, 3x + 1).Find x if the circle passes through (-3,-1) and the length of the diameter is 20 units.

Determine the domain and range of function, Determine the domain of each of... Determine the domain of each of the following functions.                         f( x ) = x - 4 / x 2 - 2 x -15 Solution With this problem we have to avoid division by

identity function, detail on identity functio detail on identity function

Noot help me, 4+8/56.75 4+8/56.75

Bernoulli differential equations, In this case we are going to consider dif... In this case we are going to consider differential equations in the form, y ′ +  p   ( x ) y =  q   ( x ) y n Here p(x) and q(x) are continuous functions in the