Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


ѕрактическа€ часть. 1. —уществует ли эйлеров цикл в графе G




«адачи:

1. —уществует ли эйлеров цикл в графе G. ≈сли существует, найдите его.[2]

–ешение:

ј) “ак как кажда€ вершина имеет чЄтную степень, то по критерию в этом графе существует эйлеров цикл: 1,4,6,9,10,8,5,3,2,4,7,10,11,8,6,5,2,1

Ѕ) ¬ этом графе также кажда€ вершина имеет чЄтную степень, значит, существует и эйлеров цикл: 1,2,3,4,5,3,1,4,5,2,1

¬) «десь кажда€ вершина имеет степень 5, то есть нечЄтную, следовательно, в этом графе (по критерию) нет эйлерова цикла.

 

 

2. √де на выставке следовало бы сделать вход и выход (рис.8), чтобы можно было провести экскурсию по всем залам, побывав в каждом из них в точности один раз?[2]

–ешение:

¬ этом графе вершины ј и ¬ имеют степень 3, то есть нечЄтную, следовательно, в нЄм существует эйлеров путь с началом в одной из этих вершин и концом в другой. «начит, вход и выход следует установить в вершинах ј и ¬.

3. —реди приведЄнных ниже графов найдите те, которые имеют эйлеров цикл.[1]

 

 

–ешение:

а) “.к. этот граф св€зный и кажда€ его вершина имеет чЄтную степень, то по критерию эйлерова графа, данный граф имеет эйлеров цикл:

a b e j i f c b d h j g f a c d e h g i a

б) Ётот граф св€зный, но т.к. все его вершины имеют нечЄтную степень, то он не имеет эйлерова цикла.

в) Ётот граф св€зный, но т.к. все его вершины имеют степень 3, то есть нечЄтную, то он не имеет эйлерова цикла.

г) ƒанный граф св€зный, степени вершин а и с имеют нечЄтную степень, значит, этот граф не имеет эйлерова цикла.

4. —реди приведЄнных ниже графов найдите те, которые имеют эйлеров цикл.[1]

 

 

–ешение:

а) √раф не €вл€етс€ св€зным, то есть не выполн€етс€ первое условие критери€, значит, он не имеет эйлерова цикла.

б) Ётот граф €вл€етс€ св€зным и все его вершины имеют чЄтную степень, значит, по критерию эйлерова графа, он имеет эйлеров цикл:

a c f h I j k g d c b f I l j g e d a

в) ƒанный граф св€зный, но степени вершин а и е нечЄтные, следовательно по критерию, этот граф не имеет эйлерова цикла.

г) √раф €вл€етс€ св€зным, но так как все его вершины имеют нечЄтную степень, то граф не имеет эйлерова цикла.

5. —реди приведЄнных ниже графов найдите те, которые имеют собственный эйлеров путь.[1]

 

–ешение:

а) √раф св€зный, и только две его вершины (a и f) имеют нечЄтную степень, следовательно, то по теореме 3, граф имеет собственный эйлеров путь.

б) √раф св€зный; deg(a)=3, deg(b)=3, deg(c)=3, то есть более двух вершин имеют нечЄтную степень, значит, не имеет эйлерова пути.

в) Ётот граф св€зный и только две вершины (с и j) имеют нечЄтную степень, значит, граф имеет собственный эйлеров путь.

г) √раф св€зный; deg(a)=3, deg(b)=4, deg(c)=1, deg(d)=3, то есть более двух вершин имеют нечЄтную степень, следовательно, в этом графе нет эйлерова пути.

6. —реди приведЄнных ниже графов найдите те, которые имеют собственный эйлеров цикл.[1]

 

–ешение:

а) ƒанный граф св€зный; deg(a)=3, deg(b)=2, deg(c)=3, deg(d)=2, deg(e)=2. –овно две вершины имеют нечЄтную степень, значит, по теореме 3, граф имеет собственный эйлеров путь.

 

б) √раф €вл€етс€ св€зным и ровно две его вершины (е и f) имеют нечЄтную степень, значит, данный граф имеет собственный эйлеров путь.

в) √раф св€зный, найдЄм степени вершин: deg(d)=5, deg(b)=5, deg(e)=5, нашлись три вершины, степень которых нечЄтна€, значит, граф не имеет эйлерова пути.

г) ƒанный граф св€зный и только две его вершины (а и b) имеют нечЄтную степень, значит, этот граф имеет собственный эйлеров путь.

7.  акие из следующих ориентированных графов имеют эйлеровы циклы? [1]

–ешение:

а) √раф св€зный, найдЄм степени входа и выхода вершин (по теореме 5 степени входа и выхода каждой вершины должны совпадать):

indeg(a)=2, outdeg(a)=1, то есть нашлась вершина, у которой не совпадают степени входа и выхода, значит, граф не имеет эйлерова цикла.

