Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Ответы, указания и решения

1. Напомним, что выпуклый многогранник называется топологически правильным, если в каждой его вершине сходится одинаковое количество ребер, и все его грани ограничены одинаковым числом ребер. Это означает, что степень каждой вершины соответствующего плоского графа многогранника равна постоянному числу л, а степень каждой вершины двойственного графа также постоянна и равна т. Используя формулы (1.4.1) и (2.3.2) можно

. . 2-е 2-е

записать: m-f — 2-e-n-v, или /=-; v =-.

т п

Подставляя эти выражения в формулу Эйлера (2.3.1),

2-е 2-е

получим, что --ел--= 2 . Последнее равенство

т п

можно записать в виде:

Следовательно,

Так как количество ребер, граней и вершин

выражается натуральными числами, то приходим к неравенству

которое можно переписать в виде

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

п

т

f

е

V

многогранник

3

3

4

в

4

тетраэдр

3

4

8

12

6

октаэдр

3

5

20

30

12

икосаэдр

4

3

6

12

8

гексаэдр (куб)

5

3

12

30

20

додекаэдр

Итак, существует ровно пять типов правильных многогранников: тетраэдр, куб, октаэдр, додекаэдр и икосаэдр. При этом куб двойственен октаэдру, икосаэдр - додекаэдру, а тетраэдр является самодвойственным пересечения. Рассмотрим любую простую замкнутую кривую, например - окружность, внутри которой лежат все выделенные 15 точек. Каждая прямая пересечет эту окружность в двух точках, и всего добавится 12 точек. Граф G, вершинами которого являются 27=15+12 отмеченных точек, а ребрами - отрезки прямых и дуги окружности, соединяющие 27 вершин, является плоским и имеет столько же внутренних граней, на сколько 6 прямых делят плоскость (см. рис. 106). Подсчитаем число граней графа G. Он имеет v=27 вершин и е~6-6+12=48 ребер (так как на каждой из 6 прямых имеется 6 ребер и 12 ребер содержит окружность). Используя формулу Эйлера, получим, что 2=v-e+/ = 27-48 + /.

многогранником. Графы двойственных многогранников являются двойственными плоскими графами.

2. Каждая прямая пересекается с пятью другими в пяти точках, и через каждую точку проходят ровно две

56 прямые. Следовательно, всего имеется —^— = 15 точек

искомое число областей „

Рис. 106

равно 22.

3. Рассмотрим плоский граф, соответствующий условию задачи. Он будет иметь внешнюю грань, ограниченную 30 ребрами (так как на сторонах четырехугольника вместе с вершинами имеется 4+5+6+7+8=30 точек), а все его внутренние грани будут треугольными. Подсчитаем сумму всех ребер, ограничивающих все грани (она равна удвоенному числу ребер): (f —1)3 + 30 = . Следовательно,

Следовательно, / = 23, и искомое число областей равно 22.

3(/ -1) + 30

е —---. Из формулы Эйлера находим, что

, .. 3(/-1) + 30 , 30-3(/-1)+2/ 33-/

2 = v-e+/ = 30----+/ =-2-= ~

Из последнего равенства следует, что f = 29. Таким образом, количество внутренних граней / — 1 = 28. Итак, четырехугольник разобьется на 28 граней.

4. Условие задачи моделирует плоский связный однородный граф четвертой степени (все вершины имеют степень 4). Этот граф содержит v=n(n-l) вершин, так как каждая из и окружностей пересекается с п-1 окружностью в двух точках и каждая точка принадлежит ровно двум окружностям. Из формулы (1.4.1) находим, что 2e=4v, или e=2v=2n(n-l). Используя формулу Эйлера, получим, что / = 2 + e-v = 2 + 2 п(п - 1) - п{п - 1) = 2 + п{п - 1).

Итак, искомое число областей равно 2+п(п-1).

5. Полученный граф G имеет и-угольную внешнюю грань, а все его внутренние грани - треугольные. Добавив во внешней грани п-3 ребра, получим плоскую триангуляцию G' с п+т вершинами, являющуюся сверхграфом графа G. Эта триангуляция имеет 3(п+т)-6 ребер (см. формулу (2.3.7)). Следовательно граф G имеет

