ному з решти, призвело б до незв'язні графу, що суперечить умові 2). [5]
Глава 2. Практична частина
Завдання:
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, тобто непарну, отже, в цьому графі (За критерієм) немає ейлерова циклу. p> 2. Де на виставці слід було б зробити вхід і вихід (рис.8), щоб можна було провести екскурсію по всіх залах, побувавши в кожному з них в точності один раз? [2]
В
В
Рис.8
Рішення:
Цього графі вершини А і В мають ступінь 3, то є непарну, отже, в ньому існує Ейлером шлях з початком в одній з цих вершин і кінцем в іншій. Значить, вхід і вихід слід встановити в вершинах А і В.
3. Серед наведених нижче графів знайдіть ті, які мають Ейлером цикл. [1]
В
В
Рішення:
а) Т.к. цей граф зв'язний і кожна його вершина має парну ступінь, то за умовою ейлерова графа, даний граф має Ейлером цикл:
a b e j i f c b d h j g f a c d e h g i a
б) Цей граф зв'язний, але тому всі його вершини мають непарну ступінь, то він не має ейлерова циклу. p> в) Цей граф зв'язний, але тому всі його вершини мають ступінь 3, тобто непарну, то він не має ейлерова циклу. p> г) Даний граф зв'язний, ступеня вершин а і з мають непарну ступінь, значить, цей граф не має ейлерова циклу.
4. Серед наведених нижче графів знайдіть ті, які мають Ейлером цикл. [1]
В
Рішення:
а) Граф не є зв'язковим, тобто не виконується перша умова критерію, значить, він не має ейлерова циклу.
б) Цей граф є зв'язним і всі його вершини мають парну ступінь, значить, за умовою ейлерова графа, він має Ейлером цикл:
a c f h I j k g d c b f I l j g e d a
в) Даний граф зв'язний, але ступеня вершин а і е непарні, отже за критерієм, цей граф не має ейлерова циклу. p> г) Граф є зв'язковим, але так як всі його вершини мають непарну ступінь, то граф не має ейлерова циклу.
5. Серед наведених нижче графів знайдіть ті, які мають власний Ейлером шлях. [1]
В
Рішення:
а) Граф зв'язний, і тільки дві його вершини (a і f) мають непарну ступінь, отже, то по теоремі 3, граф має власний Ейлером шлях.
б) Граф зв'язний; deg (a) = 3, deg (b) = 3, deg (c) = 3, то є більше двох вершин мають непарну ступінь, значить, не має ейлерова шляху.
в) Цей граф зв'язний і тільки дві вершини (з і j) мають непарну ступінь, значить, граф має власний Ейлером шлях.
...
