Line graph of a mixed graph

Line graph of a mixed graph --- рёберный граф смешанного графа.

Let [math]\displaystyle{ G = (V(G),E(G)) }[/math] be a mixed graph without loops. The line graph of [math]\displaystyle{ G }[/math] is defined to be [math]\displaystyle{ G^{l} = (V(G^{l}), E(G^{l})) }[/math], where [math]\displaystyle{ V(G^{l}) = E(G) }[/math]. For [math]\displaystyle{ e_{i},e_{j} \in V(G^{l}) }[/math], [math]\displaystyle{ e_{i}e_{j} }[/math] is an unoriented edge in [math]\displaystyle{ G^{l} }[/math] if [math]\displaystyle{ e_{i}, e_{j} }[/math] are unoriented edges in [math]\displaystyle{ G }[/math] and have a common vertex, or one of [math]\displaystyle{ e_{i}, e_{j} }[/math] is an oriented edge in [math]\displaystyle{ G }[/math] and their common vertex is the positive end of the oriented edge, or both [math]\displaystyle{ e_{i} }[/math] and [math]\displaystyle{ e_{j} }[/math] are oriented edges in [math]\displaystyle{ G }[/math] and their common vertex is their common positive (or negative) end; [math]\displaystyle{ e_{i} \rightarrow e_{j} }[/math] is an oriented edge in [math]\displaystyle{ G^{l} }[/math], where [math]\displaystyle{ e^{i} }[/math] and [math]\displaystyle{ e_{j} }[/math] are the positive and negative ends of [math]\displaystyle{ e_{i} \rightarrow e_{j} }[/math], respectively, if [math]\displaystyle{ e_{i} }[/math] is an unoriented edge, [math]\displaystyle{ e_{j} }[/math] is an oriented edge in [math]\displaystyle{ G }[/math] and their common vertex is the negative end of [math]\displaystyle{ e_{j} }[/math], or both [math]\displaystyle{ e_{i} }[/math] and [math]\displaystyle{ e_{j} }[/math] are oriented edges in [math]\displaystyle{ G }[/math] and their common vertex is the positive and negative ends of [math]\displaystyle{ e_{i} }[/math] and [math]\displaystyle{ e_{j} }[/math], respectively.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.