Contracting edge, contraction of an edge

Contracting edge, contraction of an edge — стягивание ребра.

If [math]\displaystyle{ \,G }[/math] is a graph and [math]\displaystyle{ \,(u,v) }[/math] is an edge of [math]\displaystyle{ \,G }[/math], the graph obtained by contracting edge [math]\displaystyle{ \,(u,v) }[/math] is the graph obtained from [math]\displaystyle{ \,G[V \setminus \{u,v\}] }[/math] by adding a new vertex [math]\displaystyle{ \,z }[/math] and adding edges [math]\displaystyle{ \,(z,w) }[/math] for all [math]\displaystyle{ \,w \in (N(u) \cup N(v)) \setminus \{u,v\} }[/math], where [math]\displaystyle{ \,N(u) }[/math] is the neighborhood of [math]\displaystyle{ \,u }[/math]. Contracting a subgraph means contracting all edges of it (the order in which the contraction is made is irrelevant). Note that multiple edges may appear.

Литература

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