Amalgamation of a graph: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Amalgamation of a graph''' --- амальгамация графа. Amalgamating a graph <math>H</math> can be thought of as taking <...)
 
Нет описания правки
 
Строка 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>.

Текущая версия от 16:30, 23 октября 2018

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].