В некотором графе все вершины имеют степень 3. Докажите, что в нём есть цикл.
Докажите утверждение.
Ответ
Предположим, что циклов нет. Тогда каждая компонента связности графа — дерево. Возьмём любую компоненту: в ней больше одной вершины (из каждой вершины выходят три ребра), а в любом дереве с двумя и более вершинами есть лист — вершина степени 1 (см. упражнение 90). Но по условию все степени равны 3. Противоречие, значит, цикл есть.
Другой способ: выйдем из любой вершины и будем идти по рёбрам, не возвращаясь по только что пройденному ребру (из каждой вершины есть ещё два ребра, кроме того, по которому пришли). Вершин конечное число, поэтому рано или поздно мы попадём в уже посещённую вершину — участок пути от первого её посещения до второго и есть цикл.
Что применять при решении
Связный граф, компоненты связности, полный граф
Граф называется связным, если для любых двух его вершин найдётся путь, который их соединяет. Несвязный граф состоит из нескольких связных компонент (компонент связности). Граф без рёбер — «самый несвязный»: каждая вершина — отдельная компонента. Полный граф — граф, в котором каждая пара вершин соединена ребром; он связен и содержит наибольшее возможное число рёбер.
Число рёбер полного графа с \( n \) вершинами: \( \dfrac{n(n-1)}{2} \)
Мосты
Ребро связного графа называется мостом, если после его удаления граф становится несвязным. Ребро является мостом тогда и только тогда, когда оно не принадлежит ни одному циклу: если ребро входит в цикл, после его удаления вершины по-прежнему связаны другой частью цикла.
Дерево и его свойства
Дерево — связный граф без циклов. Свойства: 1) в дереве каждое ребро является мостом; 2) между любыми двумя вершинами дерева существует единственная цепь; 3) дерево из \( n \) вершин содержит ровно \( n - 1 \) ребро; 4) в дереве с двумя и более вершинами есть хотя бы две вершины степени 1. Дерево, полученное из связного графа вычёркиванием «лишних» рёбер (по одному из каждого цикла), называется остовным деревом (остовом, каркасом) графа.
\( P = B - 1 \) для дерева с \( B \) вершинами и \( P \) рёбрами
Если в дереве выделена особая вершина — корень, дерево называют корневым и рисуют по ярусам: корень выше всех, ниже — его соседи и т. д. Вершины степени 1 называются листьями. Дерево случайного эксперимента: корень — начало опыта, вершины — состояния после очередного этапа, рёбра — переходы, листья — все возможные исходы. При \( n \) бросаниях монеты дерево двоичное и имеет \( 2^n \) листьев; у дерева опыта с кубиком из каждой вершины выходит по 6 рёбер. Если число шагов опыта разное (например, монету бросают до первого орла), листья лежат на разных ярусах и исходы не равновозможны.
Планарные графы и теорема Понтрягина — Куратовского
Граф называется планарным, если его можно нарисовать на плоскости так, чтобы рёбра попарно не пересекались (пересечения в вершинах не считаются); такое изображение называется плоским графом. Любое дерево планарно. Полный граф с 5 вершинами и граф «три домика — три колодца» (по три вершины в двух группах, каждая соединена с каждой из другой группы) непланарны. Теорема Понтрягина — Куратовского: любой непланарный граф содержит один из этих двух графов в качестве своей части.
Формула Эйлера для плоских графов и многогранников
Плоский граф разбивает плоскость на области — грани (одна из них неограниченная). Для любого связного плоского графа \( B - P + \Gamma = 2 \), где \( B \) — число вершин, \( P \) — рёбер, \( \Gamma \) — граней. Доказательство: для дерева \( P = B - 1 \), \( \Gamma = 1 \); удаление ребра из цикла уменьшает \( P \) и \( \Gamma \) на 1 и не меняет выражение. Та же формула верна для вершин, рёбер и граней выпуклого многогранника. Следствие: в планарном графе с \( B \ge 3 \) вершинами \( P \le 3B - 6 \).
Создать проектГотовый файл Word. Оплата после того, как увидите работу.
Уведомление об авторском праве и цитировании
ВНИМАНИЕ: Представленные фрагменты из учебных материалов
используются исключительно в научно-образовательных целях в объеме,
оправданном поставленной целью.
Данное использование осуществляется в рамках, установленных законодательством об авторском праве
(в частности, нормами о свободном использовании произведения для образовательных целей).
В соответствии с законодательством, автор и источник заимствования
указаны для каждого используемого фрагмента.
