аря його спадкоємці знайшли заповіт, в якому було сказано, що для відшукання скарбів достатньо увійти в одну з крайніх кімнат підземелля, пройти через усі двері, причому в точності по одному разу через кожну; скарби сховані за тими дверима, яка буде пройдена останньої. У якій кімнаті були приховані скарби? <В
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
В
Побудуємо граф, вершинами якого є кімнати підземелля, а ребрами - двері. Потім знайдемо такий шлях, щоб пройти по всіх ребрах (через усі двері) в точності по одному разу.
В
Даний граф має Ейлером шлях, так як тільки дві вершини мають непарну ступінь, це вершини 6 і 18. Значить, вхід і вихід можуть бути тільки у вершинах 6 і 18.
Так як кімната 6 є крайньою, то в ній буде вхід, значить, останній кімнатою буде 18-а, отже скарби приховані в цій кімнаті. <В
Висновок
У даній роботі були розглянуті основні поняття теорії графів, їх види. Велика увага приділили питанню існування в них ейлерових ланцюгів і циклів, розглянули ряд теорем і властивостей. Описали алгоритм знаходження ейлерова циклу в довільному графі, а в практичній частини показали його застосування на конкретних прикладах. p> Відомо, що Ейлерови графи отримали широке поширення і популярність завдяки тому, що багато головоломки й завдання можна вирішити з використанням знань теорії графів. Приватні приклади таких головоломок і сюжетних завдань були приведені в практичній частині. Завдання на відшукання шляхів через лабіринти, близькі до завдань на Ейлерови графи, знаходять застосування в сучасній психології і при конструюванні обчислювальних машин. Також з практичної точки зору, зараз графи застосовують в багатьох інших галузях науки таких як: програмування, фізика, хімія, біологія, економіка і т.д. <В
Література
1. Андерсон, Джеймс А. Дискретна математика і комбінаторика: пров. з англ. - М.: Видавничий дім «³льямсВ», 2003. - 960с. p> 2. Березина Л. Ю. Графи та їх застосування. - М.: Просвещение, 1979. p> 3. Новіков С.А. Дискрет...
