Давайте обсудим, каким может быть число компонент связности в графе. И в принципе, это может быть любое число от единицы до числа вершин. На этом примере у нас граф, в котором одна компонента связности (граф связен), а на таком примере у нас каждая вершина — это отдельная компонента связности, и компонент связности столько, сколько есть вершин в графе. Но можно ли сказать что-то более точное, если знать количество вершин и количество ребер в графе? И оказывается, что можно. Оказывается, что число компонент в графе не меньше, чем число вершин минус число ребер. Давайте поймем, что здесь, собственно, сказано? И что из этого всего следует? Если у нас ребер на два меньше, чем число вершин (или даже еще меньше), то граф не связен (компонент связности будет минимум две). Если граф связен, то напротив, число ребер должно быть, как минимум, число вершин минус один (это требуется, чтобы у нас была одна компонента связности). И оценка ничего не говорит, если ребер много. Если ребер, как минимум, число вершин минус один, то оценка ничего не говорит о связности или не связности графа. Но при малом числе ребер оценка полезна. Давайте ее докажем. Давайте сделаем следующее: давайте удалим из графа все ребра и будем по одному возвращать их обратно. И в самом начале, после удаления всех ребер, у нас в графе V вершин и нет ребер, и при этом число компонент связности совпадает с числом вершин. Оценка верна: число компонент связности не меньше, чем число вершин минус ноль (минус число ребер), так что в начале оценка верна. При возвращении одного ребра что происходит с величиной число вершин минус число ребер, V минус Е? Оно уменьшается на единицу. Число ребер увеличивается на один, поэтому величина уменьшается на единицу. Посмотрим, что происходит с числом компонент связности. Выделим текущий компонент связности в графе (вот, они здесь выделены на картинке). В них содержатся вершины, между которыми можно дойти из одной в другую. Давайте разберем два случая: вот мы возвращаем ребро — как оно может быть устроено? Может так случиться, что это ребро соединяет вершины в одной компоненте связности, и тогда, на самом деле, ничего не изменилось: мы из каких вершин могли дойти в другие, тут точно так же можем дойти и после добавления ребра. Ничего не изменилось: мы между вершинами, которые мы соединили ребром, мы и раньше могли дойти, там раньше был путь. Поэтому тут ничего не поменялось в смысле компонент связности. Есть второй случай: ребро соединяет вершины в разных компонентах связности. И тогда, как в этом примере, у нас между двумя компонентами связности появляется мостик, и теперь мы можем из С1 переходить в С3. Мы можем взять любую вершину в С1, дойти до вершины, которую мы соединили с компонентой С3, перейти по этому мостику — и дальше дойти, куда нам нужно, в компоненте С3, и в этом случае две эти компоненты сольются в одну. Итак, при возвращении одного ребра число компонент связности либо не меняется (если ребро попало внутрь одной из компонент), либо оно уменьшается на единицу (если ребро соединило две разные компоненты). Итак, в начале число компонент связности не меньше V минус Е (числа вершин минус число ребер), это было до возвращения ребер; при возвращении ребра число компонент связности может не измениться, а может уменьшиться на единицу, а величина, с которой мы его сравниваем, она точно уменьшается на один при каждом возвращении ребра. В начале число компонент связности было не меньше, чем эта величина; каждый раз величина, с которой мы сравниваем число компонент связности, убывает сильнее (не меньше, чем число компонент связности), и поэтому после возвращения ребра неравенство будет продолжать быть верным: V минус Е уменьшилось на единицу, а число компонент связности могло уменьшиться на единицу, а могло и не измениться. Неравенство остается верным после возвращения одного ребра, а значит, и в конце, после возвращения всех ребер, оно останется верным. Итак, мы доказали наше утверждение. Давайте посмотрим пример, когда такое утверждение оказывается полезным. Пусть у нас есть такая задача: у нас есть n камней и у нас есть чашечные весы. И за одно взвешивание мы можем сравнить по весу два камня. Вопрос: сколько нужно взвешиваний, чтобы гарантированно найти самый тяжелый среди этих камней? Изначально, в принципе, может быть вообще непонятно, причем тут графы и компоненты связности, как они нам помогут в этой задаче? Но давайте начнем разбираться. Давайте сначала поймем, за сколько взвешиваний это можно сделать. В принципе, нетрудно понять, что за n минус одно взвешивание это получится сделать. Мы можем делать просто следующее: мы можем брать два любых камня из нашей кучи, сравнивать их, и тот, который оказался легче, мы можем отбрасывать, потому что он точно не может быть самым тяжелым. Поэтому за одно взвешивание мы можем уменьшать количество камней в нашей куче на единицу — за каждое взвешивание мы отбрасываем один камень. У нас изначально n камней, и после n минус одного взвешивания у нас останется только один камень. Все остальные не могут быть самыми тяжелыми (мы их отбросили), значит, он — самый тяжелый. Но можно ли обойтись меньшим числом взвешиваний? И вот оказывается, что меньше, чем n минус одно взвешивания, не хватит. Как же это понять? Давайте рассмотрим такой граф. Давайте вершинами у нас будут являться камни, а ребрами мы будем соединять те камни, которые мы сравнивали на весах. И заметим, что нас даже не интересует результат взвешиваний, мы просто проводим ребро, если мы сравнивали эти два камня. Итак, пусть мы сделали меньше, чем n минус одно взвешивания, и тогда в нашем графе n вершин и не больше, чем n минус два ребра. И тогда наш граф не связен, по только что доказанному утверждению, наш граф не связен, и поэтому в нем есть как минимум две компоненты связности. Давайте посмотрим на такую картинку. Вот эти две компоненты связности, и давайте заметим, что мы не сравнивали камни в этих двух компонентах друг с другом. Мы сравнивали зеленые камни между собой, мы сравнивали красные камни между собой, но мы не сравнивали зеленые камни с красными. И тогда, в принципе, все камни в одной из компонент могут быть сильно тяжелее, чем камни в другой, то есть все зеленые камни вполне могут быть сильно тяжелее, чем все красные камни. И наоборот тоже может быть: все красные камни могут быть сильно тяжелее всех зеленых. И на результатах нашего взвешивания это никак не скажется: мы сравнивали только зеленые между собой и красные между собой, мы не сравнивали их между кучами, поэтому мы, в принципе, не знаем, какой из камней самый тяжелый: это может быть самый тяжелый камень в зеленой куче, а может быть самый тяжелый камень в красной куче. Наши взвешивания ничего об этом не говорят.
