Semigraph

Материал из WEGA

Semigraph --- полуграф.

A semigraph [math]\displaystyle{ G }[/math] is a pair [math]\displaystyle{ (V,X) }[/math], where [math]\displaystyle{ V }[/math] is a nonempty set whose elements are called vertices of [math]\displaystyle{ G }[/math] and [math]\displaystyle{ X }[/math] is a set of [math]\displaystyle{ n }[/math]-tuples, called edges of [math]\displaystyle{ G }[/math], of distinct vertices for various [math]\displaystyle{ n \geq 2 }[/math], satisfying the following conditions.

S.G.-1. Any two edges have at most one vertex in common.

S.G.-2. Two edges [math]\displaystyle{ (u_{1}, u_{2}, \ldots, u_{n}) }[/math] and [math]\displaystyle{ (v_{1}, v_{2}, \ldots, v_{m}) }[/math] are considered to be equal if and only if

(i) [math]\displaystyle{ m = n }[/math] and (ii) either [math]\displaystyle{ u_{i} = v_{i} }[/math] for [math]\displaystyle{ 1\leq i \leq n }[/math] or [math]\displaystyle{ u_{i} = v_{n-i+1} }[/math] for [math]\displaystyle{ 1\leq i \leq n }[/math].

The adjacent graph or a graph [math]\displaystyle{ G_{a} }[/math] of [math]\displaystyle{ G }[/math] is the graph with the same vertex set as that of [math]\displaystyle{ G }[/math], and two vertices are adjacent in [math]\displaystyle{ G_{a} }[/math] if and only if they are adjacent in [math]\displaystyle{ G }[/math].

The consecutive adjacent graph [math]\displaystyle{ G_{ca} }[/math] of [math]\displaystyle{ G }[/math] is the graph with the same vertex set as that of [math]\displaystyle{ G }[/math], and two vertices are adjacent in [math]\displaystyle{ G_{ca} }[/math] if and only if they are consecutive adjacent vertices in [math]\displaystyle{ G }[/math].