Cyclability: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Cyclability''' --- цикличность. A subset <math>S</math> of vertices of a graph <math>G</math> is called '''cyclable''' in <math>G</math> if there is …»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Cyclability''' --- цикличность.  
'''Cyclability''' — ''[[цикличность]]''.
 
A subset <math>\,S</math> of [[vertex|vertices]] of a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> is called '''cyclable''' in
<math>\,G</math> if there is in <math>\,G</math> some cycle containing all the vertices of <math>\,S</math>.
It is known that if <math>\,G</math> is a [[k-Connected graph|<math>\,3</math>-connected graph]] of order <math>\,n</math> and if <math>\,S</math>
is a subset of vertices such that the degree sum of any four independent vertices of <math>\,S</math> is at least <math>\,n + 2\alpha (S,G) - 2</math>, then <math>\,S</math> is cyclable. Here <math>\alpha (S,G)</math> is the number of vertices of a maximum independent set of <math>\,G[S]</math>.


A subset <math>S</math> of vertices of a graph <math>G</math> is called '''cyclable''' in
<math>G</math> if there is in <math>G</math> some cycle containing all the vertices of <math>S</math>.
It is known that if <math>G</math> is a 3-connected graph of order <math>n</math> and if <math>S</math>
is a subset of vertices such that the degree sum of any four
independent vertices of <math>S</math> is at least <math>n + 2\alpha (S,G) - 2</math>, then
<math>S</math> is cyclable. Here <math>\alpha (S,G)</math> is the number of vertices of a
maximum independent set of <math>G[S]</math>.
==See also==
==See also==
*''Pancyclable graph''.
 
* ''[[Pancyclic graph|Pancyclable graph]]''.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 15:56, 14 декабря 2021

Cyclabilityцикличность.

A subset [math]\displaystyle{ \,S }[/math] of vertices of a graph [math]\displaystyle{ \,G }[/math] is called cyclable in [math]\displaystyle{ \,G }[/math] if there is in [math]\displaystyle{ \,G }[/math] some cycle containing all the vertices of [math]\displaystyle{ \,S }[/math]. It is known that if [math]\displaystyle{ \,G }[/math] is a [math]\displaystyle{ \,3 }[/math]-connected graph of order [math]\displaystyle{ \,n }[/math] and if [math]\displaystyle{ \,S }[/math] is a subset of vertices such that the degree sum of any four independent vertices of [math]\displaystyle{ \,S }[/math] is at least [math]\displaystyle{ \,n + 2\alpha (S,G) - 2 }[/math], then [math]\displaystyle{ \,S }[/math] is cyclable. Here [math]\displaystyle{ \alpha (S,G) }[/math] is the number of vertices of a maximum independent set of [math]\displaystyle{ \,G[S] }[/math].

See also

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.