Contracting edge, contraction of an edge: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Contracting edge, contraction of an edge''' --- стягивание ребра. If <math>G</math> is a graph and <math>(u,v)</math> is an edge of <math>G</math…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Contracting edge, contraction of an edge''' | '''Contracting edge, contraction of an edge''' — ''[[стягивание ребра]].'' | ||
If <math>G</math> is a graph and <math>(u,v)</math> is an edge of <math>G</math>, the graph obtained by | 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. | ||
'''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 ''neighborhood'' | |||
of <math>u</math>. '''Contracting a subgraph''' means contracting all edges of it | * Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
(the order in which the contraction is made is irrelevant). Note that | |||
multiple edges may appear. | |||
Текущая версия от 18:17, 2 февраля 2016
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.