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