Картинки из квадратов \ Прямоугольники, собранные из квадратов \ Блочные системы и сети \
 

5.3.1. Простейшие определения,
касающиеся сетей

Мы начнем с несколько более общего, чем сети, понятия графа (следуя в используемой терминологии приведенным здесь источникам).
Графом на плоскости называется всякая система линий, например прямолинейных отрезков, соединяющих между собой точки некоторой заданной системы точек; эти точки называются вершинами графа, а соединяющие эти точки линии (отрезки) — ребрами графа.
Части плоскости, ограниченные (вообще говоря, криволинейными) ломаными, образованными из ребер графа, называются гранями графа.
Приведенный здесь в качестве примера граф содержит 6 вершин, 10 ребер и 5 граней.
Для графов существенна только "общая архитектура" связи ребер с вершинами, а такие вопросы, как длина отдельных ребер, их форма (например, прямолинейные это отрезки или криволинейные), не имеют значения.
Так, изображенный слева граф с математической точки зрения ничем не отличается от графа, изображенного выше. В частности, как и предыдущий, этот граф содержит 6 вершин, 10 ребер и 5 граней.
Более строго можно сказать, что эти два графа являются изоморфными (мы не будем здесь уточнять этот термин, отсылая читателя к специальной литературе).
Подчеркнем, что мы будем иметь дело только с плоскими графами (т. е.  с графами, которые можно нарисовать на плоскости таким образом, что их ребра будут пересекаться друг с другом только в вершинах). Числа В вершин, Р ребер и Г граней каждого плоского графа связаны между собой формулой Эйлера:
В - Р + Г = 1.
В частности, для приведенных выше графов имеем:  6 - 10 + 5 = 1 (т. е. все правильно).
Иногда графы отождествляют с сетями, иногда же под сетями понимают графы специального вида. Мы будем придерживаться второй точки зрения.
Слева изображены два примера графов, которые мы будем называть сетями. Вообще, эти графы ориентированные, т. е. каждому ребру в них приписано свое "направление". Обычно направленность ребра указывается изображенной на нем стрелкой, однако рисовать стрелки на ребрах мне лень, поэтому они будут подразумеваться в соответствии со следующим правилом.
Если две вершины сети соединены ребром, то оно будет считаться направленным от более высокой вершины к более низкой. Чтобы это правило всегда работало корректно, при изображении сетей мы не будем допускать, чтобы какие-либо две связанные ребром вершины находились на одном уровне.
Если вершины M и N соединены ребром x, направленным от вершины M к вершине N, то мы будем говорить также, что ребро x входит в вершину N (или, что ребро x выходит из вершины M).
В наших сетях всегда будет иметься вершина, расположенная выше всех других вершин. Из нее ребра будут только выходить и не будет иметься ни одного ребра, которое в нее входило бы. Такая вершина будет называться истоком сети. На изображенных выше сетях a и b их истоки обозначены буквой s.
Аналогично, будет иметься одна вершина, расположенная ниже всех остальных вершин сети. В нее ребра будут только входить и не будет иметься ни одного ребра, которое из нее выходило бы. Такая вершина будет называться стоком сети. На изображенных выше сетях a и b их стоки обозначены буквой t.
  К началу данной страницы
Картинки из квадратов \ Прямоугольники, собранные из квадратов \ Блочные системы и сети \