Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Некоторые свойства гамильтоновых графов



Читайте также:
  1. II. Собственно свойства пульса.
  2. III. Психические свойства, влияющие на безопасность.
  3. V2: Механические свойства материалов
  4. Алюминий: физические свойства, получение, применение, история
  5. Аметист камень - свойства.
  6. Ассортимент, потребительские свойства, экспертиза качества молока и молочных продуктов
  7. Ассортимент, потребительские свойства, экспертиза качества рыбы и рыбных продуктов

Теорема. Пусть связный граф имеет п вершин и п 3. Если в этом графе для степени любой вершины А выполняется неравенство , то он обладает гамильтоновым циклом.

Следствие 1. В полном графе:

а) количество циклов n!

б) любая неповторяющаяся последовательность вершин является гамильтоновым путем.

Следствие 2. Пусть элементарный связный граф имеет п вершин и п 3. Если в этом графе для любой пары вершин А и В выполняется неравенство , то он обладает гамильтоновым циклом.

Теорема. Если при п 3 элементарный связный граф имеет п вершин и для любой его пары вершин А и В выполняется неравенство , то он обладает гамильтоновой цепью.

 

 



Дата добавления: 2015-07-11; просмотров: 94 | Нарушение авторских прав






mybiblioteka.su - 2015-2024 год. (0.005 сек.)