Смотрите, друзья, вот еще такой интересный вопрос: мы с вами разобрали критерий двудольности графа, то есть мы знаем, что граф является двудольным, коль скоро в нем отсутствуют простые нечетные циклы. Вот наличие нечетных циклов является однозначно свидетельством того, что граф нельзя покрасить в два цвета, что он не является двудольным. А что будет с графом, если запретить в нем, наоборот, четные циклы? Вот давайте докажем, что если в графе [БЕЗ_ЗВУКА] G с множеством вершин V и множеством ребер E, что если в графе G мощность V равняется n и нет простых циклов четной длины, нет простых циклов четной длины, простых четных циклов, то количество ребер в этом графе заведомо небольшое, количество ребер в этом графе точно не превосходит 3 × (n – 1)/2. Ну любители чистоты слога могут, конечно, мне предложить еще здесь нарисовать целую часть, то есть округление до ближайшего снизу целого числа. Ну это понятно, если какое-то целое число — скажем, количество ребер — не превосходит некоторого, вообще говоря, нецелого числа, значит, оно не превосходит и его нижней целой части. Ну это мелочи. Это какие-то уже детали, плюс минус единичка. Давайте поймем, откуда взялась вот эта оценка? Оказывается, что отсутствие четных циклов гарантирует такое вот вполне себе небольшое количество ребер в графе. Ну давайте прежде всего, прежде всего заметим, что если в графе циклов нет вовсе, если в графе циклов нет вовсе, то этот граф, конечно, по определению является лесом. Но мы знаем, что в каждом дереве, которое составляет этот лесок, не больше ребер, чем количество вершин без единицы. Вернее, в точности столько ребер, чему равняется разность между количеством вершин и единицей. Так вот, если в графе нет циклов и он является тем самым деревом, то, конечно, количество ребер просто не превосходит (n – 1) в наших обозначениях. То есть в этой ситуации оценка получается с огромным запасом. Она даже в полтора раза лучше, чем та оценка, которую мы собираемся доказать. Ну замечательно. Тогда давайте предположим, что в графе циклы есть. Тогда пусть в графе есть циклы, но они, разумеется, все являются нечетными, потому что четные циклы мы запретили. Вот давайте я нарисую для пущей понятности дальнейшего такую картину: вот есть простой цикл. Ну, может быть, я какой-то коротенький нарисовал, ну неважно. Значит, есть простой цикл. Так, и он у меня нечетный. Да, это очень благополучно, а то я как-то не подумал. Ну, удачным образом он нечетным получился. Четных циклов у нас нет, иначе пришлось бы менять картину. Так, давайте заметим, что между любыми двумя вершинами этого цикла в виду отсутствия четных циклов, любые цепи, любые пути могут проходить только по ребрам того же самого цикла. То есть если у нас есть 2 какие-то вершины этого цикла, то мы можем двигаться между ними только по ребрам этого цикла. Ну, действительно, если бы это было не так, тогда существовала бы какая-нибудь цепочка, которая не проходит вообще по ребрам вот этого цикла. Ну если не между этими двумя вершинами, то уж точно между какими-то двумя существовала бы цепочка, вообще не задействующая ребер исходного цикла. Ну так посмотрите. Я не знаю, ну можно, конечно, произвести этот перебор подробно, но понятно, что один из трех циклов, которые образовались на картинке, — значит, вот этот цикл образовался на картинке, вот этот цикл образовался на картинке, и еще с самого начала был внешний цикл, — так вот один из этих циклов, конечно, имеет четную длину. Очень легко сообразить. Ну можно тупым перебором. Например, если здесь нечетное количество ребер в этой центральной цепочке, то и здесь оно не может быть нечетным, иначе сразу образуется четный цикл тут. И здесь оно не может быть нечетным, иначе четный цикл образуется здесь. То есть понятно, что оно и тут четное в этом случае и тут четное. Но тогда внешний цикл является четным вопреки нашему изначальному допущению. У нас четных циклов нету. Замечательно. Ну, наоборот, если центральная цепочка является четной, то понятно, что и здесь должно быть нечетное и здесь нечетное количество ребер. И опять получается, что внешний цикл четный, что, конечно, невозможно. То есть в любом случае выходит, что такая ситуация заведомо отсутствует. Не могут идти цепи между вершинами нашего цикла, ну, так сказать, внутри него или извне, неважно, но главное, что не по ребрам этого цикла. Не по ребрам они идти никак не могут. Замечательно. В частности, это означает, что любые 2 цикла (имеется в виду, конечно, простых цикла; если я не добавляю слово простой и никак не оговариваюсь, то на самом деле подразумевается именно это), так вот любые 2 цикла в графе G пересекаются не более чем по одной вершине. У них не может быть общих ребер, потому что эти общие ребра и были бы вот такими цепями, которые идут внутри одного большого простого цикла. Вот любые 2 простых цикла в G пересекаются не более чем по вершине. То есть либо вовсе не пересекаются, либо имеют ровно одну общую вершину. Никаких других вариантов быть не может. Не более чем по вершине. Замечательно. То есть картина какая-то вот такая: один цикл, другой цикл, там, третий какой-нибудь цикл вот такой, может быть, где-то отдельно. Потом к нему еще что-то приляпано. В общем, вот какая-то такая картина. Ну смотрите, как же много тогда в нашем графе может быть циклов? Давайте оценим их количество. Ведь смотрите, у них же нет общих ребер. А в каждом из них — внимание! — очевидно, что в каждом из этих циклов не меньше 3-х ребер, правильно? Потому что цикл (самый короткий цикл, простой цикл я имею в виду) — это, конечно, треугольник. Ну я плохо нарисовал, вы меня будете сейчас осуждать. Я плохо нарисовал, потому что вот этот цикл является четным. Ну, товарищи, я думаю, вы понимаете и простите меня. Имеется в виду, что здесь, скажем, 5 вершин, здесь 17. Вот надо было все такие рисовать. Четных циклов у нас нет, не смущайтесь. Это я просто не очень хорошо рисую. Забыл нарисовать лишнее ребро. Конечно, все циклы предполагаются нечетными, но в любом случае, повторяю, длина каждого их них. количество ребер в каждом из них никак не меньше тройки. Это означает, что число циклов в графе G никак не больше, чем количество ребер в этом графе поделить на 3. Циклы не имеют общих ребер. У каждого из них не меньше трех ребер, значит, их количество точно не превосходит числа всех ребер, поделенного на 3. Мощность E поделить на 3. А теперь давайте сделаем такой фокус: удалим из каждого цикла в нашем графе G ровно одно ребро. Ну, естественно, из каждого свое, потому что общих ребер, повторяю, они, конечно, не имеют. Значит, удалим из каждого цикла в G ровно одно уникальное свое ребро. Сколько удалится ребер? Ну понятно, удалится не больше, чем мощность E поделить на 3 ребер. Значит, останется в итоговом графе останется не меньше чем 2|E| / 3 ребер. После вот этой операции удаления как минимум 2|E| / 3 ребер все еще будут живы. Но новый граф, который у нас получился в результате этой операции удаления ребер, новый граф, опять-таки, является лесом, потому что мы разрубили каждый цикл в нем. Всё, этот граф является лесом. Ну значит у него не больше чем (n – 1) ребро, что он по-прежнему находится на (n – 1) вершине. То есть смотрите, с одной стороны, мы знаем, что у этого нового графа не меньше чем 2|E| / 3 ребер, а с другой стороны, мы понимаем, что этих же самых ребер не больше чем (n – 1). Ну, собственно говоря, и все. Значит, получается, что 2|E| / 3 не превосходит (n – 1), она не превосходит, видите? 2|E| / 3 не превосходит реального количества ребер, а оно, в свою очередь, не превосходит (n – 1). Ну то есть удвоенная мощность E/3 таки не превосходит (n – 1), откуда, в свою очередь, вытекает искомая оценка |E| ≤ 3 × (n – 1) / 2. Вот такая вот милая задачка, по-моему.