Читайте также:
|
Теорема. Пусть связный граф имеет п вершин и п 
3. Если в этом графе для степени любой вершины А выполняется неравенство 
, то он обладает гамильтоновым циклом.
Следствие 1. В полном графе:
а) количество циклов n!
б) любая неповторяющаяся последовательность вершин является гамильтоновым путем.
Следствие 2. Пусть элементарный связный граф имеет п вершин и п 3. Если в этом графе для любой пары вершин А и В выполняется неравенство 
, то он обладает гамильтоновым циклом.
Теорема. Если при п 3 элементарный связный граф имеет п вершин и для любой его пары вершин А и В выполняется неравенство 
, то он обладает гамильтоновой цепью.
Дата добавления: 2015-07-11; просмотров: 94 | Нарушение авторских прав