Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


ƒоказательство




ќт противного. ѕусть G Ч не гамильтонов. ƒобавим к G минимальное количество новых вершин u1, Е,un, соедин€€ их со всеми вершинами G так, чтобы GТ:= G + u1 + Е + un был гамильтоновым.

ѕусть v, u1, w, Е,v Ч гамильтонов цикл в графе GТ, причем v G, u1 GТ, u1 G. “ака€ пара вершин v и u1 в гамильтоновом цикле об€зательно найдетс€, иначе граф G был бы гамильтоновым. “огда w G, w {u1,Е,un}, иначе вершина u1 была бы не нужна. Ѕолее того, вершина v несмежна с вершиной w, иначе вершина u1 была бы не нужна.

ƒалее, если в цикле v,u1,w, Е,uТ,wТ, Е,v есть вершина wТ, смежна€ с вершиной w, то вершина vТ несмежна с вершиной v, так как иначе можно было бы построить гамильтонов цикл v,vТ, Е,w,wТ, Е,v без вершины u1, вз€в последовательность вершин w, Е,vТ в обратном пор€дке. ќтсюда следует, что число вершин графа GТ, не смежных с v, не менее числа вершин, смежных с w. Ќо дл€ любой вершины w графа G d(w) ≥ p/2+n по построению, в том числе d(v) ≥ p/2+n. ќбщее число вершин (смежных и не смежных с v) составл€ет n+p-1. “аким образом, имеем:

n+p-1 = d(v)+d(V) ≥ d(w)+d(v) ≥ p/2+n+p/2+n = 2n+p.

—ледовательно, 0 ≥ n+1, что противоречит тому, что n > 0.

“еорема ќре. ≈сли число вершин графа G(V,E) n ≥ 3 и дл€ любых двух несмежных вершин u и v выполн€етс€ неравенство:

d(u)+d(v) ≥ n и (u,v) E, то граф G Ч гамильтонов.

√раф G имеет гамильтонов цикл если выполн€етс€ одно из следующих условий:

”словие ѕоша: d(vk) ≥ k+1 дл€ k < n/2.

”словие Ѕонди: из d(vi) ≤ i и d(vk)≤ k => d(vi)+d(vk)≥n (k≠i)

”словие ’ватала: из d(vk) ≤ k ≤ n/2 => d(vn-k) ≥ n-k.

ƒалее, известно, что почти все графы гамильтоновы, то есть


где H(p) Ч множество гамильтоновых графов с p вершинами, а G(p) Ч множество всех графов с p вершинами. “аким образом, задача отыскани€ гамильтонова цикла или эквивалентна€ задача коммиво€жера €вл€ютс€ практически востребованными, но дл€ нее неизвестен (и, скорее всего не существует) эффективный алгоритм решени€.

ѕример графа, когда не выполн€етс€ условие теоремы ƒирака, но граф €вл€етс€ гамильтоновым.

N = 8; d(vi) = 3; 3 ≥ 8/2 = 4 не гамильтонов граф, но существует гамильтонов цикл: M = (1, 2, 3, 4, 5, 6, 7, 8, 1

 





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-10-01; ћы поможем в написании ваших работ!; просмотров: 922 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

—тремитесь не к успеху, а к ценност€м, которые он дает © јльберт Ёйнштейн
==> читать все изречени€...

1333 - | 1275 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.009 с.