Хорошо, друзья, давайте немножко ещё порассуждаем о планарности графов и о том, как это связано с раскрасками. Мы уже говорили немножко об этом, вот я хочу ещё добавить важное содержательное замечание на эту тему. Так, ну смотрите, значит, давайте назовём, назовём планарный граф плоским, назовём планарный граф плоским, если он уже изображён на плоскости без пересечения рёбер не по вершинам. Конечно, таких изображений может быть много, но вот у нас есть конкретный плоский граф, изображённый на плоскости без пересечения рёбер не по вершинам. Назовём такой планарный граф плоским. Он изображён на плоскости без пересечения рёбер не по вершинам. [ПИШЕТ НА ДОСКЕ] Рёбер не по вершинам. Ну то есть без неправильных, если хотите, пересечений. Ну давайте так, чтобы было совершенно понятно, вот просто пример какой-то. Вот у нас есть граф K4, про который мы, конечно, знаем, что он планарен, но вот такое изображение этого графа плоским не является, это неплоский граф. Он, безусловно, планарный, как и всякий K4, понятное дело, но он неплоский, а плоский граф — это правильное изображение, при котором нехороших пересечений рёбер нет, любые два ребра пересекаются только по вершинам. Вот это граф плоский, а это граф неплоский, хотя оба они планарные и, вообще, представляют собой один и тот же граф K4, полный граф на четырёх вершинах. Вот давайте для плоского графа введём ещё одну характеристику, помимо тех, которые мы уже знаем. Знаем мы, конечно... Давайте вот в этом месте так обозначать число вершин, вот мы его обозначим v. Это мы с очевидностью знаем. И буковкой e обозначим тоже то, что мы, конечно, знаем — число рёбер в этом графе. Число рёбер в этом графе. Но есть ещё одна важная характеристика плоского графа, которую немножко неформально, может быть чуть-чуть, с формальной точки зрения, неаккуратно, но я сейчас определю. Я не хочу закапываться совсем в формалистические детали, потому что мне кажется, что курс в большей мере всё-таки развлекательный, привлекательный, а не формалистический. Ну будет всё понятно. Вот для этой картинки вообще сразу будет понятно. Назовём буковкой f число так называемых граней плоского графа. Значит, неформально, что такое грань плоского графа? Вот, например, нарисован плоский граф, вот у него одна грань, ограниченная таким циклом длины 3, вот у него другая грань, тоже ограниченная циклом длины 3. Вот у него третья грань, простите за занудство, снова цикл длины 3 её ограничивает, и есть ещё внешняя грань, то есть этот граф, он расположен на плоскости без пересечения рёбер не по вершинам. Вот он однозначно задаёт разбиение плоскости на некоторое количество областей. Видите, есть три как бы внутренних области, которые ограничены циклами, и есть некая внешняя бесконечная область, которая тоже возникает в результате. Вот все эти четыре области, давайте вот эту я тоже как бы условно изображу, называются гранями нашего плоского графа. Конечно, в этом месте слушатель должен, если он такой очень въедливый, если он понимает в каких-то математических тонкостях, он должен пристать с хитрыми и каверзными вопросами. Ну он скажет: «А представьте себе, что плоское изображение вашего графа — это не такая простенькая штуковина, а какая-нибудь бяка, ужасная бяка». Ну, например, есть такая замкнутая кривая, ну я условно рисую, чтобы долго не рисовать ломаную, на самом деле здесь ломаная какая-то будет присутствовать. Ну вот она вот такая. Жуткая-прежуткая. Сейчас я её как-нибудь долго буду рисовать, чтобы убедить вас в том, насколько на самом деле всё может быть ужасно. Вот она так там как-то ходит вокруг себя, но нигде сама себя не пересекает. Всё, я лично заблудился. Я лично просто заблудился в этой кривой, и я уже глядя на вот эту картинку… Кривая — хорошо, кривая — это ломаная, но всё равно, глядя на эту картинку, я уже даже не понимаю, где внешняя часть, а где внутренняя. Вот на картинке, которая тут, всё понятно, вот три внутренних части, одна внешняя. А тут какой-то очень-очень большой граф, его долго там, сложно укладывали на плоскость. Да, он оказался плоским, в итоге планарным, то есть мы смогли его изобразить без пересечения рёбер не по вершинам, но для этого нам пришлось вот так покрутиться. Ну вот пришлось. И где здесь грани? Ну вот, товарищи, есть такая замечательная теорема Жордана, которую доказывали не одно десятилетие, но, слава богу, уже больше ста лет назад доказали окончательно. Доказали, что если кривая непрерывна и при этом замкнутая, и не самопересекающаяся, то как бы хитро она ни была уложена на плоскости, как бы ужасно эта картинка ни выглядела, но эта кривая обязательно разграничивает ровно две области, одна из которых внутренняя по отношению к этой кривой, а другая внешняя. И вот если бы я не нарисовал эту замечательную ужасную картинку, то многие слушатели покрутили бы просто пальцем около виска и сказали: «Да вы что, математики, с ума сошли, что ли? Чего вы тут доказываете очевидные вещи? Конечно, если замкнутая кривая, не самопересекающаяся, то, конечно, она отграничивает две области — внутреннюю и внешнюю». А вот глядите сюда. Где внутренняя, где внешняя? Я лично запутался, то есть я даже не смог понять, куда мне дальше вести эту линию в этом лабиринте, чтобы замкнуть свою кривую. Ну то есть тут вот есть такие математические тонкости, но в них я вдаваться не хочу. Я повторяю, что за счёт вот этой хитрой теоремы Жордана, которая интуитивно кажется понятной, особенно на первый взгляд, число граней в этом графе, понятно, что такое. Давайте я ещё замечу, что, в принципе, грань может выглядеть вот так. Там нарисована какая-то циклическая граница. Ну понятно, что если внутренняя грань, то граница будет циклическая, а тут ещё внутри какие-то такие вот бяки сидят разные, вот такие вот. То есть так тоже может быть, грань может, как целая страна, внутри вот этого нашего плоского графа может быть какими-то реками испещрена. Вот если где-то произошло замыкание, всё, значит, это какая-то уже другая грань образовалась, а если нигде замыкания не произошло, тогда нет новых граней. Ну вот она грань, испещрённая такими вот дополнительными жилками-речками, и вот все эти рёбра, которые не образуют циклическую границу грани, все эти рёбра называются внутренними по отношению к этой грани. Вот здесь на картинке изображено понятие внутренних рёбер. Внутренние рёбра грани. Более того, в графе вообще может не быть внутренних граней. Ну, например, если мы изображаем на плоскости какое-нибудь дерево, естественно, оно является плоским графом. Вот такое вот дерево, да? Но у него вообще нет никакой циклической границы. В этом случае f равно единице, и единственная грань, которая отделяется на плоскости вот таким вот деревом, ну это, собственно, бесконечная грань, а все рёбра этого дерева являются, естественно, внутренними по отношению к ней. Вот такая вот история, то есть вот такое вот определение, которое связано с плоскими графами.
