4634
правки
Amalgamation of a graph: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Amalgamation of a graph''' --- амальгамация графа. Amalgamating a graph <math>H</math> can be thought of as taking <...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Amalgamation of a graph''' | '''Amalgamation of a graph''' — ''[[амальгамация графа]].'' | ||
Amalgamating a graph <math>H</math> can be thought of as taking <math>H</math>, partitioning | Amalgamating a [[graph, undirected graph, nonoriented graph|graph]] <math>\,H</math> can be thought of as taking <math>\,H</math>, partitioning | ||
its vertices, then, for each element of the partition, squashing | its [[vertex|vertices]], then, for each element of the partition, squashing | ||
together the vertices to form a single vertex in the amalgamated graph | together the vertices to form a single vertex in the amalgamated graph | ||
<math>G</math>. Any edges incident with original vertices in <math>H</math> are then | <math>\,G</math>. Any [[edge|edges]] incident with original vertices in <math>\,H</math> are then | ||
incident with the corresponding new vertex in <math>G</math>, and any edge | incident with the corresponding new vertex in <math>\,G</math>, and any edge | ||
joining two vertices that are squashed together in <math>H</math> becomes a | joining two vertices that are squashed together in <math>\,H</math> becomes a | ||
loop on the new vertex in <math>G</math>. The number of vertices squashed | loop on the new vertex in <math>\,G</math>. The number of vertices squashed | ||
together to form a new vertex <math>w</math> is the '''amalgamation number''' | together to form a new vertex <math>\,w</math> is the '''amalgamation number''' | ||
<math>\eta(w)</math> of <math>w</math>. The resulting graph is the '''amalgamation''' of the | <math>\,\eta(w)</math> of <math>\,w</math>. The resulting graph is the '''amalgamation''' of the | ||
original. Formally, this is represented by a graph homomorphism <math>f: | original. Formally, this is represented by a graph homomorphism <math>f: | ||
V(G) \rightarrow V(H)</math>; so for example if <math>w \in V(H)</math>, then <math>\eta(w) | V(G) \rightarrow V(H)</math>; so for example if <math>w \in V(H)</math>, then <math>\,\eta(w) | ||
= |f^{-1}(w)|</math>. | = |f^{-1}(w)|</math>. | ||