II. Задачи для усвоения материала. I. Необходимые определения и формулировки теорем

I. Необходимые определения и формулировки теорем.

Эйлерова цепь (цикл). Формула Эйлера.

Плоские и планарные графы»

1. Что такое эйлерова цепь?

2. Что такое эйлеров цикл?

3. У каких графов существует эйлерова цепь?

4. У каких графов существует эйлеров цикл?

5. В чем состоит формула Эйлера?

6. Для каких объектов верна формула Эйлера?

7. Как выглядят непланарные графы № 1, № 2, типов 1, 2?

8. В чем состоит теорема Куратовского-Понтрягина?

ЗАДАЧА ЭЙЛЕРА

1. Обладают ли эйлеровой цепью (или эйлеровым циклом) следующие графы:

а) б) в)

г) д) е)

ж)

ФОРМУЛА ЭЙЛЕРА

Для любого плоского или планарного связного графа (к которым, заметим, относятся все многогранники в пространстве) верна формула В + Г– Р = 2, где В – число вершин, Г – число граней, Р – число ребер графа.

2. Считая данные графы планарными, выяснить, сколько граней получится после преобразования их в плоские («распутывания»):

3*. а) Пусть k – число граней правильного многогранника, сходящихся в одной вершине. Доказать геометрически, что всегда 3 £ k £ 5.

б) Правильный многогранник называется октаэдром (от греческого "окта" – восемь, "эдр" – грань). Выяснить форму его граней.

в) То же для додекаэдра (додека – двенадцать) и икосаэдра (икоса - двадцать).

г) Выявить все возможные правильные многогранники.

НЕПЛОСКИЕ ГРАФЫ

4. Являются ли данные графы плоскими (планарными)?

г) д) е)

ж) з)

10. «Раскраски графа».

Дата добавления: 2014-11-25