Contracting edge, contraction of an edge

Материал из WikiGrapp
Перейти к:навигация, поиск

Contracting edge, contraction of an edgeстягивание ребра.

If \,G is a graph and \,(u,v) is an edge of \,G, the graph obtained by contracting edge \,(u,v) is the graph obtained from \,G[V \setminus \{u,v\}] by adding a new vertex \,z and adding edges \,(z,w) for all \,w \in (N(u) \cup N(v)) \setminus \{u,v\}, where \,N(u) is the neighborhood of \,u. 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.