б) √раф св€зный, найдЄм степени вершин:

indeg(a)=2 outdeg(a)=2

indeg(b)=2 outdeg(b)=2

indeg(c)=2 outdeg(c)=2

indeg(d)=2 outdeg(d)=2

indeg(e)=2 outdeg(e)=2

—ледовательно, по теореме 5, граф имеет эйлеров цикл.

 

 

в) √раф св€зный, найдЄм степени вершин:

indeg(a)=2 outdeg(a)=2

indeg(b)=1 outdeg(b)=1

indeg(c)=3 outdeg(c)=1

”слови€ теоремы 5 не выполн€ютс€, значит, граф не имеет эйлерова цикла.

г)) √раф св€зный, найдЄм степени вершин:

indeg(a)=2 outdeg(a)=1

—ледовательно, т.к. услови€ теоремы 5 не выполн€ютс€ то, граф не имеет эйлерова цикла.

8.  акие из следующих ориентированных графов имеют эйлеровы циклы? [1]

 

 

–ешение:

а) √раф св€зный, найдЄм степени вершин:

indeg(a)=1 outdeg(a)=1

indeg(b)=5 outdeg(b)=1

“.к. второе условие теоремы 5 не выполн€етс€, значит, граф не имеет эйлерова цикла.

б) √раф не св€зный, то есть первое условие теоремы 5 не выполн€етс€. «начит, граф не имеет эйлерова цикла.

в) √раф св€зный, найдЄм степени вершин:

indeg(a)=2 outdeg(a)=1

¬торое условие теоремы 5 не выполн€етс€, значит, граф не имеет эйлерова цикла.

г) √раф св€зный, найдЄм степени вершин:

indeg(a)=2 outdeg(a)=2

indeg(b)=3 outdeg(b)=1

√раф не имеет эйлерова цикла, т.к. не выполн€етс€ второе условие теоремы 5.

 

 

9. Ќа рисунке план подземель€, в одной из комнат которого скрыты богатства рыцар€. ѕосле смерти рыцар€ его наследники нашли завещание, в котором было сказано, что дл€ отыскани€ сокровищ достаточно войти в одну из крайних комнат подземель€, пройти через все двери, причЄм в точности по одному разу через каждую; сокровища скрыты за той дверью, котора€ будет пройдена последней. ¬ какой комнате были скрыты сокровища?

 

 

 

1  
3      
7      
11        
16      
20    
           

ѕостроим граф, вершинами которого €вл€ютс€ комнаты подземель€, а рЄбрами Ц двери. «атем найдЄм такой путь, чтобы пройти по всем рЄбрам (через все двери) в точности по одному разу.

 

ƒанный граф имеет эйлеров путь, так как только две вершины имеют нечЄтную степень, это вершины 6 и 18. «начит, вход и выход могут быть только в вершинах 6 и 18.

“ак как комната 6 €вл€етс€ крайней, то в ней будет вход, значит, последней комнатой будет 18-а€, следовательно сокровища скрыты в этой комнате.

 

 

«аключение

¬ данной работе были рассмотрены основные пон€ти€ теории графов, их виды. Ѕольшое внимание уделили вопросу существовани€ в них эйлеровых цепей и циклов, рассмотрели р€д теорем и свойств. ќписали алгоритм нахождени€ эйлерова цикла в произвольном графе, а в практической части показали его применение на конкретных примерах.

»звестно, что эйлеровы графы получили широкое распространение и попул€рность благодар€ тому, что многие головоломки и задачи можно решить с использованием знаний теории графов. „астные примеры таких головоломок и сюжетных задач были приведены в практической части. «адачи на отыскание путей через лабиринты, близкие к задачам на эйлеровы графы, наход€т применение в современной психологии и при конструировании вычислительных машин. “акже с практической точки зрени€, сейчас графы примен€ют во многих других област€х науки таких как: программирование, физика, хими€, биологи€, экономика и т.д.

 

 

Ћитература

1. јндерсон, ƒжеймс ј. ƒискретна€ математика и комбинаторика: пер. с англ. Ц ћ.: »здательский дом Ђ¬иль€мсї, 2003. Ц 960с.

2. Ѕерезина Ћ. ё. √рафы и их применение. Ц ћ.: ѕросвещение, 1979.

3. Ќовиков —.ј. ƒискретна€ математика дл€ программистов Ц —ѕб.: ѕитер, 2001. Ц 304с.

4. ќре о. √рафы и их применение. Ц ћ.: ћир,1973.

5. ”илсон –. ¬ведение в теорию графов. Ц ћ.: ћир, 1977.

6. ’арари ‘. “еори€ графов. Ц ћ.: ћир, 1973.

 

 





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


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


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

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

„то разум человека может постигнуть и во что он может поверить, того он способен достичь © Ќаполеон ’илл
==> читать все изречени€...

1546 - | 1421 -


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

√ен: 0.028 с.