Contracting edge, contraction of an edge: различия между версиями

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

If <math>\,G</math> is a [[graph, undirected graph, nonoriented graph|graph]] and <math>\,(u,v)</math> is an [[edge]] of <math>\,G</math>, the graph obtained by '''contracting edge''' <math>\,(u,v)</math> is the graph obtained from <math>\,G[V \setminus \{u,v\}]</math> by adding a new [[vertex]] <math>\,z</math> and adding edges <math>\,(z,w)</math> for all <math>\,w \in (N(u) \cup N(v)) \setminus \{u,v\}</math>, where <math>\,N(u)</math> is the ''[[neighbourhood of a vertex|neighborhood]]'' of <math>\,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.