03 Графы. Деревья.

Это неверно. Например, если рассмотреть такой граф

то мы увидим, что в нем 5 вершин, 4 ребра, но деревом он, конечно, не является, потому что он даже не связный.

На самом деле, это уже будет верно.

Допустим, что - связный, в нем вершин, рёбер и выполняется соотношение

но он - не дерево.

Но тогда, раз - связный, то у него всегда существует остовное дерево . Причем в будет ребер точно меньше, чем в , потому что иначе бы сам был бы своим остовным деревом, а это не так по предположению.

Следовательно, в ребер меньше, чем в , а вершин - столько же (по определению остовного дерева).

Но тогда получается, что раз для выполнялось соотношение

а в у нас ребер меньше , а вершин - столько же, т.е.

то для соотношение

уже выполняться не будет.

Противоречие, ведь - остовное дерево, в частности, просто дерево. А для дерева такое соотношение, как мы уже доказали, всегда выполняется.

Следовательно, сам должен был быть своим остовным деревом, то есть - это дерево и мы получаем, что формула

является критерием деревьев в классе связных графов.

Разумеется, оно практически никогда не единственно. Чтобы это понять, достаточно вспомнить алгоритм построения остовного дерева связного графа.

В этом алгоритме мы берем любое ребро любого цикла и выбрасываем его и продолжаем так до тех пор, пока у нас есть циклы.

Но вот какое именно ребро взять и удалить у очередного цикла - зависит только от нас. Поэтому результаты могут получиться очень разными.

Например, у такого графа

Остовным деревом может быть как этот

Так и этот граф

Однако, конечно, в редких случаях для данного графа его остовное дерево - единственно. Нетрудно понять, что так будет точно если сам изначально был деревом. Тогда у него остовное дерево единственно - это он сам.

Сам граф , заметим, не обязательно связный. Но рассмотрим какую-то его компоненту связности . В ней тоже, естественно, все вершины имеют степень 15.

Но - связный граф (как и любая компонента связности). Однако, получается, раз в все вершины степени 15, то, в частности, в нет висячей вершины. А в дереве она всегда должна быть. Следовательно, - не дерево. Но - связный. Следовательно, в есть цикл. Этот цикл будет циклом и в самом графе .

Возьмем некоторое ребро , соединяющее вершины и . Удалим его.

Почему оставшийся граф - связный?

1 шаг.
Во-первых, заметим, что у нас все еще существует путь из в .

Действительно, если бы это было не так, то и лежали бы в разных компонентах связности . Пусть, например, .

Но тогда в все вершины кроме имеют четную степень, имела четную степень до удаления ребра , следовательно, теперь имеет нечетную степень.

Но тогда в у нас получается ровно 1 вершина нечетной степени (это ), а все остальные - четной. Такого не может быть по лемме о рукопожатиях (компоненту связности в данном случае можно считать просто отдельным графом).

Противоречие.

Следовательно, и после удаления ребра лежат в одной компоненте связности. То есть между ними есть путь.

2 шаг.
На самом деле, из вышесказанного следует, что и между любыми двумя вершинами в оставшемся графе после стирания будет путь.

Действительно, возьмем некоторые 2 вершины и . До стирания ребра между ними был путь, потому что исходный граф был связным.

Если этот путь не проходил через стертое ребро , то этот путь годится и после стирания.

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

Следовательно, мы любые две вершины и можем соединить путём и после стирания ребра .

И мы всё доказали.

Наша волейбольная сетка - это граф, вершинами которого являются узлы сетки, а ребрами - нитки сетки, соединяющие узлы.

И фактически нас спрашивают, сколько максимально ребер мы можем удалить из нашего графа, не потеряв его связности.

Исходно в графе было

Но что такое минимальный в плане количества ребер связный подграф данного графа?

Конечно же это его остовное дерево. То есть нам надо взять остовное дерево нашего графа - столько и будет ребер в графе после удаления максимального числа ребер при условии связности.

И сколько же ребер будет в остовном дереве нашего графа?

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

В исходном графе было

вершин, значит, столько их и будет в остовном дереве. Значит, ребер в остовном дереве будет на одно меньше,то есть 30650. Следовательно, удалить надо

рёбер.

Ясно, что карта страны - это граф, где вершины - города, а ребра - дороги.

По условию нам дано, что этот граф изначально связный.

Тогда можно взять его остовное дерево .

У этого остовного дерева есть висячая вершина по теореме.

Возьмем и удалим эту вершину и все выходящие из нее ребра исходного графа. Тогда в остовном дереве удалится только одно ребро (потому что в остовном дереве эта вершина была висячей) и, следовательно, оставшаяся часть остовного дерева будет связной. Но тогда и весь оставшийся граф тем более будет связным.