Презентация на тему: "Окружность и круг"

Тема: Знакомство с программой grin.exe. Решение задач с помощью программы

Основная цель:

• ознакомиться с программой grin.exe,
• научиться решать задачи с помощью программы.

• Какой путь называется эйлеровым?

Эйлеровым путем в графе называется путь, содержащий все ребра графа.

• Какой цикл называется эйлеровым?

Эйлеровым циклом называется цикл, содержащий все ребра графа и притом только по одному разу.

• Какой граф является эйлеровым?

Эйлеров граф – это граф, обладающий эйлеровым циклом.

• Какой граф называется полуэйлеровым?

Полуэйлеров граф – это граф, содержащий маршрут, обходящий все ребра по одному разу.

Не является полуэйлеров эйлеров

эйлеровым

Графом

Теоремы Эйлера:

Теорема 1. Для того, чтобы связный граф являлся эйлеровым, необходимо и достаточно, чтобы степени всех его вершин были четными.

Теорема 2. Связный граф будет полуэйлеровым тогда и только тогда, когда степени двух его вершин будут нечетными, а степени остальных вершин – четными.

• Какой путь называется гамильтоновым?

Гамильтоновым путем в графе называется путь, проходящий через каждую его вершину и только один раз.

• Какой цикл называется гамильтоновым?

Гамильтоновым циклом называется цикл, проходящий через каждую его вершину и только один раз.

• Какой граф является гамильтоновым?

Гамильтоновым графом называется граф, содержащий гамильтоновый цикл.

V1 V2 V3 V4 V1 V5 – V9 V2 V4 V3 V5 V1 V7

не является

гамильтоновым путем V6 V8 V10 V12 V11 V9

V1 V2 V3 V4 V1 V5 –

гамильтонов путь гамильтоновый цикл

Решение задач:

а)

б)

в)

а)

б)

в)

г)