В некоторой стране железнодорожная сеть устроена так, что можно попасть из любого города в любой другой (возможно, через другие города). Докажите, что всегда можно выбрать такой город, что если закрыть на ремонт все ведущие в него дороги, то всё равно можно будет попасть из любого города в любой другой (кроме самого выбранного города).
Докажите утверждение.
Ответ
Граф железных дорог связен. Если в нём есть циклы, будем удалять по одному ребру из каждого цикла, пока циклов не останется, — связность при этом не нарушается. Получим остовное дерево \( T \), содержащее все города.
В дереве есть лист. Дерево с \( n \ge 2 \) вершинами имеет \( n - 1 \) ребро, поэтому сумма степеней равна \( 2(n-1) < 2n \), и хотя бы одна вершина имеет степень меньше 2. Степень 0 невозможна (дерево связно), значит, есть вершина \( v \) степени 1 — лист.
Выбираем город \( v \). Если удалить лист вместе с единственным ведущим в него ребром, оставшийся граф \( T - v \) остаётся деревом: он связен (любая цепь между двумя другими вершинами дерева не проходила через \( v \), ведь через вершину степени 1 пройти «насквозь» нельзя) и не содержит циклов. Значит, все остальные города по-прежнему связаны дорогами дерева \( T \), а тем более — дорогами исходной сети. Что и требовалось доказать.
Что применять при решении
Связный граф, компоненты связности, полный граф
Граф называется связным, если для любых двух его вершин найдётся путь, который их соединяет. Несвязный граф состоит из нескольких связных компонент (компонент связности). Граф без рёбер — «самый несвязный»: каждая вершина — отдельная компонента. Полный граф — граф, в котором каждая пара вершин соединена ребром; он связен и содержит наибольшее возможное число рёбер.
Число рёбер полного графа с \( 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. Оплата после того, как увидите работу.
Уведомление об авторском праве и цитировании
ВНИМАНИЕ: Представленные фрагменты из учебных материалов
используются исключительно в научно-образовательных целях в объеме,
оправданном поставленной целью.
Данное использование осуществляется в рамках, установленных законодательством об авторском праве
(в частности, нормами о свободном использовании произведения для образовательных целей).
В соответствии с законодательством, автор и источник заимствования
указаны для каждого используемого фрагмента.
