г) Граф зв'язний; 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 не виконується. Значить, граф не має ейлерова циклу. p> в) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 2 outdeg (a) = 1
Друга умова теореми 5 не виконується, значить, граф не має ейлерова циклу.
г) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 2 outdeg (a) = 2
indeg (b) = 3 outdeg (b) = 1
Граф не має ейлерова циклу, тому що не виконується друга умова теореми 5.
9. На малюнку план підземелля, в одній з кімнат якого приховані багатства лицаря. Після смерті лиц...