е = (3(и + т) - б) - (и - 3) = 2п + Зт - 3 ребер. В силу

формулы Эйлера имеем: п + т- (2п + Зт - 3) + / — 2. Поэтому для числа граней графа G справедливо соотношение / = п + 2т -1, а для числа внутренних (треугольных) граней справедливо равенство / - 1 = и + 2т - 2 .

6. Рассмотрим внешнюю грань полученного графа и обозначим через п количество вершин, лежащих на границе этой грани. Граф имеет е = 2п + Ът-Ъ ребер (см. задачу 5), здесь п+т-1000 и т- число точек, не примыкающих к внешней грани. Следовательно

е=3(л+/и)-л-3 = 3 1000-л-3 = 2997-л, т.е. л=2997-е. Так как количество вершин на границе внешней грани (граница внешней грани является выпуклым и-угольником) удовлетворяет условию 3 < л < 1000, то

  • 3< 2997-е < 1000 и 1997 <е< 2994 . Итак, границы изменения числа отрезков равны 1997 (если граница внешней грани - 1000-угольник) и 2994 (если граница внешней грани - треугольник).
  • 7. Если внутри л-угольника взяты т точек и после соединения этих точек между собой и с вершинами л-угольника получилось разбиение л-угольника на четырехугольники, то, используя формулу (2.3.2), найдем: 2е - 4(/ - 1) + и. Следовательно, л - четно. Так как

v = л + т и е = 2(/ - 1) + —, то из формулы Эйлера получим: п + т- 2 (/ — 1) — — + / = 2, т.е. количество

, . и

четырехугольников равно J - 1 = — + т — 1. [1]

  • 9. Предположим противное, что все грани графа ограничены не менее чем шестью ребрами, т.е. <7 *(h,) > 6, 1 = 1,2,...,/. Просуммировав эти / неравенств, из формулы (2.3.2) получим, что V е
  • 2е = 2^0 *(Д) ^6/, т.е. / < —. С другой стороны, так /=1 3

