What is the significance of a graph exhibiting the delta property?

Question

In class about AI we are studying graph searches. Here, we defined the "delta" property to mean that c(n,m)≥δ>0 for each (n,m) edge in the graph where c(n,m) is the weight of the edge connecting vertices n and m. We defined a δ-graph as a weighted, directed graph exhibiting the δ property and having a finite number of outgoing edges. In a lot of theorems we explicitly state that "the theorem is true for δ-graphs", but I don't quite see why this kind of graph is so important for such tasks. Can you explain what the significance of these properties is?

Answer 1

It is important because it makes it impossible to have arbitrarily long paths of small weights.

In other words, for every weight $w$ there is a length $l$ such that every path of weight less than $w$ has length at most $l$.

The other important property is that every vertex has a finite number of neighbours.

these two properties guarantee the following:

• For every two vertices $u$ and $v$ there exists a path of minimum length from $u$ to $v$ (or no paths exist)

• the path of minimum length can be computed using brute force