Вопросы после параграфа §10 на странице 48, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Два графа называются изоморфными, если, во-первых, в них поровну вершин и поровну рёбер и, во-вторых, между множествами вершин и между множествами рёбер можно установить взаимно однозначное соответствие так, что любое ребро одного графа связывает две вершины тогда и только тогда, когда соответствующее ему ребро связывает соответствующие вершины в другом графе.
Ответ: графы называются изоморфными, если у них поровну вершин и поровну рёбер и между вершинами и между рёбрами можно установить взаимно однозначное соответствие, при котором ребро связывает две вершины одного графа тогда и только тогда, когда соответствующее ребро связывает соответствующие вершины другого.
Граф называется плоским, если все его вершины и рёбра лежат на плоскости и никакие два ребра не пересекаются во внутренних точках, то есть во всех точках, кроме концов. Общий конец у двух рёбер быть может: это вершина графа.
Ответ: плоским называется граф, все вершины и рёбра которого лежат на плоскости, причём никакие два ребра не пересекаются во внутренних точках.
Граф называется планарным, если он изоморфен какому-либо плоскому графу, то есть если его вершины можно расставить на плоскости по-другому и провести рёбра так, чтобы они пересекались только в вершинах.
Ответ: планарным называется граф, изоморфный какому-нибудь плоскому графу, то есть такой, который можно перерисовать на плоскости без пересечений рёбер во внутренних точках.
Да, верно. Сопоставим каждой вершине графа эту же вершину, а каждому ребру — это же ребро: соответствие взаимно однозначно, и ребро связывает две вершины тогда и только тогда, когда соответствующее ему ребро связывает соответствующие вершины. Значит, всякий граф изоморфен самому себе.
Плоский граф изоморфен самому себе, а сам он плоский, следовательно, он изоморфен плоскому графу, то есть планарен.
Ответ: да, каждый плоский граф планарен, потому что он изоморфен самому себе.
Нет, неверно — достаточно одного контрпримера.
Четыре вершины \(A\), \(B\), \(C\), \(D\), попарно соединённые 6 рёбрами \(AB\), \(BC\), \(CD\), \(DA\), \(AC\), \(BD\), расставим по вершинам квадрата: \(A\) — слева вверху, \(B\) — справа вверху, \(C\) — справа внизу, \(D\) — слева внизу. Рёбра \(AC\) и \(BD\) — диагонали квадрата, они пересекаются в его центре, а центр вершиной не является: такой граф не плоский.
Те же вершины расставим иначе: \(A\), \(B\), \(C\) — вершины треугольника, \(D\) — точка внутри него. Рёбра \(AB\), \(BC\), \(CA\) — стороны треугольника, а \(DA\), \(DB\), \(DC\) идут из внутренней точки к вершинам, и никакие два ребра не пересекаются во внутренних точках: этот граф плоский.
У обоих графов одни и те же вершины и одни и те же 6 рёбер, поэтому соответствие можно взять тождественное и графы изоморфны. Значит, первый граф планарен, хотя плоским он не является.
Ответ: нет, не каждый: полный граф на четырёх вершинах, нарисованный квадратом с двумя диагоналями, планарен, но не плосок, так как диагонали пересекаются в точке, вершиной не являющейся.
Годится треугольник: три вершины \(A\), \(B\), \(C\) и три ребра \(AB\), \(BC\), \(CA\). Этот граф плоский и связный, он делит плоскость на внутренность треугольника — конечную область — и всё, что лежит вне его, — бесконечную внешнюю область; других областей нет.
Подойдёт и петля: одна вершина и одно ребро, оба конца которого сходятся в этой вершине.
Ответ: например, треугольник — три вершины и три попарно соединяющих их ребра: его внутренность является конечной областью, а всё вне треугольника — бесконечной внешней областью.
Область — фигура без дырок, и граница области является замкнутым путём, поэтому пример надо искать среди несвязных графов.
Треугольник \(DEF\) лежит целиком внутри треугольника \(ABC\) и не соединён с ним ни одним ребром: получился плоский несвязный граф из шести вершин и шести рёбер. Он разбивает плоскость на три части: внутренность треугольника \(DEF\), часть между двумя треугольниками и бесконечную часть вне треугольника \(ABC\).
Первая и третья части — области, а часть между треугольниками областью не является: в ней есть дырка — внутренность треугольника \(DEF\), и граница этой части состоит не из одного замкнутого пути, а из двух.
Ответ: например, два треугольника, из которых один лежит внутри другого и не соединён с ним рёбрами: часть плоскости между треугольниками содержит дырку и областью не является.
Два графа называются изоморфными, если выполнены два условия:
1) в этих графах поровну вершин и поровну рёбер;
2) между множествами вершин и между множествами рёбер этих графов можно установить взаимно однозначное соответствие так, что любое ребро одного графа связывает две вершины тогда и только тогда, когда соответствующее ему ребро связывает соответствующие вершины в другом графе.
Изоморфные графы устроены одинаково, поэтому их часто не различают: их считают разными изображениями одной и той же системы связей.
Ответ: графы называются изоморфными, если у них поровну вершин и поровну рёбер и между вершинами и между рёбрами можно установить взаимно однозначное соответствие, при котором ребро связывает две вершины одного графа тогда и только тогда, когда соответствующее ребро связывает соответствующие вершины другого.
Граф называется плоским, если все его вершины и рёбра лежат на плоскости и никакие два ребра не пересекаются во внутренних точках.
Внутренние точки ребра — это все его точки, кроме концов. Общий конец у двух рёбер быть может: это вершина графа. Запрещены только «перекрёстки» вне вершин.
Ответ: плоским называется граф, все вершины и рёбра которого лежат на плоскости, причём никакие два ребра не пересекаются во внутренних точках.
Граф называется планарным, если он изоморфен какому-либо плоскому графу.
Иными словами, граф планарен, если его вершины можно расставить на плоскости по-другому и провести рёбра так, чтобы они пересекались только в вершинах. Система связей при этом сохраняется, меняется лишь чертёж.
Ответ: планарным называется граф, изоморфный какому-нибудь плоскому графу, то есть такой, который можно перерисовать на плоскости без пересечений рёбер во внутренних точках.
Да, верно. Пусть дан плоский граф. Сопоставим каждой его вершине эту же вершину, а каждому ребру — это же ребро. Такое соответствие взаимно однозначно, и ребро связывает две вершины тогда и только тогда, когда соответствующее ему ребро (то есть оно само) связывает соответствующие вершины (то есть те же самые). Значит, всякий граф изоморфен самому себе.
Плоский граф изоморфен самому себе, а сам он плоский. Следовательно, он изоморфен плоскому графу, то есть планарен.
Ответ: да, каждый плоский граф планарен, потому что он изоморфен самому себе.
Нет, неверно: достаточно одного контрпримера.
Возьмём четыре вершины \(A\), \(B\), \(C\), \(D\), попарно соединённые рёбрами, — всего 6 рёбер: \(AB\), \(BC\), \(CD\), \(DA\), \(AC\), \(BD\). Расставим их по вершинам квадрата: \(A\) — слева вверху, \(B\) — справа вверху, \(C\) — справа внизу, \(D\) — слева внизу. Тогда рёбра \(AC\) и \(BD\) — диагонали квадрата, и они пересекаются в его центре, а центр квадрата вершиной не является. Такой граф не плоский.
Те же четыре вершины можно расставить иначе: \(A\), \(B\), \(C\) — вершины треугольника, а \(D\) — точка внутри него. Рёбра \(AB\), \(BC\), \(CA\) — стороны треугольника, а \(DA\), \(DB\), \(DC\) идут из внутренней точки к вершинам, и никакие два ребра не пересекаются во внутренних точках. Этот граф плоский.
У обоих графов одни и те же четыре вершины и одни и те же 6 рёбер, поэтому соответствие можно взять тождественное, и графы изоморфны. Значит, первый граф планарен, хотя плоским он не является.
Ответ: нет, не каждый: полный граф на четырёх вершинах, нарисованный квадратом с двумя диагоналями, планарен, но не плосок, так как диагонали пересекаются в точке, вершиной не являющейся.
Годится треугольник: три вершины \(A\), \(B\), \(C\) и три ребра \(AB\), \(BC\), \(CA\). Этот граф плоский и связный. Он делит плоскость на две области: внутренность треугольника — конечная область, а всё, что лежит вне треугольника, — бесконечная внешняя область. Других областей нет.
Подойдёт и петля: одна вершина и одно ребро, оба конца которого сходятся в этой вершине, — петля точно так же отделяет свою внутренность от бесконечной внешней части плоскости.
Ответ: например, треугольник — три вершины и три попарно соединяющих их ребра: его внутренность является конечной областью, а всё вне треугольника — бесконечной внешней областью.
Область — это фигура без дырок, и граница области является замкнутым путём. Поэтому пример надо искать среди несвязных графов.
Возьмём треугольник \(ABC\) и треугольник \(DEF\), целиком лежащий внутри треугольника \(ABC\) и не соединённый с ним ни одним ребром. Получился плоский граф из шести вершин и шести рёбер; он не связный.
Этот граф разбивает плоскость на три части: внутренность треугольника \(DEF\), часть между двумя треугольниками и бесконечную часть вне треугольника \(ABC\). Первая и третья части — области. А часть между треугольниками областью не является: в ней есть дырка — внутренность треугольника \(DEF\), и граница этой части состоит не из одного замкнутого пути, а из двух.
Ответ: например, два треугольника, из которых один лежит внутри другого и не соединён с ним рёбрами: часть плоскости между треугольниками содержит дырку и областью не является.
