-
Задачи для усвоения материала.
ЗАДАЧА ЭЙЛЕРА
1. Обладают ли эйлеровой цепью (или эйлеровым циклом) следующие графы:
а)
б) в)
г)
д)
е)
ж)
ФОРМУЛА ЭЙЛЕРА
|
Для любого плоского или планарного связного графа (к которым, заметим, относятся все многогранники в пространстве) верна формула В + Г– Р = 2, где В – число вершин, Г – число граней, Р – число ребер графа. |
2. Считая данные графы планарными, выяснить, сколько граней получится после преобразования их в плоские («распутывания»):
|
|
|
3*. а) Пусть k – число граней правильного многогранника, сходящихся в одной вершине. Доказать геометрически, что всегда 3 £ k £ 5.
б) Правильный многогранник называется октаэдром (от греческого "окта" – восемь, "эдр" – грань). Выяснить форму его граней.
в) То же для додекаэдра (додека – двенадцать) и икосаэдра (икоса - двадцать).
г) Выявить все возможные правильные многогранники.
НЕПЛОСКИЕ ГРАФЫ
4. Являются ли данные графы плоскими (планарными)?
г)
д)
е)
ж)
з)
К практическому занятию 11 Итоговое повторение раздела 2. Контрольная работа № 2.
-
Основные вопросы.
-
Что такое орграф, граф, вершина, дуга, ребро, путь, цепь, контур, цикл?
-
Каков алгоритм решения задачи о кратчайшем пути в невзвешенном графе?
-
Каков алгоритм решения задачи о кратчайшем пути во взвешенном графе?
-
Что такое эйлерова цепь (цикл), у каких графов они существуют?
-
В чем состоит формула Эйлера и для каких объектов она верна?
-
Как выглядят непланарные графы № 1, № 2, типов 1, 2 и в чем состоит теорема Куратовского-Понтрягина?
-
Контрольная работа.
Вариант 0
-
Вопрос по теории.
-
Обладает ли эйлеровой цепью (или эйлеровым циклом) следующий граф?
-
Является ли данный граф плоским? (планарным)
-
Считая данный граф планарным, определить количество его граней.
-
Дан граф:
Найти кратчайший
путь из точки
в точку В (в смысле наименьшего количества
рёбер).
-
Дан граф.
B
A
а) Превратить его во взвешенный, используя следующие данные
б) Найти кратчайший
путь из точки
в точку В (в смысле наименьшей суммы
весов).