как каждая вершина Л, (/=7, 2 ,... ,v) имеет степень, большую или равную трем, т.е. a (AJ >3, i = l,2,...,v, то, просуммировав эти v неравенств, из формулы (1.4.1) ^ 2е

получим, что = /_,& (Л,) > 3v, т.е. v < —. Следова-

/=| 3

2е е

тельно, 2 = v - е + f < — - е + — = 0 и 2<0. Получили противоречие.

10. Граф, двойственный

графу из многоугольников, можег не являться графом из многоугольников. Так, например, два графа на рис. 107 являются двойственными, но один из них имеет параллельные ребра и не является графом из мно- Рис. 107

гоугольников.

11. Предположим, что степень каждой вершины однородного плоского графа равна п. Тогда 2e=v n. Так как граф является самодвойственным, то / =v. С учетом вышесказанного формула Эйлера примет вид:

п-v 4

v — —— + v = 2 . Следовательно, v =-, и лишь при

2 ' 4-и

п=0, «=2 или и=3 получаем натуральные значения для у. Итак, однородный самодвойственный граф может содержать либо одну вершину степени 0 (рис. 108), либо две вершины степени 2 (рис. 109), либо четыре вершины степени 3 (рис. ПО). Других самодвойственных однородных графов не существует.

Рис. 109 Рис. 110

Рис. 108 Рис. 109 Рис. 110

Пусть нам задан некоторый плоский граф G(V,E,F), имеющий v вершин, е ребер и / граней. Условимся, что в дальнейшем будем использовать следующие обозначения: у, - количество вершин из V, имеющих степень /; f - количество граней из F, ограниченных i ребрами.

Очевидно, что имеют место следующие соотношения:

12. Докажем, что 2e>3v. Так как многогранник является графом из многоугольников, то

Из формулы Эйлера следует, что 6v-6e+6/ = 12. Поэтому 6/-12 = 6e-6v. Но > 3v и 6v<4e. Значит, 6/-12=6е-6у>6е-4е=2е.

Итак, 6/ - 12 > 2е.

Наконец, докажем, что 3v > 6 + е. Действительно, 6v-6e+6f = 12. Следовательно, 3v = 3e-3/ + 6.

Но так как 2е> 3/ то

13. Из формулы Эйлера имеем 6v-6e+6f = 12. Подставив в эту формулу следующие выражения: 6v < 4е, 2е = 3/3 + 4/4+5/5+... и / = /3 +/4 .

получим

4е-4е-(3/3 + 4/4 +5/5+...) + 6(/3 +/4 +/5+...) >12, или З/з + 2/4+/5 > 12. Так как по условию задачи fA=f5- 0, получим, что /з > 4.

14. Обозначим сумму плоских углов всех граней многогранника за S, а сумму углов плоского многоугольника с тем же количеством вершин через S'. Нам надо доказать, что S = 2S". Имеем: S' = n(v — 2), где v - количество вершин. Если i-я грань многогранника ограничена р, ребрами, то сумма углов этой грани равна л (р, — 2). Следовательно,

/

Здесь было учтено, что "^р, = (см. формулу (2.3.2)), и

/.I

была использована формула Эйлера (из которой следует, что е- f = v-2).

15. Предположим противное, что в графе

многогранника все вершины имеют степень, большую трех, и все грани ограничены более чем тремя ребрами. Тогда формулы (2.3.15) и (2.3.16) примут вид: 2е = 4v4 + 5v5 +... и = 4/4 +5/5+... . Мы можем записать:

= 4v4 +5vs+...>4v4 +4v5+...= 4(v4 +v5+...) = 4v и

T.e. e>2v и е>2/.

Складывая эти неравенства, получим, что 2е > 2v + 2/, или v - е + / < 0. Мы получили противоречие с формулой Эйлера. Следовательно, либо в многограннике существует треугольная грань, либо - трехгранный угол.

  • 16. Пусть существует многогранник нулевого рода, имеющий 7 ребер, е=7. Найдем число его вершин. Так как 3v < 2е (см. задачу 12), то 3v < 14. Но так как v - натуральное число, большее трех, то v-4. Из формулы Эйлера находим, что / = 2 + e- v = 2 + 7- 4 = 5. С другой стороны, для графа этого многогранника должно выполняться неравенство (2.3.3): 2е>Ъ/, т.е. 14 >15. Полученное противоречие доказывает, что многогранник нулевого рода (и тем более выпуклый многогранник) не может иметь 7 ребер.
  • 17. Обозначим через 5, сумму плоских углов выпуклого многогранника при i-й вершине. Требуется

у

доказать, что 51 (2л -S,) = 4л. Действительно, так / = 1

у

как 51= S, где S - сумма всех плоских углов

/=1

многогранника, то, используя задачу 14, получим

18. Граф на рис. 103 изоморфен прямолинейному графу куба (см. рис. 111), а граф на рис. 104 изоморфен прямолинейному графу октаэдра (см. рис. 112). Действительно, для каждого из этих двух случаев соответствие вершин с одинаковыми номерами задает отображение изоморфизма.

Ill Рис. 112

Рис. Ill Рис. 112

19. В силу формулы (2.3.12) соответствующий двудольный граф имеет 2 -r)s2 = (З2 — 3)22 = 24

реберных пересечений. Для превращения этого графа с 11=6+5 вершинами в максимально плоский двудольный граф, необходимо удалить Ae=(v, -2)(v2 -2) =(6-2Х5-2) = 12 ребер (см. вывод соотношений (2.3.10)). Итак, достаточно закрыть 12 рельсовых путей от печей к платформам, чтобы избавиться от всех 24 рельсовых пересечений.

  • [1] Предположим противное, что в графе из многоугольников каждая вершина Л, (/=/, 2 ,... ,v) имеетстепень, большую или равную шести, т.е. a (At) >6, / = 1,2,___,v. Просуммировав эти v неравенств, из формулы (1.4.1) получим, что V 2е = ^ ст (Л,) > 6v, т.е. е > 3v . Но, с другой стороны, из1=1 неравенства (2.3.4) имеем: е < 3v - 6. Следовательно,3v — 6 > 3v, т.е. - 6 > 0. Полученное противоречиедоказывает, что в графе из многоугольников существуетвершина, степень которой меньше шести.
 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы