Вопросы после параграфа §13 на странице 65, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Конечный связный плоский граф разбивает плоскость на области, и границей каждой служит замкнутый путь. Степень области — длина этой границы, то есть число рёбер в замкнутом пути, по которому граница обходится; ребро, дважды принадлежащее границе одной и той же области, при обходе проходится дважды и дважды же считается.
Ответ: степень области — длина её границы, то есть число рёбер замкнутого пути, ограничивающего область; ребро, дважды входящее в границу, считается дважды.
Плоскость с нарисованным графом — бесконечная резиновая плёнка. Стянем все её бесконечно далёкие края в одну точку: плёнка замкнётся и превратится в сферу, вершины останутся вершинами, рёбра — рёбрами, а новых точек пересечения растяжение не создаёт.
Изменится только внешняя область: из бесконечной она станет обычной ограниченной — той, которая содержит новую точку. Числа вершин, рёбер и областей у графа на сфере такие же, как у исходного плоского графа.
Ответ: плоскость можно стянуть в сферу, как резиновую плёнку: вершины, рёбра и области сохраняются, а бесконечная внешняя область превращается в обычную ограниченную; поэтому всякий плоский граф изображается на сфере.
Для конечного связного плоского графа (а значит, и для графа на сфере) число \(\chi = v - e + f\) всегда равно 2 — сколько бы в графе ни было вершин и рёбер и как бы он ни был нарисован; значит, \(\chi\) не различает графы.
Для связного графа на другой поверхности тот же подсчёт даёт другое число: на торе \(\chi = 0\). Значит, \(\chi\) зависит не от графа, а от поверхности, на которой граф нарисован.
Ответ: для любого связного графа на одной и той же поверхности число \(\chi = v - e + f\) получается одним и тем же (на сфере 2, на торе 0), поэтому оно говорит не о графе, а о поверхности.
Теорема: в любом конечном связном плоском графе сумма степеней всех областей чётна и равна удвоенному числу рёбер.
При обходе границ каждое ребро проходится ровно два раза: либо оно разделяет две области — и тогда его проходят по одному разу при обходе каждой из них, — либо дважды принадлежит границе одной области — и тогда его дважды проходят при обходе этой области.
Ответ: сумма степеней всех областей конечного связного плоского графа чётна и равна удвоенному числу рёбер.
Конечный связный плоский граф разбивает плоскость на области, и границей каждой области служит замкнутый путь. Степенью области называется длина этой границы, то есть число рёбер в замкнутом пути, по которому граница обходится. Ребро, которое дважды принадлежит границе одной и той же области, при обходе проходится дважды и дважды же считается.
Например, квадрат с проведённой диагональю делит плоскость на три области: две треугольные, граница каждой из которых состоит из трёх рёбер, и внешнюю, граница которой — четыре стороны квадрата. Степени этих областей равны 3, 3 и 4.
Ответ: степень области — длина её границы, то есть число рёбер замкнутого пути, ограничивающего область; ребро, дважды входящее в границу, считается дважды.
Представим себе плоскость с нарисованным на ней плоским графом как бесконечную резиновую плёнку. Стянем все её бесконечно далёкие края в одну точку — плёнка замкнётся и превратится в сферу. Вершины при этом останутся вершинами, рёбра — рёбрами, и рёбра, которые не пересекались на плоскости, не пересекутся и на сфере: растяжение плёнки новых точек пересечения не создаёт.
Изменится только внешняя область. На плоскости она бесконечная, а после стягивания краёв в одну точку она становится обычной ограниченной областью — той, которая содержит эту новую точку. Поэтому число вершин, число рёбер и число областей у графа на сфере такие же, как у исходного плоского графа; разница лишь в том, что на сфере все области ограниченные.
Ответ: плоскость можно стянуть в сферу, как резиновую плёнку: вершины, рёбра и области сохраняются, а бесконечная внешняя область превращается в обычную ограниченную; поэтому всякий плоский граф изображается на сфере.
Для конечного связного плоского графа (а значит, и для графа на сфере) число \(\chi = v - e + f\) всегда равно 2 — каким бы этот граф ни был: сколько бы в нём ни было вершин и рёбер, как бы он ни был нарисован. Значит, число \(\chi\) не различает графы: по нему ничего нельзя сказать о самом графе.
А если проделать тот же подсчёт для связного графа, нарисованного на другой поверхности, получится другое число: например, для графа на торе выйдет \(\chi = 0\). Значит, число \(\chi\) зависит не от графа, а от той поверхности, на которой граф нарисован. Поэтому его и называют эйлеровой характеристикой поверхности.
Ответ: для любого связного графа на одной и той же поверхности число \(\chi = v - e + f\) получается одним и тем же (на сфере 2, на торе 0), поэтому оно говорит не о графе, а о поверхности.
Теорема: в любом конечном связном плоском графе сумма степеней всех областей чётна и равна удвоенному числу рёбер.
Это видно из обхода границ: если обойти по границе каждую область, то каждое ребро окажется пройденным ровно два раза. Ребро либо разделяет две области — и тогда его проходят по одному разу при обходе каждой из них, — либо дважды принадлежит границе одной и той же области — и тогда его дважды проходят при обходе этой области.
Ответ: сумма степеней всех областей конечного связного плоского графа чётна и равна удвоенному числу рёбер.
