Дата: 28.04.2020 (2 часа). ИСиП Дискретная математика с элементами математической логики. Практическое занятие №18. Планарные графы. Эйлеровы графы. Гамильтоновы графы

Дата: 28.04.2020 (2 часа)

19-11-2 ИСиП Дискретная математика с элементами математической логики

Практическое занятие №18

Планарные графы. Эйлеровы графы. Гамильтоновы графы

1. Дана каркасная модель объёмного тела с 20 вершинами, 30 рёбрами и 12 гранями.

Можно ли получить планарную реализацию данной каркасной модели? Ответ обоснуйте.

2. На рисунке ниже представлен граф.

Можно ли получить для данного графа его планарную реализацию? Ответ обоснуйте.

3. Дан полный граф с пятью вершинами.

Можно ли в таком графе пройти по всем рёбрам, используя проход по каждому ребру только 1 раз? Ответ обоснуйте.

4. Какие из приведённых графов являются эйлеровыми и/или гамильтоновыми? Ответ обоснуйте.