A question about a labeled directed graph

631 Views Asked by At

Given a labeled directed graph 〈N,E,l〉 with N a set of vertices, E ⊆ N×N a set L to edges. Let source and target be functions on E such that source(s,t)=s and target(s,t)=t . Formally formulate the following properties: I. There are no nodes that are target of more than two edges with identical labels. II. There is at least one path of length three where all the edges have identical labels.

1

There are 1 best solutions below

0
On BEST ANSWER

It seems like many different formulations could work. For the first property, maybe: $$\forall n \in N, \forall e_1, e_2, e_3 \in \mathsf{target}^{-1}(n) : e_1 \neq e_2 \neq e_3 \neq e_1, \;[\mathsf{label}(e_1)\neq \mathsf{label}(e_2)] \vee [\mathsf{label}(e_1) \neq \mathsf{label}(e_3)] $$

("For every node, and every three distinct edges into that node, either the first two edges have different labels, or the first and last edges have different labels.")

For the second property, maybe:

$$\exists e_1, e_2, e_3 \in E : [\mathsf{target}(e_1)=\mathsf{source}(e_2)] \wedge [\mathsf{target}(e_2)=\mathsf{source}(e_3)] \wedge [\mathsf{label}(e_1)=\mathsf{label}(e_2)=\mathsf{label}(e_3)] $$

("There exist three edges that line up properly—the target of the first is the source of the second, and the target of the second is the source of the third— such that all three have the same label.")