Information Technology Reference
In-Depth Information
that each vertex is contained in some segment and once assigned to a segment
such vertex is not assigned to any other segment. Precise definition can be found
in Definition 1. The main difference between subgraph and segment of a graph
is that segment can contain edges which's both vertices are not in the same
segment.
Definition 1.
Graph segment and a graph segmentation:
•
LEF T V
(
e
)=
v
1
⇔
e
=(
v
1
,v
2
)
•
RIGHT V
(
e
)=
v
2
⇔
e
=(
v
1
,v
2
)
Segment
S in a graph G : S
=(
V
S
,E
S
):
V
S
⊆
V
∧
E
S
=
{
e
∈
E
|
RIGHT V
(
e
)
∈
V
S
∨
LEF T V
(
e
)
∈
V
S
}
S, S
∈
=
S
Segmentation
S
(
G
)=
{
S
|
SisasegmentofG
}∧∀
S
(
G
)
,S
:
V
S
∩
V
S
=
∅∧
V
S
=
V
S
∈
S
(
G
)
Afterward, the vertices and edges between vertices within one segment form a
subgraph of the indexed graph. The edges lying between vertices assigned to
different segments form edges in the simplified graph. Segments then form the
vertices in the simplified graph what we call a segment graph which is defined in
Definition 2. By this transformation, multiple edges can appear between vertices
in the new graph. Regardless, each multiple edge can be substituted by a single
edge since from a path point of view it means a redundant information.
Definition 2.
Segment graph of G:
SG
(
G
)=(
S
(
G
)
,X
)
,X
=
{
h
|
h
=(
S
i
,S
j
)
⇔
1
≤
i, j
≤
k
∧
EDGES -
OUT
(
S
i
)
∅}
where k is the number of segments in S
(
G
)
.
∩
EDGES IN
(
S
j
)
=
The segment graph
SG
(
G
) has very similar properties as the graph
G
.Anypath
followed in the indexed graph can be observed also in the segment graph. Since
we left out only the inner edges of each segment. This simplified path in the
segment graph we call a sequence of segments just to avoid confusion of terms,
see Definition 3. Intuitively, each path in the indexed path can be represented by
only one sequence of segments. The method to transform a path into a sequence
of segments is to replace each group of vertices and inner edges of each segment
by that particular segment and to replace each edge lying between two vertices
assigned to different segments by a particular edge from
X
, with regard to the
Definition 2 such edge always exists.
Definition 3.
Sequence of segments:
EDGES OUT(S) =
{
e
|
e
∈
E
S
∧
LEF T V
(
e
)
∈
V
S
∧
RIGHT V
(
e
)
∈
V
S
}
EDGES IN(S) =
{
e
|
e
∈
E
S
∧
RIGHT V
(
e
)
∈
V
S
∧
LEF T V
(
e
)
∈
V
S
}
Sequence of segments
(
S
1
...S
l
):
S
1
,...S
l
∈
S
(
G
)
,
1
≤
i
≤
l
−
1:
EDGES -
OUT
(
S
i
)
∩
EDGES IN
(
S
i
+1
)
=
∅
