Vertex Contraction
المؤلف:
Pemmaraju, S. and Skiena, S.
المصدر:
"Contracting Vertices." §6.1.1 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press
الجزء والصفحة:
...
12-4-2022
1861
Vertex Contraction
The contraction of a pair of vertices 
and 
of a graph, also called vertex identification, is the operation that produces a graph in which the two nodes 
and 
are replaced with a single node 
such that 
is adjacent to the union of the nodes to which 
and 
were originally adjacent. In vertex contraction, it doesn't matter if 
and 
are connected by an edge; if they are, the edge is simply removed upon contraction (Pemmaraju and Skiena 2003, p. 231). Note that Skiena (1990, p. 91) is ambiguous about the distinction between vertex contraction and edge contraction, and confusingly refers to vertex contraction on vertices 
and 
as "contracting an edge ![<span style=]()
{v_1,v_2}" src="https://mathworld.wolfram.com/images/equations/VertexContraction/Inline13.svg" style="height:22px; width:55px" />."
The figure above shows a random graph contracted on vertices 
and 
.
Vertex contraction is implemented in the Wolfram Language as VertexContract[g, ![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/VertexContraction/Inline16.svg" style="height:22px; width:6px" />v1, v2, ...![<span style=]()
}" src="https://mathworld.wolfram.com/images/equations/VertexContraction/Inline17.svg" style="height:22px; width:6px" />].
REFERENCES
Pemmaraju, S. and Skiena, S. "Contracting Vertices." §6.1.1 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, pp. 231-234, 2003.
Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 91, 1990.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
